Решение. Такое значение S — 19. Своим первым ходом Петя может получить позиции 20, 23 и 76. Во всех случаях Ваня увеличивает количество камней в куче в четыре раза и выигрывает своим первым ходом.
Ответ: 19.
Приведём другое решение на языке Python.
Для контроля ходов игроков заведём переменную m.
Если m = 1, то это действие x + 1.
Если m = 2, то это действие x + 4.
Если m = 3, то это действие x · 4.
Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.
def f(x, h, m):
if h == 3 and x >= 78:
return 1
elif h == 3 and x < 78:
return 0
elif x >= 78 and h < 3:
return 0
else:
if h % 2 == 0:
if h == 2:
if m == 1:
return f(x + 1, h + 1, m) or f(x * 4, h + 1, m)
elif m == 2:
return f(x + 4, h + 1, m) or f(x * 4, h + 1, m)
elif m == 3:
return f(x + 1, h + 1, m) or f(x + 4, h + 1, m)
else:
return f(x + 1, h + 1, 1) and f(x + 4, h + 1, 2) and f(x * 4, h + 1, 3)
for x in range(1, 78):
if f(x, 1, 0) == 1:
print("Задача 19:", x)
break
Приведём решение Евгения Джобса (аналитическое).
Изобразим игру схематически:
Сперва определим все значения S, при которых ходящий из них игрок может выиграть первым ходом (одним или несколькими из допустимых ходов). Тогда:
Следовательно, при значениях S, принадлежащих диапазону [20; 77], игрок, делающий ход из них одерживает победу своим первым ходом (выигрышные позиции для игры длиной в один ход).
Чтобы найти выигрышные позиции для игры длиной в два хода (вопрос задачи), необходимо, чтобы после первого хода следующий игрок ходил из выигрышной позиции для игры длиной в один ход.
Приведём решение Евгения Джобса (электронные таблицы, формула).
Вставим в столбец А с ячейки A1 числа арифметической прогрессии от 1 до 78 с шагом 1.
В ячейке В1 запишем формулу для победы первым ходом В1:
=ЕСЛИ(ИЛИ(А1+1>79;A1+4>79;A1*4>79);1;0).
В ячейке C1 запишем формулу для победы вторым ходом:
B1 =ЕСЛИ(ИЛИ(A1+1>79;A1+4>79;A1*4>79);1;0).
Условие B1 = 1 гарантирует, что проверяемое значение не удовлетворяло игре в один ход. ИНДЕКС(В:В;А1*4) возвращает значение для 4S в столбце В. Также для удобства поиска найденных значений наложим на диапазон B:Е условное форматирование для значений неравных 0.
Приведём решение Юрия Красильникова на языке Python.
def move(n,lim,s):
# n - номер хода, lim - ограничение на число ходов, s - число камней
# Результат: 1 - выиграл первый игрок, 2 - второй, 0 - победителя нет
player = 2 - n%2# Текущий игрок
rival = 3 - player# Противник
if s >= 78:# Игра уже окончена
return rival # Выиграл сделавший предыдущий ход
if n > lim:# Превышен лимит ходов
return 0# Победитель не определен
pos = [s+1, s+4, s*4]# Позиции после хода игрока
res = [move(n+1, lim, x) for x in pos]# Результаты ходов
if any([x == player for x in res]):# Есть выигрышный ход
return player
if all([x == rival for x in res]):# Все ходы проигрышные
return rival
return 0# Победитель не определен
print('#19:',*[s for s in range(1,78) if move(1,2,s)==2])
print('#20:',*[s for s in range(1,78) if move(1,1,s)==0 and move(1,3,s)==1])
print('#21:',*[s for s in range(1,78) if move(1,2,s)==0 and move(1,4,s)==2])
PDF-версии: 