Очевидно, (1,0,0) — проигрышная ситуация.
(n,0,0) — выигрышная, потому что можно за один шаг -(n-1,0,0) привести к проигрышной (1,0,0) (и передать ход противнику).
(n,1,0) — выигрышная, -(n,0,0) => (0,1,0).
Дальнейший анализ становится ветвистым... Поэтому сразу дам ответ.
Посчитаем характеристику следующим образом: это побитовый XOR количества спичек в кучках.
Для (1,0,0) это будет 1.
Утверждение: любая ситуация, для которой XOR равен 1, проигрышна.
Доказательство — по индукции.
1) любой ход из проигрышной ситуации меняет характеристику.
2) из любой ситуации (кроме проигрышных) можно сделать ход в проигрышную.
Обозначим текущую ситуацию как (p,q,r).
Пусть ситуация выигрышная, т.е. её характеристика x = p^q^r != 1.
Очевидно, p^q^r^x == x^x == 0, s = p^q^r^x^1 == 1.
Попробуем найти ситуацию, характеристикой которой является s.
Теперь расставим скобки: y = x^1. s == (p^y)^q^r == p^(q^y)^r == p^q^(r^y).
Выберем из этих вариантов тот, для которого t^y < t (t — это p, q или r).
То есть для которого мы сможем выполнить вычитание: dt = t-(t^y), t' = t-dt.
Нужно доказать, что такой вариант всегда найдётся. (Попробуйте).
Пусть ситуация (p,q,r) проигрышная, x = p^q^r == 1.
Любым ходом (для определённости, dp) мы получим s = (p-dp)^q^r == (p^y)^q^r == x^y.
Допустим (от противного), мы получили s == 1. То есть, y = s^x == 0.
Это значит, что p^y == 0, dp = p-(p^y) == p-p == 0. Попросту говоря, мы пропустили ход.
Как видите, задача элементарно обобщается на любое число кучек и спичек.
Условия такие:
играет двое.
есть 3 ряда спичек.
в верхнем 7 шт.
в среднем 5 шт.
в нижнем 3 шт.
Всегда можно забирать любое количество спичек, но только из одного ряда.
тот кто забирает последнюю спичку проиграл.
Здравствуйте, Олег Гашев, Вы писали:
ОГ>Условия такие: ОГ>играет двое. ОГ>есть 3 ряда спичек. ОГ>в верхнем 7 шт. ОГ>в среднем 5 шт. ОГ>в нижнем 3 шт. ОГ>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>тот кто забирает последнюю спичку проиграл.
ОГ>Выигрышная стратегия?
Выигрывает тот кто ходит первый. Его стратегия проста: сводить к проигрышным положениям. Проигрышные положения определяют тем, что любой наш ход приводит в выигрышное положение противника. Вот матрица положений:
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
----------- ----------- ----------- -----------
0| B . B B B B . B B B B B B B . B B B B B B . B B
1| . B B B B B B . B B B B B B B . B B B B . B B B
2| B B . B B B B B B . B B . B B B B B B . B B B B
3|0: B B B . B B 1: B B . B B B 2: B . B B B B 3: . B B B B B
4| B B B B . B B B B B B . B B B B B B B B B B B B
5| B B B B B . B B B B . B B B B B B B B B B B B B
6| B B B B B B B B B B B B B B B B . B B B B B B .
7| B B B B B B B B B B B B B B B B B . B B B B . B
B - выигрышные положения
Как видно никакой определенной простой стратегии не существует.
Здравствуйте, Neo09, Вы писали:
ОГ>>Условия такие: ОГ>>играет двое. ОГ>>есть 3 ряда спичек. ОГ>>в верхнем 7 шт. ОГ>>в среднем 5 шт. ОГ>>в нижнем 3 шт. ОГ>>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>>тот кто забирает последнюю спичку проиграл. ОГ>>Выигрышная стратегия?
N>Выигрывает тот кто ходит первый.
Не. Один мой "старший товарищ" выигрывает в эту игру вне зависимости от того, кто ходит первым
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Neo09, Вы писали:
ОГ>>>Условия такие: ОГ>>>играет двое. ОГ>>>есть 3 ряда спичек. ОГ>>>в верхнем 7 шт. ОГ>>>в среднем 5 шт. ОГ>>>в нижнем 3 шт. ОГ>>>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>>>тот кто забирает последнюю спичку проиграл. ОГ>>>Выигрышная стратегия?
N>>Выигрывает тот кто ходит первый. _FR>Не. Один мой "старший товарищ" выигрывает в эту игру вне зависимости от того, кто ходит первым
Как? Если у одного игрока есть стопроцентно выиграшная стратегия, то значит постоянно использовав ее он не сможет проиграть, а значит другой игрок не сможет выиграть
Здравствуйте, Neo09, Вы писали:
N>Здравствуйте, _FRED_, Вы писали:
_FR>>Здравствуйте, Neo09, Вы писали:
ОГ>>>>Условия такие: ОГ>>>>играет двое. ОГ>>>>есть 3 ряда спичек. ОГ>>>>в верхнем 7 шт. ОГ>>>>в среднем 5 шт. ОГ>>>>в нижнем 3 шт. ОГ>>>>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>>>>тот кто забирает последнюю спичку проиграл. ОГ>>>>Выигрышная стратегия?
N>>>Выигрывает тот кто ходит первый. _FR>>Не. Один мой "старший товарищ" выигрывает в эту игру вне зависимости от того, кто ходит первым
N>Как? Если у одного игрока есть стопроцентно выиграшная стратегия, то значит постоянно использовав ее он не сможет проиграть, а значит другой игрок не сможет выиграть
здесь написал прогу, которая играет и ходит первой. Я не смог выиграть Извините, интерфейс писать некогда.
Здравствуйте, Олег Гашев, Вы писали:
ОГ>Условия такие: ОГ>играет двое. ОГ>есть 3 ряда спичек. ОГ>в верхнем 7 шт. ОГ>в среднем 5 шт. ОГ>в нижнем 3 шт. ОГ>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>тот кто забирает последнюю спичку проиграл.
Решение (для любого количества кучек и спичек) привёл, кажется, Жак Арсак. А может быть, Мартин Гарднер. (Не помню).
Оно нетривиально и основано на двоичном представлении чисел
Здравствуйте, Олег Гашев, Вы писали:
ОГ>Условия такие: ОГ>играет двое. ОГ>есть 3 ряда спичек. ОГ>в верхнем 7 шт. ОГ>в среднем 5 шт. ОГ>в нижнем 3 шт. ОГ>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>тот кто забирает последнюю спичку проиграл.
ОГ>Выигрышная стратегия?
Стратегия такая:
Нужно убирать спички, так чтобы их число в любых двух рядах не было одинаковым, проиграет тот, кто нарушит это правило, т.е. выиграет тот кто создаст ситуацию 1, 2, 3 спички.
Если нарушить это правило, то соперник просто убирает ряд в котором количество спичек отлично от других и побеждает (там уже не такой сложный расклад).
Правда это решение порождает новую игру. Как убирать спички так, чтобы в итоге оказаться в той самой выигрышной ситуации.
В нашем случае начинающий игрок должен сделать первый ход убрав из 3 кучки 1 спичку, иначе он проиграет (просто можно посчитать). Далее он действует по ситации, там уже не так сложно все просчитывается...
Здравствуйте, Олег Гашев, Вы писали:
ОГ>Условия такие: ОГ>играет двое. ОГ>есть 3 ряда спичек. ОГ>в верхнем 7 шт. ОГ>в среднем 5 шт. ОГ>в нижнем 3 шт. ОГ>Всегда можно забирать любое количество спичек, но только из одного ряда. ОГ>тот кто забирает последнюю спичку проиграл.
ОГ>Выигрышная стратегия?
вроде так первый ходит и выигрывает.
ход1
убираем один ряд(любой).
ход2
а.если противник убрал полностью какой либо ряд, убираем в оставшемся все кроме одной (на след ходу мы выйграли)
б.если противник убрал в каком либо ряду все спички кроме одной убираем целый рад где несколько спичек (на след ходу мы выйграли)
в.если противник убрал какое либо количество в любом ряду но не такое как описано в 2 предыдущих случаях убираем в том ряду спички так чтобы осталось 2 шт. если в этом ряду их и так 2 то убираем в оставшемся ряду спички чтобы осталось только 2, на следущем ходу выйграем так как останется
2 2 и противнику есть возможность убрать либо 1 либо 2 а нам остается оставить 1 спичку либо убиранием ряда либо убиранием одной спички в одном оставшемся ряду...
В игру "Ним" можно играть в хапалки и в поддавки (кто берёт последнюю — выигрывает / проигрывает).
В первом случае цель — придерживаться XOR==0, во втором — XOR==1.
Здравствуйте, Кодт, Вы писали:
К>В игру "Ним" можно играть в хапалки и в поддавки (кто берёт последнюю — выигрывает / проигрывает). К>В первом случае цель — придерживаться XOR==0, во втором — XOR==1.
Перекуём баги на фичи!
