Решение Задания 20.. Решение Задания 21.

Решение Задания 20.

Ø Петя своим ходом должен перевести игру в такую позицию, что Ваня не может выиграть своим первым ходом, но добавление одного камня в любую кучу позволяет выиграть Пете вторым ходом

Ø рассмотрим такие (проигрышные) позиции; при удвоении второй (большей) кучи в сумме должно получаться 76 камней (недостаточно для выигрыша):

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

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

Ø поэтому условию задания удовлетворяют значения S = 31 и 34, их нужно записать в порядке возрастания

Ø Ответ: 31 34.

Решение Задания 21.

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

а) это проигрышная позиция, то есть все возможные ходы из нее ведут в выигрышные позиции;

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

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

Ø таблица будет прямоугольная, на вертикальной оси откладываем количество камней в первой куче, на горизонтальной – количество камней во второй куче:



					-1

				-1

			-1

		-1

	-1

-1

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

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



					-1

				-1

			-1

		-1

	-1

-1

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

Ø докажем, что в верхней строке больше нет позиций с кодом 2; по определению из позиции с кодом 2 есть ход в позицию с кодом «–1»; во всех позициях с кодом «–1», не попавших в рассмотренную часть таблицы, в первой куче больше 14 камней, то есть, стартовав с первой кучей из 7 камней, мы не можем получить такие позиции за один ход

Ø нам нужно найти в верхней строке позиции, из которых все ходы ведут в выигрышные позиции с кодами 1 (выигрыш за 1 ход) или 2 (выигрыш за 2 хода)

Ø сразу видны две таких позиции (выделены на следующем рисунке зелёным цветом):

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

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


	–2			–2
					-1

				-1

			-1

		-1

	-1

-1

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

Ø однако на самом деле позиция (7, 17) нам не подходит, докажем это, рассмотрев все возможные ходы Пети:

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

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

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

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

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

Ø Ответ: 30.

⇐ Предыдущая 12