есть нечетное число камней (например 135)
есть 2 игрока каждый берет из кучки от 1 до 4 выйгрывает тот кто набрал чётное количество камней

каков принцип задачи способ решения
негде не могу найти решение этой задачи

Выиграет тот кто всегда брал только четное число камней за раз. И\или четное число раз брал еще и нечетное количество камней за раз, то есть взял четыре раза по 3, 5, 7, 1 камней, например. Четыре раза бралось нечетное число камней, но в сумме они дадут четное число, так как в каждом нечетном есть одна лишняя единица, делающая из четного числа нечетное. Если таких "нечетных чисел\лишних единиц" становится 2, 4, 6 то эти единицы сливаясь превращаются в четное.

Доступно?

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

Airt_Reg
не все так просто. просто сформулировано странно. по идее это вариация игры на кто последний возьмет камни.
бо все умные. но если останется только 1 тебе придется его взять.

скорее победа у того - кто берёт предпоследним, промежуточное количество камней не играет роли, предпоследний в данной ситуации в любом случае побеждает.

Доступно-то доступно, но это всё общие рассуждения, не приводящие к выводу кто же именно при правильной стратегии сможет осуществить данный план. И шансов не может быть больше или меньше. В таких задачах предполагается, что соперники бесконечно умны, а так как игра конечна и ничья невозможна, то один из игроков имеет выигрышную стратегию, то есть способен выиграть независимо от действий оппонента.


Во-первых, это неверно; во-вторых даже если бы это было так, то кто же предпоследний - первый или второй?

benwar
Мда, давненько я такое не решал.
Сначала подумалось о стратегии, основанной на том, что при любом "ходе" можно сделать так, что твой ход и ход оппонента в сумме снимают пять камней, но четность сюда как-то не привязать. Нагуглил на вот это, но что-то я там не понимаю как считать ту функцию G(). Скажем что делать, если после того как первый взял 2 камня второй возьмет 1. Я так понял, что надо перевести G(0,0,1) в некое выигрышное состояние, но G(0,0,1) уже вроде как выигрышное, а сделать из него опять G(0,0,1) мы не можем, так как надо брать 0 или 6 камней. Но остаток по модулю 6 и выигрышные позиции взял на заметку, и вроде как решил.
Выигрывает первый.
Обозначать ситуацию в игре будем также, как в статье: (количество оставшихся камней, четность камней у первого, четность у второго). То есть в начале игры (135,0,0). Но лучше будем использовать в качестве первого числа не количество камней а остаток от деления этого количества на 6, то есть в начале игры (3,0,0). Наша задача привести игру к ситуации, из которой мы выиграем. Анализ показал, что достаточно трех ситуаций: (0,0,1), (1,0,0), и (5,1,1). Если эти "позиции" возникают после нашего хода, то после любого хода оппонента мы можем вновь привести ситуацию в одну из этих позиций. А в конце игры (0,0,1) - это и есть выигрыш по условию, (1,0,0) - оппонент вынужден забрать последний камень и проиграть, (5,1,1) - если оппонент берет четное число камней, то мы забираем остальные и выигрываем( (0,0,1) ), а если нечетное, то забираем все камни, кроме одного и тоже выигрываем( (1,0,0) ) после того как оппонент забирает последний ( (0,0,1) ). Покажем теперь, что походу игры первый игрок всегда своим ходом может сделать одну из этих позиций. Первым ходом он делает (1,0,0) из (3,0,0), забирая два камня. Далее в зависимости от хода второго:
Вариант (1,0,0)
Второй берет 1 камень: (0,0,1), тогда первый берет 1: (5,1,1)
Второй берет 2 камня: (5,0,0), тогда первый берет 4: (1,0,0)
Второй берет 3 камня: (4,0,1), тогда первый берет 4: (0,0,1)
Второй берет 3 камня: (3,0,0), тогда первый берет 2: (1,0,0)
Если первый делает позицию (1,0,0), то ситуация повторяется. Рассмотрим варианты (5,1,1) и (0,0,1):
Вариант (5,1,1):
1: (4,1,0) : 3 : (1,0,0)
2: (3,1,1) : 3 : (0,0,1)
3: (2,1,0) : 1 : (1,0,0)
4: (1,1,1) : 1 или 2 : (0,0,1) или (5,1,1)
Вариант (0,0,1):
1: (5,0,0) : 4 : (1,0,0)
2: (4,0,1) : 4 : (0,0,1)
3: (3,0,0) : 2 : (1,0,0)
4: (2,0,1) : 2 или 3 : (0,0,1) или (5,1,1)
Всё, при любых ходах второго мы возвращаемся в одну из выигрышных ситуаций, то есть когда камней останется 5 или меньше то мы тоже обязательно окажемся в одной из этих ситуаций и выиграем.
Замечание:
Важно, что второй при такой стратегии не может сделать ситуацию выигрышную для себя. Мы разобрали все случаи, а после хода второго не встречается вариантов (0,1,0), (1,0,0), или (5,1,1), что означало бы, что игроки по очереди меняются псевдовыигрышными позициями и стратегия неверна, так как в конце выигрышная может оказаться у второго. Замечание к замечанию: для второго аналогом (0,0,1) является (0,1,0), поэтому и изменение в одной из выигрышных ситуаций - второму ведь надо четное число у себя, а не у первого игрока.
Замечание 2: Не любое нечетное подойдет. Если вначале остаток от деления числа камней на 6 равен 1, то побеждает второй (если вначале 7, 13, ... , 127, 133, 139, ... камней)

Вот как-то так