Авторы:
Жучков Борис (6 класс)
Казанцева Варвара (7 класс)
Руководитель команды:
Зинцова Анастасия Сергеевна
Из кучи, содержащей Н камней, два игрока по очереди забирают порции, первый – 1 или 4 камня, второй – 2 или 3 камня. Проигрывает тот, кто не может сделать ход. Кто победит?
Этой табличкой мы отвечали на вопрос “Что будет, если первому или второму игроку на его ход достанется n камней?”
В переводе на русский, n - сколько камней досталось какому-то игроку на какой-то ход, n показано в верхней синей строке.
На первой жёлтой строчке мы отображаем знаком “+” выигрышные и “-” проигрышные случаи, когда первый игрок получает n на свой ход.
На второй жёлтой строчке мы отображаем знаком “+” выигрышные и “-” проигрышные случаи, когда второй игрок получает n на свой ход.
NB: Первое предложение относится к первому игроку, второе - ко второму.
Если достанется...
Ноль камней всем, для всех - проигрыш, значит везде ставим минусы .
1-ому игроку 1 - это выигрыш, он берёт 1 камень и оставляет ег0 второму игроку (+).
2-ому игроку 1 - проигрыш, т.к. он не может оттуда взять ничего, иначе кол-во камней уйдёт в отрицательную зону (+).
Для 1-ого 2 камня - выигрыш (+).
Для 2 игрока 2 - выигрышный случай (+).
Для 1-ого игрока 3 камня - проигрыш, он берёт 1 камень, 2 игрок забирает 2 и выигрывает - проигрыш (-).
3 камня получит 2-ой игрок, то он выиграет, взяв 3 камня - выигрыш (+).
4 - выигрыш для первого, сводится к 0 для второго (+).
4 для второго сводится к 1 или 2, выигрышными для первого, а значит это проигрыш (-).
5 для первого сводится к проигрышным для 2-ого 1 и 4 - выигрыш (+).
5 для 2-ого сводится к 3 проигрышной и 2 выигрышной для 1-ого. Нам, как для 2-ого игрока не важно, что есть один случай для нас проигрышный, нам важно, что есть один выигрышный, мы следуем по этому пути и берём 2 камня и отдаём 3 камня, проигрышную ситуацию 1 игроку - выигрыш (+).
6 сводится 1-ым игроком к 5 и 2, которые выигрышны для 2-го - проигрыш (-).
6 сводится 2-ым игроком к 4 и 3; 4 выигрышна для 1-ого, но 3 - проигрышна, значит 2-ому надо брать 3 камня и оставлять 1-ому проигрышные 3 - выигрыш (+).
7 сводится 1-ым игроком к 6 или 3, которые проигрышны для него, значит это проигрыш (-).
7 сводится 2-ым игроком к 4 и 5, которые для первого игрока выигрышны, значит это проигрыш (-).
8 сводится к семёрке - (+).
8 2-ым сводится к 6 - (+).
9 сводится к 5 - (+).
9 сводится к 7 - (+).
10 сводится к 6 и 9, которые для второго игрока выигрышные, значит (-).
10 сводится к 7, которая для первого проигрышна для первого, значит (+).
11 сводится к 7 и 10, которые выигрышные для 2-ого, значит (-).
11 сводится к 9, (+).
12 сводится к 11 и 8, которые выигрышны для 2-ого, (-).
12 сводится к 10, (+).
13 сводится к 12 и 10, которые выигрышны для 2-ого, (-).
13 сводится к 11 и 10, которые для 1-ого проигрышные, (+).
14 сводится к 13 и 10, которые выигрышны для 2-ого, (-).
14 сводится к 12 и 11, которые для 1-ого проигрышные, (+).
Цепь, где 1-ый постоянно проигрывает, а 2-ой постоянно выигрывает уже и так длинна, поэтому мы утверждаем, что дальнейшие продолжения этого ряда бессмысленны, т.к. в случае 12 1-ый игрок получил ситуацию, что с кучи, где 8 камней и больше, второй будет постоянно выигрывать, а значит, цепь эта будет продолжаться далее, т.к. второй игрок проиграть не может, т.к. у первого накопилось достаточно поражений “в ряд”, чтобы тот выиграл;
ПЕРВЫЙ БУДЕТ ВСЕГДА ПРОИГРЫВАТЬ ПРИ n<=12, А ВТОРОЙ БУДЕТ ВСЕГДА ВЫИГРЫВАТЬ ПРИ ТАКОМ n.
Первая модификация задачи
Добавим третьего игрока. Тогда, первый берёт 1 или 6, второй - 2 и 5, третий - 3 и 4. Сначала первый, потом второй, затем третий. Если один игрок проиграл, то оставшиеся 2 победили. Если игрок видит, что он не проиграет при обоих взятиях, то он забирает максимально возможное кол-во камней.
Ниже приведена таблица проигрышно-выигрышных позиций. Здесь приняты следующие обозначения:
Плюс или минус означают проигрышная или выигрышная позиция для игрока. 1п, 2п, 3п, 4п говорит о том, кто проиграет: первый, второй, третий или четвертый соответственно. В скобочках минус сколько-то говорит о том, сколько камней берет игрок.
Вывод: В данной задаче 2 игрок будет постоянно проигрывать, начиная с 19 камней, но тут есть брешь проигрыша 3 и выигрыша 2. Но мне кажется, что из-за того, что первый постоянно выигрывает за счёт 2, поэтому 3 постоянно выигрывает, а соответственно эта брешь прикрывается.
Вторая модификация задачи (для четырех игроков)
Добавим четвертого игрока. Тогда, первый берёт 1 или 8, второй - 2 и 7, третий - 3 и 6, четвертый -4 или 5 Сначала первый, потом второй, затем третий. Если один игрок проиграл, то оставшиеся 3 победили. Если игрок видит, что он не проиграет при обоих взятиях, то он забирает максимально возможное кол-во камней.
Ниже приведена таблица проигрышно-выигрышных позиций. Здесь приняты следующие обозначения:
Минус в ячейке говорит о том, что этот игрок в любом случае проиграет. 1п, 2п, 3п, 4п говорит о том, кто проиграет: первый, второй, третий или четвертый соответственно. Значение в скобочках говорит о том, сколько камней берет игрок.
Далее мы посчитали нелогичным заниматься ручным трудом, но ниже приведены мои предположения.
Есть у нас подозрение, что с какого-то момента у нас 4 игрок будет всегда проигрывать.
Гипотеза: Чем меньше у тебя разница между макс. и мин. возможностями хода, тем хуже для тебя.
Программа:
Я написала программу для двух игроков, чтобы проверить наше решение и использовать меньше ручного труда для нахождения таблиц и делать это быстрее. Программа позволяет набрать много данных для разных вариантов ходов и затем их проанализировать.
Мы программе даем номер хода, включительно до которого надо вывести всю таблицу. Количество, камней, которое могут брать игроки, меняем прямо в программе.
Ниже приведен скрипт программы для двух, где первый может брать 1 или 7, а второй 2 или 6:
for 2
first=[1]
step1=[1, 7]
step2=[2, 6]
second=[1]
stones=int(input())
fcount = 0
scount = 0
for i in range(1,stones+1):
for l in step1:
if len(second)>=l and second[i-l]==1:
fcount += 1
for L in step2:
if len(first)>=L and first[i-L]==1:
scount += 1
if fcount == 0:
first.append(1)
else:
first.append(0)
fcount=0
if scount == 0:
second.append(1)
else:
second.append(0)
scount=0
print(first)
print(second)
По этой ссылке можно перейти и протестировать программу: https://colab.research.google.com/drive/1RcedPz_7VcFuCjaAr7CRQJgSWGZMDBkV#scrollTo=vdjzDLjL0OJi
Результаты
Анализ результатов:
Далее s - это натуральное число.
Далее, чтобы проверить нашу гипотезу, мы запустили программу для s=20, то есть первый берет 1 или 61, а второй 2 или 60. Ожидая, что ситуация стабилизируется на 240 и выиграет второй. И наша программма подтвердила наши ожидания. Результат можете посмотреть по ссылке https://docs.google.com/spreadsheets/d/1kyC7xFeuZjU7hZF0lDklHQU9Mb8e4BnSlatnhBLHHE0/edit#gid=1940564115
Для чистоты эксперимента мы проверили и следующие два варианта задачи, когда первый берет 1 или 62, когда первый берет 1 или 63. И опять же по нашей формуле результаты программы сошлись с нашими и ситуация стабилизировалась на 122 и 123 соответственно.