-- Задачка - помогите решить [пожалуйста]

[Elsa]

в общем задача -
На столе лежит некоторое количество спичек. Два игрока по очереди убирают со стола от 1 до 3х спичек за раз. Проигрывает тот,который вынужден забрать последнюю спичку. Придумать выигрышную стратегию игроков.


мысли конечно есть, но оформить не могу что то

Помогите

[Miker]

Для начала, надо оставить противнику ровно 1 спичку)

[Miker]

Играешь хоть как до 5 спичек.

Когда остаётся ровно 5 в твой ход - ты проиграл по-любому, сколько не убирай.

Если осталось меньше 5 в твой ход - убираешь все кроме одной, противник вынужден убрать последнюю, you win)

[m@verick]

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

[Elsa]

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

вот вот, лень шевелить мне )) брату надо..гг

[Miker]

мля, походу не годится моя стратегия, да?) Добиться, чтобы в твой ход осталось меньше 5, но больше одной спички)

[pref]

1. Если кол-во спичек 1 -- выиграл второй: очевидно.
2. Если кол-во спичек 2 -- выиграл первый: убираем одну и второй игрок в сутации (1).
3. Если кол-во спичек 3 -- выиграл первый: убираем две и второй игрок в ситуации (1).
4. Если кол-во спичек 4 -- выиграл первый: убираем три и второй игрок в ситуации (1).
5. Если количество спичек 5 -- выиграл второй: убирая от одной до трех мы помещаем второго игрока в ситуацию (4)-(2) соответственно.
...

База индукции - (1).
Предположение.
N. Если количество спичек N -- выиграл второй, если N делится на 4 с остатком 1, иначе первый.

Утверждение.
N+1: Если количество спичек N+1 -- выиграл второй, если N+1 делится на 4 с остатком 1, иначе первый.

Действительно, допустим, N+1 делится на 4 с остатком 1, тогда первый игрок забирая от 1 до 3х спичек оставляет перед вторым игроком от N-2 до N спичек, но N-2, N-1, N дают в остатке от деления на 4 соответственно 2, 3, 0, а, значит, по предположению индукции в них побеждает игрок делающих первый ход, т.е. в нашем случае второй. Аналогично, если N+1 дает при делении на 4 остаток 0, 2 или 3, то игроку, делающему ход надо забрать соответственно 3, 2 или 1 спичку, оставив тем самым второму игроку число спичек, делящееся на 4 с остатком 1. В этой ситуации по предположению индукции побеждает игрок, делающий второй ход, т.е. в нашем случае первый игрок. Согласно принципу полной математической индукции утверждение доказано.

[Elsa]

вай дорогой, если правильно - с меня сок

[<[Switch]>]

1. Если кол-во спичек 1 -- выиграл второй: очевидно.
2. Если кол-во спичек 2 -- выиграл первый: убираем одну и второй игрок в сутации (1).
3. Если кол-во спичек 3 -- выиграл первый: убираем две и второй игрок в ситуации (1).
4. Если кол-во спичек 4 -- выиграл первый: убираем три и второй игрок в ситуации (1).
5. Если количество спичек 5 -- выиграл второй: убирая от одной до трех мы помещаем второго игрока в ситуацию (4)-(2) соответственно.
...

База индукции - (1).
Предположение.
N. Если количество спичек N -- выиграл второй, если N делится на 4 с остатком 1, иначе первый.

Утверждение.
N+1: Если количество спичек N+1 -- выиграл второй, если N+1 делится на 4 с остатком 1, иначе первый.

Действительно, допустим, N+1 делится на 4 с остатком 1, тогда первый игрок забирая от 1 до 3х спичек оставляет перед вторым игроком от N-2 до N спичек, но N-2, N-1, N дают в остатке от деления на 4 соответственно 2, 3, 0, а, значит, по предположению индукции в них побеждает игрок делающих первый ход, т.е. в нашем случае второй. Аналогично, если N+1 дает при делении на 4 остаток 0, 2 или 3, то игроку, делающему ход надо забрать соответственно 3, 2 или 1 спичку, оставив тем самым второму игроку число спичек, делящееся на 4 с остатком 1. В этой ситуации по предположению индукции побеждает игрок, делающий второй ход, т.е. в нашем случае первый игрок. Согласно принципу полной математической индукции утверждение доказано.

:o :o :o КЭП нервно курит в сторонке! Как все элементарно:) я гуманитарий, так просто офигеваю:)