Игра "11 спичек"

zzzXAXAXAzzz

Игра “11 спичек”
Двое игроков берут поочередно спички (всего 11 спичек) брать можно не более 3-х спичек за один ряд; проигрывает тот, кто берет последнюю спичку.
Ясно, что для победы 1-ому игроку необходимо оставить 2-му 5 или 4 спички. Тогда в любом раскладе 1-ый победил.
В случае для 11 спичек, надо пытаться выдержать сумму спичек после ходов = 6, так как 11-6=5. Соответсвенно для 11 их легко можно все записать, безвыиграшная только (3, 3).
Вопрос - а как переложить алгоритм на большее число спичек. Вообще требуется написать беспроигрышную программу. Может уже кто-то делал такую прогу? Для любого ли числа спичек можно сделать алгоритм?

andy_null

Игра Баше вроде называется. Идея - дополнять до 4х

zzzXAXAXAzzz

Идея - дополнять до 4х
ну это я так понимаю только одна тсратегия. К примеру, для 11 спичек имем
(2,31,х)
(2,22,х)
(2,13,х)
Тут действительно срабатывает дополнение до четырех, после хода 2.
Но есть и другая стратегия
(1,23,х)
(1,32,х)
(1,11,3)
(1,11,21,х)
(1,11,12,х)
Тут как раз срабатывает, чтобы сумма была 6, чтобы свести к остатку 5. Просто для большего количества спичек сложно программно реализовать алгоритм.

mtk79

а при чем здесь "проги" и "алгоритмы"? Это вполне конкретная школьная задача на делимость, решить которую для произвольных N — общего числа и n — максимальнго числа забора за один подход к фуршетному столу (N>n я надеюсь, Вы в состоянии.

zzzXAXAXAzzz

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

zzzXAXAXAzzz

а при чем здесь "проги" и "алгоритмы"?
при том, что надо написать программу, котораяреализует ВСЕ выигрышные алгоритмы

mtk79

никаких "всех" выигрышных алгоритмов не существует: если он существует для одного из игроков — то один неверный ход ведет к тому, что существует выигрышная стратегия у соперника

zzzXAXAXAzzz

выигрышный алгоритм для первого игрока, ситуация, что игрок тупанул не рассамтривается

mtk79

это при 11-3 выигрышный алгоритм (причем, единственный, а не два) для первого.

Skilet3d

не гони! алгоритм для первого: вытащить вначале 2 спички а дальше дополнять до 4, чтобы последняя осталась после хода первого игрока должно всегда оставать ся 4*k+1 спичка

zzzXAXAXAzzz

но можно выиграть 1-ым игроком, если взять вначале и 1 спичку...

ventr

нет, конечно
если есть алгоритм обеспечивающий выигрыш вытаскиванием 2 спичек,то нельзя выиграть вытащив 1.

ventr

(1,11,3)
вот эта часть мне не понятна,что первому дальше делать?
это проигрышная стратегия...

griz_a

Пусть всего N спичек.
Пусть первый может выиграть, взяв первым ходом n спичек.
Имеем
1) Если к ходу игрока остается N-n, то при любых его действиях он проигрывает.
Пусть первый может выиграть, взяв первым ходом m<n спичек.
Т.е. верно
2) Если к ходу игрока остается N-m, то при любых его действиях он проигрывает
Но, если из N-m второй возьмет n-m (0<n-m<=2) спичек, то их останется N-n и по 1 выиграет второй. Но это противоречит 2. Значит не существует различных m и n, таких, что взяв их первый выигрывает

CLERiC_77rus

Ясно, что для победы 1-ому игроку необходимо оставить 2-му 5 или 4 спички. Тогда в любом раскладе 1-ый победил.
не понял, как оставить 4 спички 2-му. он береn 3, и первый проиграл..

seregaohota

Номера проигрышных позиций при делении на 4 дают остаток 1. Т.е. проигрышные позиции 4n+1= 1,5,9,... остальные выигрышные. Т.к. берёшь столько спичек, чтобы всё время противник попадал на позицию 4n+1. С каждым полным ходом (сначала! противника, а потом своим) n уменьшается на 1, а число спичек в куче на 4.
С 11 спичек к этому ведёт первый ход "забрать 2".
Осталось 9 = 4*2+1 Противник забрал сколько то - ты забираешь так, чтобы попасть на
5. Потом на 1. И всё - он проиграл.
PS Более серьёзная задача в хобби в задачках на подумать моя задачка про N куч. запостил(а спасибо.
Оставить комментарий
Имя или ник:
Комментарий: