(8, 34) (10, 33) (12, 32) (14,31) (16,30) …

3. 
   теперь подумаем, какие из них можно получить из начальной позиции (7, S) за один ход; видно, что количество камней в первой куче изменяется, то есть Петя на первом ходу работает с первой кучей; он может получить там 7 + 1 = 8 камней (и у нас есть критическая позиция (8,34)!) или 7*2=14 камней (для этого случая тоже есть критическая позиция (14,31))
   
4. 
   поэтому условию задания удовлетворяют значения S = 31 и 34, их нужно записать в порядке возрастания
   
5. 
   Ответ: 31 34.
   

Решение Задания 21 (благодарю за обсуждение Д. Муфаззалова и В. Бабия).

1. 
   определим свойства позиции, которую мы ищем:
   

1. 
   это проигрышная позиция, то есть всех возможные ходы из нее ведут в выигрышные позиции;
   
2. 
   из этой позиции есть ход в выигрышную позицию, из которой Ваня не может выиграть за один ход, но может гарантированно выиграть за два; это значит, что есть ход в позицию, определённую в решении задачи 20 или равноценную ей!
   

2. 
   для полного решения задачи построим таблицу выигрышных и проигрышных позиций; выигрышные позиции будем обозначать положительными числами, например, 2 – выигрыш в два хода; проигрышные позиции обозначаем отрицательными числами, например, «–2» – проигрыш в два хода (это значит, что при самой лучшей игре первого игрока второй выиграет по крайней мере своим вторым ходом)
   
3. 
   таблица будет прямоугольная, на вертикальной оси откладываем количество камней в первой куче, на горизонтальной – количество камней во второй куче:
   

	28	29	30	31	32	33	34	35	36	37
7								1	1	1
8							-1	1	1	1
9							1	1	1	1
10						-1	1	1	1	1
11						1	1	1	1	1
12					-1	1	1	1	1	1
13					1	1	1	1	1	1
14				-1	1	1	1	1	1	1
15				1	1	1	1	1	1	1
16			-1	1	1	1	1	1	1	1
17			1	1	1	1	1	1	1	1
18		-1	1	1	1	1	1	1	1	1

---

пока в таблице расставлены единицы в позициях, которые ведут к выигрышу Пети на первом ходу и «–1» в позициях, которые ведут к выигрышу Вани на своем первом ходу (после любого первого хода Пети)

4. 
   отметим числом 2 ячейки, откуда есть ходу в серые клетки с ходом «–1»:
   

	28	29	30	31	32	33	34	35	36	37
7				2			2	1	1	1
8			2			2	-1	1	1	1
9						2	1	1	1	1
10					2	-1	1	1	1	1
11					2	1	1	1	1	1
12				2	-1	1	1	1	1	1
13				2	1	1	1	1	1	1
14			2	-1	1	1	1	1	1	1
15			2	1	1	1	1	1	1	1
16		2	-1	1	1	1	1	1	1	1
17		2	1	1	1	1	1	1	1	1
18	2	-1	1	1	1	1	1	1	1	1

---

в верхней строке таблицы выделены жёлтым позиции (7, 31) и (7, 34), найденные при решении предыдущего задания

5. 
   докажем, что в верхней строке больше нет позиций с кодом 2; по определению из позиции с кодом 2 есть ход в позицию с кодом «–1»; во всех позициях с кодом «–1», не попавших в рассмотренную часть таблицы, в первой куче больше 14 камней, то есть, стартовав с первой кучей из 7 камней мы не можем получить такие позиции за один ход
   
6. 
   нам нужно найти в верхней строке позиции, из которых все ходы ведут в выигрышные позиции с кодами 1 (выигрыш за 1 ход) или 2 (выигрыш за 2 хода)
   
7. 
   сразу видны две таких позиции (выделены на следующем рисунке зелёным цветом):
   

(7, 30) – возможные ходы в (7, 31), (8, 30) и (14, 30) с кодом 2 и (7, 60) с кодом 1

(7, 33) – возможные ходы в позиции (7, 34) и (8, 33) с кодом 2, а также (14, 33) и (7, 66) с кодом 1:

	28	29	30	31	32	33	34	35	36	37
7			–2	2		–2	2	1	1	1
8			2			2	-1	1	1	1
9						2	1	1	1	1
10					2	-1	1	1	1	1
11					2	1	1	1	1	1
12				2	-1	1	1	1	1	1
13				2	1	1	1	1	1	1
14			2	-1	1	1	1	1	1	1
15			2	1	1	1	1	1	1	1
16		2	-1	1	1	1	1	1	1	1
17		2	1	1	1	1	1	1	1	1
18	2	-1	1	1	1	1	1	1	1	1

---

8. 
   вроде бы все хорошо, и можно выбрать минимальное из двух найденных значений S (30), но кроме этих ячеек есть ещё кандидат на решение – S = 17, потому что ходом из позиции (7, 17) можно получить позицию (7, 34) с кодом 2
   
9. 
   однако на самом деле позиция (7, 17) нам не подходит, докажем это, рассмотрев все возможных ходы Пети:
   

(8, 17) (14, 17) (7, 18) (7, 34)

здесь жёлтым фоном выделены ходы с кодом 2 – выигрышные позиции за 2 хода (из позиции (8, 17) есть ход в (8, 34) с кодом «–1»)

10. 
    рассмотрим ход (14, 17); возможные ходы из него
    

(15, 17) (28, 17) (14, 18) (14, 34)

среди них нет ни одного хода в позицию с кодом «–1», то есть, ход Пети (14, 17) не даст Ване выиграть за 2 хода; поэтому эта позиция не подходит

11. 
    Ответ: 30.
    

Решение с помощью программы (рекурсия)

1. 
   напишем программу на языке Python, которая для всех значений S выдаёт код позиции (про коды позиций см. выше)
   
2. 
   сначала поясним идею; пусть нужно определить код позиции (x, y); для этого мы должны предварительно определить коды позиций, куда можно попасть одним ходом из (x, y):
   

(x+1, y) (2x, y) (x, y+1) (x, 2y)

поскольку нужно выполнить ту же самую операцию, это будет рекурсивная функция

3. 
   итак, пусть мы нашли коды четырёх возможных следующих позиций; рассмотрим несколько примеров:
   

1. 
   пусть эти коды [1, 2, 2, 3], то есть все возможные ходы ведут в выигрышные позиции, Петя проигрывает; он заинтересован в том, чтобы проиграть за максимальное число ходов (всячески оттягивая поражение), поэтому из этих кодов нужно выбрать максимальный и записать его со знаком минус, получаем код «–3», то есть Петя проиграет за 3 хода (на 3-м ходу Ваня выиграет)
   
2. 
   пусть эти коды [1, –2, 2, –3], то есть найдены два хода в проигрышные позиции (с кодами «–2» и «–3»), и Петя может выиграть; он заинтересован в том, чтобы выиграть за наименьшее число ходов, поэтому нужно выбрать максимальное из полученных отрицательных чисел («–2»), убрать знак минус и добавить единицу (Петя добавляет новый ход); поэтому для данного случая код клетки будет равен 3
   

4. 
   рекурсия должна заканчиваться, когда сумма x+yстала больше или равна 77; определим это значение как константу TARGET («цель»);
   

TARGET = 77

такую позицию (когда игра завершена) будем обозначать кодом 0 и считать её проигрышной

---

, как и позиции с отрицательным кодом

5. 
   запишем первую версию функции gameResult, которая принимает два параметра - количество камней в первой и второй кучах:
   

def gameResult( x, y ):

if x + y >= TARGET: return 0

# рекурсивно определяем коды всех возможных ходов

nextCodes = [ gameResult(x+1, y), gameResult(x*2, y),

gameResult(x, y+1), gameResult(x, y*2) ]

if в nextCodes есть отрицательные или 0:

res = -max(отрицательные или 0) + 1

else:

res = -max(nextCodes)

return res

6. 
   строки, выделенные красным цветом – это псевдокод, который нужно заменить на операторы Python; выделим из массива nextCodes все отрицательные числа и нули (соответствующие проигрышным позициям):
   

negative = [c for c in nextCodes if c <= 0]

тогда условный оператор if в nextCodes есть отрицательные или 0: может быть записан как

if negative:

res = -max(negative) + 1

else:

res = -max(nextCodes)

получается такая функция:

def gameResult( x, y ):

if x + y >= TARGET: return 0

# рекурсивно определяем коды всех возможных ходов

nextCodes = [ gameResult(x+1, y), gameResult(x*2, y),

gameResult(x, y+1), gameResult(x, y*2) ]

negative = [c for c in nextCodes if c <= 0]

if negative:

res = -max(negative) + 1

else:

res = -max(nextCodes)

return res

7. 
   попробуем посчитать коды для всех возможных значений S от 69 = 77-7-1 до 1:
   

X = 7

for S in range(TARGET-X-1,0,-1):

r = gameResult( X, S )

print( "{:d} {:d}".format(S, r) )

8. 
   к сожалению, обнаруживаем, что программа работает очень медленно… Дело в том, что программа много раз вычисляет значение кода для одних и тех позиций. Чтобы этого избежать, будем запоминать их в словаре results:
   

results = {} # (1)

def gameResult( x, y ):

if (x,y) in results: return results[(x,y)] # (2)

if x + y >= TARGET: return 0

nextCodes = [ gameResult( x+1, y ), gameResult( x*2, y ),

gameResult( x, y+1 ), gameResult( x, y*2 ) ]

negative = [c for c in nextCodes if c <= 0]

if negative:

---

Смотрите также файлы

• Экология мірді соып тран жрегі!.docx

• ТАырып Инвестициялы саясат туралы ым Инвестицияны экономикалы мазмны мен рлі Инвестиция термині латынны invest сзінен аударанда салым салу.docx

• Балаларды жасы 5 жас Жоспар андай кезеге жасалды (айды, жылды крсету).docx

• Математическая грамотность (8 класс) Характеристики заданий и система оценивания.docx

• Бастауыш, ши бауырса, самса мелкие, булочки мелкие, жеті нан.docx