Дано 100 спичек. За ход разрешается брать любое количество спичек, которое является степенью простого числа (в т.ч. 1 или простое число). Проигрывает тот, у кого нет хода. Найдите наименьшее число спичек, которое нужно взять первому, чтобы выиграть. Если вы считаете, что выигрывает второй, то поставьте в качестве ответа 0.

Проигрышными здесь будут все числа, кратные 6. В самом деле, всегда можно взять от 1 до 5 спичек, и если число спичек не было кратно 6, то за ход всегда можно получить число, кратное 6. С другой стороны, если число спичек кратно 6, то из этой кучи мы не сможем получить кучу, в которой число спичек кратно 6 (т.к. для этого придётся убрать $6k$ спичек, а это число не является степенью простого). Значит, позиции $6k$ проигрышные, остальные выигрышные. Следовательно, из кучи 100 спичек можно удалить 4 спички (но нельзя меньше), чтобы получить проигрышную позицию.

Дано число 96. За ход число $x$ на доске можно заменить на любое число, меньшее $x$ и не являющееся его делителем. Проигрывает тот, у кого нет хода (т. е. получивший 2 выигрывает). Какое число нужно написать первому игроку, чтобы выиграть? Перечислите все варианты. Если вы считаете, что выигрывает второй, напишите 0.

Докажем, что степени двойки являются проигрышными числами, а остальные выигрышными. В самом деле, сама двойка, очевидно, является проигрышной. Далее, из степени двойки можно получить только число, степенью двойки не являющееся (все меньшие степени двойки - делители большей степени двойки). С другой стороны, из числа, не являющегося степенью двойки, всегда можно получить ближайшую степень двойки (потому что если $2^n<x<2^{n+1}$, то $x$ не делится на $2^n$).

Итак, число 96 выигрышное, и для выигрыша нам необходимо заменить его на степень двойки, на которую не делится число 96. Таких степеней только две: 32 и 64.

Дано число 128. За ход из числа можно вычесть любой его делитель, отличный от самого числа, но с одним ограничением: игрок не может вычесть нечётный делитель, если по правилам возможно вычесть чётный (тем самым из 2 можно вычесть 1, а из 4 --- нельзя). Проигрывает тот, у кого нет хода (т. е. получивший 1 выигрывает). Перечислите все варианты. Если вы считаете, что выигрывает второй, напишите 0.

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

Докажем, что распределение чисел на выигрышные и проигрышные именно такое. Пусть мы уже знаем распределение чисел до $4k$. Тогда число $4k+2$ проигрышное, т.е. из него можно вычесть только чётный делитель. Этот делитель будет давать остаток 2 по модулю 4 (т.к. само число не кратно 4), и разность будет делиться на 4 и не равна 4 (т.е. разность будет выигрышной). Из чисел $4k+3$ и $4k+4$ можно за один ход получить проигрышное число $4k+2$, поэтому такие числа выигрышные. Так как число 128 делится на 4, то из него нужно вычесть делитель, чтобы получить число с остатком 2 по модулю 4. Единственным таким делителем является двойка.

Замечание. Эта задача интересна тем, что в ней не нужно приводить полный анализ выигрышных и проигрышных позиций: числа вида $4k+1$ можно оставить неизвесными (не выигрышными и не проигрышными). Но можно и заметить, что если у такого число есть делитель вида $4x+3$, то можно вычесть этот делитель и попасть в проигрышную позицию (т.е. такое число выигрышное), а если такого делителя нет, то мы следующим ходом попадаем в число, кратное 4 (и не равное 4, т.е. в выигрышное).

Дано число 100. За ход из числа можно вычесть любой его делитель, отличный от самого числа. Проигрывает тот, у кого нет хода (т. е. получивший 1 выигрывает). Какой делитель нужно вычесть, чтобы выиграть? Перечислите все варианты. Если вы считаете, что выигрывает второй, напишите 0.

Чётные числа являются выигрышными, нечётные - проигрышными. В самом деле, число 1 проигрышное, а 2 выигрышное. Из нечётных чисел вычитанием делителя можно получить только чётное число, а из чётного можно, например, вычесть 1, и получить нечётное. Поэтомк распределение исел на выигрышные и проигрышные совпадает с распреелением на чётные и нечётные. Из числа 100 нужно получить нечётное число, т.е. нужно вычесть нечётный делитель. Все такие ходы - 1, 5 или 25.

Имеется куча из 100 камней. Петя и Вася ходят по очереди (начинает Петя). За один ход можно взять 1, 3, 4 или 5 камней. Проигрывает тот, кто не может сделать ход. Сколько камней нужно взять Пете первым ходом, чтобы выиграть? Если вы считаете, что выигрышная позиция есть у Васи, то напишите 0.

