Игра со спичками (сама придумала)

[Xenia1996]

У Ксюши и Ани по n спичек. Ходят по очереди, начинает Ксюша. За один ход разрешается передать противнику любое натуральное число спичек (разумеется, не больше, чем у игрока есть на данный момент), если только это число ещё не было передано одним из игроков. Проигрывает тот, кто не может сделать ход.
Указать выигрышную стратегию для каждого натурального n.

[ewert]

(Оффтоп)

извините за явную неполиткорректность (со всех точек зрения), но первое решение, пришедшее в голову: детям -- со спичками лучше всё-таки не играть...

[Xenia1996]

ewert в сообщении #471881 писал(а):

(Оффтоп)

извините за явную неполиткорректность (со всех точек зрения), но первое решение, пришедшее в голову: детям -- со спичками лучше всё-таки не играть...

(Оффтоп)

А мы перед игрой у всех спичек головки пооткусывали, так что всё зашибись

Условие задачи понятно?
А то ведь сама придумывала, вдруг что не ясно.
Лично я нашла целых два способа решения.
И задача на самом деле лёгкая, если правильно понять условие.

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

[Naf2000]

Не очень просто как-то получилось

(Оффтоп)

Второй выигрывает всегда. Его тактика:
Если первый передает 2k, то второй передает обратно 2k-1, если первый 2k-1, то второй 2k.
То есть все ходы разбиваются по парам чисел (2k,2k-1), единственная проблема - всегда ли второй может походить?
Это может случиться только в следующем случае: ему передали 2k-1, а он должен вернуть 2k. Когда он не сможет этого сделать? Когда у него до того как принял 2k-1 количество 0. Покажем, что такого быть не может при данной стратегии.
За каждую пару ходов количество у второго игрока изменяется ровно на 1 (увеличиваясь или уменьшаясь). Первоначально было N, стало 0. Значит прошло минимум N пар ходов, то есть использовано 2N разных ходов, но их всего 2N, игра окончена после хода второго и первому попросту нечем ходить.

[Xenia1996]

Naf2000 в сообщении #471963 писал(а):

Не очень просто как-то получилось

(Оффтоп)

Второй выигрывает всегда. Его тактика:
Если первый передает 2k, то второй передает обратно 2k-1, если первый 2k-1, то второй 2k.
То есть все ходы разбиваются по парам чисел (2k,2k-1), единственная проблема - всегда ли второй может походить?
Это может случиться только в следующем случае: ему передали 2k-1, а он должен вернуть 2k. Когда он не сможет этого сделать? Когда у него до того как принял 2k-1 количество 0. Покажем, что такого быть не может при данной стратегии.
За каждую пару ходов количество у второго игрока изменяется ровно на 1 (увеличиваясь или уменьшаясь). Первоначально было N, стало 0. Значит прошло минимум N пар ходов, то есть использовано 2N разных ходов, но их всего 2N, игра окончена после хода второго и первому попросту нечем ходить.

Как раз очень даже просто. Есть ещё одно решение:
Победит второй игрок, придерживаясь правила: "всякий раз отдавай минимально возможное число спичек".