Выберите серию
Длина красной ломанной равна 8.
А чему равна длина синей ломанной?
Ответ:
Варианты ответов:
Ответ:
Варианты ответов:
Дано 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, т.е. в выигрышное).