Проигрышными являются числа (количества камней), дающие остаток 0 или 2 по модулю 8, остальные числа являются выигрышными. В самом деле, если в куче 0 или 2 камня, то начинающий проиграл ещё до начала игры. Числа 1, 3, 4, 5, 6 и 7 являются выигрыщными (в один ход). Далее можно заметить, что из чисел, кратным 8, можно получить только числа с остатком 7, 5, 4 или 3 по модулю 8, а из чисел с остатком 2 по модулю 8 - только числа с остатками 1, 7, 6 или 5. Из остальных же чисел можно получить число, кратное 8 или дающее остаток 2 по модулю 8 (из 1, 3, 4 и 5 можно сделать 0, из 6, и 7 - 2). Таким образом, мы расставили выигрышные и проигрышные позиции. Число 100 даёт остаток 4 по модулю 8, поэтому единственный выигрышный ход - взять 2 камня (тогда Вася будет стартовать с проигрышного числа 98).

На пляже есть куча из 50 камней. За ход можно взять один или несколько камней, но не более трети кучи. Проигрывает тот, кто не может походить (т. е. перед его ходом осталось два камня). Сколько камней необходимо взять первому для выигрыша? Если вы считаете, что выиграет второй, напишите 0.

Число 2 является проигрышным, т.к. если осталось 2 камня, то начинающий уже проиграл. Число 3, соответственно, выигрышное. Число 4 проигрышное, числа 5 и 6 выигрышные (из куч 5 или 6 камней можно сделать куча 4 камня). Продолжая далее, получаем, что 7 - проигрышное число, от 8 до 10 - выигрышные, 11 - проигрышное, от 12 до 16 выигрышные, 17 проигрышное, от 18 до 25 выигрышные, 26 проигрышное, от 27 до 39 выигрышные, 40 проигрышное, от 51 до 59 выигрышные. Итак, число 50 является выигрышным, и единственный выигрышный ход - взять 10 камней. Совсем простой закономерности распределения проигрышных чисел в данной задаче нет (хотя ясно, что каждая следующее проигрышное число примерно в полтора раза больше предыдущего).

На доске написано число. Петя и Вася ходят по очереди. За ход можно вычесть из числа любую ненулевую цифру, содержащуюся в данном числе (после хода цифры в числе меняются, и возможности у соперника могут быть другими!) Проигрывает тот, кто не может сделать ход. Изначально есть число 123456789. Какую цифру необходимо вычесть первому, чтобы выиграть? Если вы считаете, что выигрышная стратегия есть у второго, напишите 0.

Анализ игры показывает, что проигрышными являются позиции, в которых число оканчивается на 0. В самом деле, в конце игры образуется число 0, и оно является проигрышным. Из числа, не оканчивающегося на 0, всегда можно вычесть последнюю цифру (и тогда оно станет оканчиваться на 0), а из числа, оканчивающегося на 0, любым возможным ходом получается число, которое на 0 не оканчивается. Таким образом, стратегия игрока - вычитать последнюю цифру (если она не равна 0).

Имеется куча из 12345 камней. Петя и Вася ходят по очереди (начинает Петя). За один ход можно взять 5, 6, 7, 8, 9 или 10 камней. Проигрывает тот, кто не может сделать ход. Сколько камней нужно взять Пете первым ходом, чтобы выиграть? Если вы считаете, что выигрышная позиция есть у Васи, то напишите 0.

Из этой позиции выиграет Вася. Проигрышными являются позиции, в которых число камней даёт остаток 0, 1, 2, 3 или 4 по модулю 15. В самом деле, если в куче осталось 0, 1, 2, 3 или 4 камня, то начинающий протгрывает сразу. Если в куче от 5 до 14 камней, то начинающий выигрывает. Любой ход можно дополнить таким ходом, чтобы в паре ходов в сумме было взято 15 камней. Поэтому если позиция x проигрышная, то и x+15 тоже проигрышная, поэтому все позиции, дающие остатки 0, 1, 2, 3 или 4 по модулю 15 - проигрышные. Но с любой другой позиции есть ход в одну из проигрышных.

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

Вся вертикаль Н (т.е. восьмая), очевидно, проигрышная (с этих клеток нельзя ходить). Тогда все клетки, с которых можно походить на восьмую горизонталь (это диагональ от А1 до H8 и всё, что выше, а также диагональ от А8 до Н1 и всё, что ниже) - выигрышные. Значит, клетки C4 и C5 проигрышные (и них можно попасть только на выигрышные). Все клетки, с которых можно попасть на C4 или C5, выигрышные. Остались лишь две клетки - А4 и А5, которые являются проигрышными.

