Question

В каждой клетке доски 10 на 10 лежит по 100 сосисок. Два кота Полосатики и Волосатик играют в игру по следующим правилам. За один ход можно выбрать в таблице строку и столбец в каждой клетке которого есть хотя бы одна сосиска и из всех этих клеток съесть по одной сосиске. Начинает полосатик, проигрывает не имеющие хода. Какой код имеет выигрышную стратегию? с решением. заранее спасибо

Answer 1

Незнаю может поможет ну так в класи решал
Ответ: При нечетном n выигрывает второй кот, при четном n - первый. В самом деле, пусть n = 2k+1 нечетно. Занумеруем все сосиски подряд числами от 1 до n . Сосиску с номером k+1 будем называть центральной. Второму коту каждым ходом нужно перегрызать перемычку, симметричную той, которую перегрыз на предыдущем ходу первый кот (относительно центральной сосиски). Тогда он съест сосисок не меньше, чем первый, причем первый при такой игре не сможет съесть центральную сосиску (так как ее концы (перемычки) симметричны друг другу относительно этой сосиски). Значит, второй кот съест не менее k+1 сосиски и выиграет. Пусть теперь n = 2k четно. Занумеруем все сосиски подряд числами от 1 до n . В этом случае первый кот должен первым ходом съесть одну из крайних сосисок (скажем, последнюю). Тогда перед вторым котом окажется нечетное число сосисок, и из них он сможет съесть только меньше половины, если первый игрок будет пользоваться стратегией второго для случая нечетного n. (Другими словами, далее первому игроку надо отвечать на ходы второго симметричными (относительно k+1-ой сосиски) ходами.) При такой стратегии первый игрок съест в результате по крайней мере на две сосиски больше, чем второй.

Answer 2

Эта игра, называемая "Игра в сосиски", является комбинаторной игрой. Для того чтобы выиграть, игрок должен следовать определенной стратегии, которая обеспечит ему победу, при условии, что у него есть выигрышная стратегия.

Правила игры:

1. Доска имеет размер 10x10, и в каждой клетке находится по 100 сосисок.
2. Два игрока, Полосатик и Волосатик, играют поочередно.
3. В свой ход игрок выбирает строку и столбец, в каждой клетке которого есть хотя бы одна сосиска, и съедает по одной сосиске из каждой выбранной клетки.

Давайте рассмотрим, какой код имеет выигрышная стратегия:

Игра имеет математическое решение, и она принадлежит классу так называемых "игр с нормальной формой Гранди". В этом случае, позиция игры представляется числом (Grundy number) для каждой возможной позиции на доске. Это число указывает на позицию в ним-числовой последовательности, и игрок, у которого число равно нулю, имеет выигрышную стратегию.

Для игры в сосиски на доске 10x10 с 100 сосисками в каждой клетке, Grundy number для каждой возможной позиции равен 0. Это означает, что у Полосатика и Волосатика нет выигрышных стратегий - игра всегда заканчивается в ничью, при правильной игре обоих игроков.

Итак, выигрышная стратегия отсутствует, и игра всегда завершается в ничью, при условии, что оба игрока играют оптимально.