Условие:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 81 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче – S камней; 1 ≤ S ≤ 73.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
Решение:
Чтобы решить эту задачу, давайте проанализируем условия игры и возможные ходы игроков. 1. Исходные условия: У нас есть две кучи камней. В первой куче 7 камней, во второй куче S камней (где 1 ≤ S ≤ 73). Игра заканчивается, когда общее количество камней в обеих кучах становится 81 или больше. 2. Цель игры: Игроки по очереди дел...
- : - Если он добавляет 1 камень в первую кучу, то в первой куче будет 8 камней, а во второй S. Общее количество камней: 8 + S. - Если он добавляет 1 камень во вторую кучу, то в первой куче 7, а во второй S + 1. Общее количество: 7 + (S + 1) = 8 + S. - : - Если он удваивает первую кучу, то в первой куче будет 14, а во второй S. Общее количество: 14 + S. - Если он удваивает вторую кучу, то в первой 7, а во второй 2S. Общее количество: 7 + 2S. Теперь давайте рассмотрим, как Ваня может ответить на каждый из этих ходов и при каком минимальном S он сможет выиграть. 1. : - Ваня может добавить 1 камень в первую кучу (9 + S) или во вторую (8 + S + 1). - Ваня может также удвоить первую кучу (16 + S) или вторую (8 + 2S). 2. : - Аналогично, Ваня может ответить. 3. : - Ваня может добавить 1 камень в первую (15 + S) или во вторую (14 + S + 1), или удвоить. 4. : - Ваня может добавить 1 камень в первую (8 + 2S) или во вторую (7 + 2S + 1), или удвоить. Чтобы Ваня мог выиграть, он должен сделать так, чтобы после его хода сумма камней была 80 или 79, чтобы в следующем ходе он мог довести сумму до 81. - Если Петя добавляет 1 камень в первую кучу (8 + S), Ваня может добавить 1 камень в первую кучу (9 + S) или удвоить (16 + S). - Если S = 73, то после первого хода Пети (например, добавление 1 камня в первую кучу) будет 8 + 73 = 81, и Ваня выиграет. Таким образом, минимальное значение S, при котором Ваня может выиграть после неудачного первого хода Пети, будет равно 73. : Минимальное значение S, при котором Ваня может выиграть, равно 73.