Петя и Вася по очереди передвигают ладью. за ход её можно переместить на любое количество полей вверх или вправо. Проигрывает тот, кто поставит ладью на поле Н8. Перечислите, какие из позиций являются проигрышными: С2, С3, С4, D4, D5, D6. G3, G6, G7.

Поля H7 и G8 проигрышные (единственный возможный ход с этих полей ведёт к проигрышу). Остальные поля седьмой и восьмой горизонталей и вертикалей выигрышные (с них можно попасть на одну из этих двух клеток). Соответственно, поле F6 проигрышное (с него можно попасть только на выигрышные поля).  Далее очевидно, что поля на диагонали (т.е. А1, В2, С3, D4, E5 и F6) проигрышные, а остальные поля - выигрышные (потому что с проигрышных полей можно попасть только на выигрышные, а с любого выигрышного поля есть ход на проигрышное).

Петя и Вася по очереди перемещают короля на шахматной доске. За один ход можно переместить его на одну клетку вверх, вправо или по диагонали вверх-вправо. Проигрывает тот, кто не может сделать ход. Какие из перечисленных позиций являются проигрышными? B2, B3, B4, C4, C5, D5, D6, D7.

Проигрышные позиции находятся на пересечении чётных горизонталей и чётных вертикалей. В самом деле, поле Н8, очевидно,проигрышное. Далее, пусть у нас есть клетка Х, а все клетки не ниже и не левее мы уже разделили на выигрышные и проигрышные. Если Х имеет хотя бы одну нечётную координату, то мы можем увеличить на 1 нечётные координаты и прийти в клетку с чётными координатами (которая является проигрышной по нашему предположению). Значит, Х выигрышная. Если же Х имеет обе чётные координаты, то любым ходом мы вынуждены изменить чётность хотя бы одной из координат и встать на выигрышную позицию. Поскольку любой ход ведёт с Х на выигрышную позицию, то такая клетка является проигрышной.

Петя и Вася по очереди передвигают ладью. за ход её можно переместить на любое количество полей вверх или вправо. Проигрывает тот, кто не может сделать ход. Перечислите, какие из позиций являются проигрышными: С2, С3, С4, D4, D5, D6. G3, G6, G7.

Проигрышными являются позиции на диагонали (А1, В2, С3 и т.д.), выигрышными - все остальные. В самом деле, клетка Н8 проигрышная (стартующий с неё уже проиграл); с диагональых леток (проигрышных) можно походить исключительно на недиагональные; из недиагональной клетки существует ход на диагональную.

Пусть есть некоторая игра (играют Петя и Вася, делают ходы по очереди, начинает Петя). Пусть мы уже играем в эту игру (неважно, на стороне Пети или Васи), перед нами некоторая позиция, и сейчас наш ход. Если мы можем походить, чтобы в итоге выиграть, то такая позиция будет называться выигрышной (в дальнейшем решении будем называть её В). Если же все ходы приводят к нашему проигрышу при правильных ходах соперника, то такую позицию будем называть проигрышной (П). Какие утверждения являются верными? Перечислите пункты без пробелов.

а) Из выигрышной позиции можно попадать только на проигрышные,

б) Из проигрышной позиции можно попадать только на выигрышные,

в) Из выигрышной позиции существует хотя бы один ход на проигрышную,

г) Из выигрышной позиции существует ровно один ход на проигрышную,

д) Из проигрышной позиции существует ровно один ход на выигрышную,

е) Из выигрышных позиций можно попадать только на выигрышные, а из проигрышных - только на проигрышные.

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

Перед Петей и Васей есть две кучи, по 100 конфет в каждой. Они делают ходы по очереди, начинает Петя. За один ход можно взять любое число конфет, но из одной кучи. Прогрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?

Заполните пропуски в решении задачи.
Выиграет __. Пусть мы уже играем в эту игру (неважно, на стороне Пети или Васи), перед нами две кучи из $k$ и $n$ конфет, и сейчас наш ход. Если мы можем походить, чтобы в итоге выиграть, то такая позиция будет называться выигрышной (в дальнейшем решении будем называть её В). Если же все ходы приводят к нашему проигрышу при правильных ходах соперника, то такую позицию будем называть проигрышной (П).

Позиция (0,0) (когда конфет не осталось ни в одной из кучек, и сейчас наш ход), очевидно, __. Позиции $(0,k)$ и $(k,0)$ - __ (потому что можно сделать ход и перейти в позицию (0,0)). Позиция (1,1) - __ (потому что из неё можно получить лишь позиции (0,1) или (1,0)). Позиции $(1,k)$ и $(k,1)$ при $k>1 - __ (из них можно получить позицию (1,1)). Продолжая далее, заметим, что позиции $(n,k) с равными $n$ и $k$ - __, а с неравными $n$ и $k$ - __. Так как (100,100) - позиция с равным количеством конфет в долях, то выиграет __.

