Выигрышная стратегия (школьная задача)

[marie-la]

Анна и Иван играют в игру. На столе лежат конфеты. Анна ходит первой. Если во время хода игрока число конфет на столе $n\geq 2$, то он может съесть либо $[\frac{n}{2}]$ конфет, либо одну конфету. Если осталась одна конфета, игрок должен ее съесть. Проигрывает тот, кто съест последнюю конфету. В зависимости от начального числа конфет, кто имеет выигрышную стратегию?

Пыталась делать как-то по индукции. Пока только поняла, что если для $n$ у первого игрока проигрыш, то для $n+1$ у него выигрыш. Повыписывала для первых 20 чисел - между проигрышами $1,2,3$ числа бывает. Но закономерность понять не могу.

[TOTAL]

Я бы съедал как можно больше конфет. Лишь бы после моего хода противник мог скушать только одну конфету.

[12d3]

marie-la в сообщении #1618438 писал(а):

н может съесть либо $\frac{n}{2}$ конфет, либо одну конфету

А если число конфет нечетно, только одну конфету можно съесть?

[marie-la]

12d3 в сообщении #1618441 писал(а):

marie-la в сообщении #1618438 писал(а):

н может съесть либо $\frac{n}{2}$ конфет, либо одну конфету

А если число конфет нечетно, только одну конфету можно съесть?

Исправила, целая часть там.

[EUgeneUS]

marie-la в сообщении #1618443 писал(а):

Исправила, целая часть там.

Так целая часть, как Вы написали, или арифметическое округление, как Вы нарисовали?
$1.5$ как следует округлать?

[marie-la]

EUgeneUS в сообщении #1618449 писал(а):

marie-la в сообщении #1618443 писал(а):

Исправила, целая часть там.

Так целая часть, как Вы написали, или арифметическое округление, как Вы нарисовали?
$1.5$ как следует округлать?

Целая часть. Вроде всегда целую часть так обозначали в школах, только в англоязычной литературе сверху нет полосок.

[mihaild]

На всех четных первый игрок выигрывает: если все четные вплоть до $2k$ выигрышные, то на $2k+2$: если $k + 1$ проигрышное, то идем в него, если выигрышное - идем в $2k + 1$, и получим в ответ либо $k + 1$, либо $2k$, оба выигрышные.
Если же исходное число нечетное, $a \cdot 2^b + 1$ ($a$ нечетное), то, т.к. вычитать единицу нельзя (получим четное и проиграем), придется делить, переходя к $a \cdot 2^{b - 1} + 1$. Если и это число четное ($b = 1$), то исходное число проигрышное. Дальше сами

[Yadryara]

marie-la в сообщении #1618451 писал(а):

Целая часть. Вроде всегда целую часть так обозначали в школах, только в англоязычной литературе сверху нет полосок.

Ну то есть всегда пол:

$\lfloor\frac{n}{2}\rfloor$

[Null]

Посчитайте Функцию Шпрага — Гранди для маленьких $n$, а потом попробуйте ее угадать. Несмотря на звучное название и сложное описание это стандартный школьный олимпиадный метод.

[marie-la]

Null в сообщении #1618455 писал(а):

Посчитайте Функцию Шпрага — Гранди для маленьких $n$, а потом попробуйте ее угадать. Несмотря на звучное название и сложное описание это стандартный школьный олимпиадный метод.

Спасибо! Удалось угадать таки - для четных всегда первый, для нечетных в зависимости от четности степени двойки в предсталении $n-1$ как нечетного умножить на степень двойки.