Перед Петей и Васей есть куча из 100 конфет. Они делают ходы по очереди, начинает Петя. За один ход можно взять от 1 до 5 конфет. Прогрывает тот, кто съест последнюю конфету. Кто выиграет при правильной игре?

Заполните пропуски в решении задачи.
Выиграет __. Пусть мы уже играем в эту игру (неважно, на стороне Пети или Васи), перед нами куча из n конфет, и сейчас наш ход. Если мы можем походить, чтобы в итоге выиграть, то такая позиция будет называться выигрышной (в дальнейшем решении будем называть её В). Если же все ходы приводят к нашему проигрышу при правильных ходах соперника, то такую позицию будем называть проигрышной (П).

Позиция 1 (когда осталась 1 конфета, и сейчас наш ход), очевидно, __. Позиции от 2 до 6 - __ (потому что можно сделать ход и перейти в позицию 1). Позиция 7 - __ (потому что из неё можно получить лишь позиции от 2 до 6). Позиции 8-12 - __ (из них можно получить позицию 7). Продолжая далее, заметим, что позиции, дающие остаток 1 при делении на 6 - __, а дающие все остальные остатки при делении на 6 - __. Так как 100 не даёт остаток 1 при делении на 6, то выиграет __, ему нужно для выигрыша взять __ конфет(-ы или -у).

Перед Петей и Васей есть куча из 100 конфет. Они делают ходы по очереди, начинает Петя. За один ход можно взять от 1 до 5 конфет. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Заполните пропуски в решении задачи.
Выиграет __. Пусть мы уже играем в эту игру (неважно, на стороне Пети или Васи), перед нами куча из n конфет, и сейчас наш ход. Если мы можем походить, чтобы в итоге выиграть, то такая позиция будет называться выигрышной (в дальнейшем решении будем называть её В). Если же все ходы приводят к нашему проигрышу при правильных ходах соперника, то такую позицию будем называть проигрышной (П).

Позиция 0 (когда осталось 0 конфет, и сейчас наш ход), очевидно, __. Позиции от 1 до 5 - __ (потому что можно сделать ход и перейти в позицию 0). Позиция 6 - __ (потому что из неё можно получить лишь позиции от 1 до 5). Позиции 7-11 - __ (из них можно получить позицию 6). Продолжая далее, заметим, что позиции, кратные 6 - __, а не кратные 6 - __. Так как 100 не кратно 6, то выиграет __, ему нужно для выигрыша взять __ конфет(-ы или -у).

Ладья стоит на поле А1 шахматной доски. Петя и Вася по очереди перемещают эту ладью. Начинает Петя, за ход можно переместить ладью на любое количество клеток вверх или вправо. Проигрывает тот, кто не может сделать ход. Петя переместил ладью на А7. Какой ход должен сделать Вася для выигрыша?

После такого хода Петя сможет походить либо на G8 (с последующим ходом на Н8), либо на Н7 (также с последующим ходом Васи на Н8). В любом случае Вася выигрывает. Все остальные ходы являются проигрышными для Васи.

На столе лежат две кучи по 10 конфет. Петя и Вася по очереди берут конфеты. Начинает Петя. За один ход можно взять сколько угодно конфет, но только из одной кучи. Проиграет тот, кто не сможет сделать ход. Петя первым делом взял 9 конфет из первой кучи. Как должен действовать Вася, чтобы победить? Он должен взять __ конфет из __ кучи.

Если Вася возьмёт 9 конфет из второй куче, то в каждой куче останется по одной конфете.  За один ход из этой позиции выиграть (для этого нужно есть сразу из двух куч, что запрещено),а за два хода игра гарантированно закончится (за каждый ход нужно что-нибудь взять). Значит, Вася выиграет.

Это единственный ход, выигрышный для Васи. (Почему?)

Ферзь стоит на клетке А2 шахматной доски. Петя и Вася по очереди могут передвигать его на любое количество клеток, но только в трёх направлениях - вправо, вверх или по диагонали вправо-вверх. Начинает Петя. Если кто-то не может сделать ход согласно правилам, то он проигрывает. Какой ход нужно сделать Пете, чтобы точно выиграть после второго своего хода?

Выигрывает тот, кто сможет поставить ферзя на поле H8. Петя должен походить по диагонали на F7. Тогда Вася следующим ходом сможет загнать ферзя на какую-нибдь клетку, соседнюю с Н8, но не на саму Н8. Следующим ходом Петя гарантированно выиграет.

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