Разделы 
Дополнительно
Задача по математике - 3385
2019-06-03 
Боря задумал целое число, большее чем 100. Кира называет целое число, большее чем 1. Если Борино число делится на это число, Кира выиграла, иначе Боря вычитает из своего числа названное, и Кира называет следующее число. Ей запрещается повторять числа, названные ранее. Если Борино число станет отрицательным, Кира проигрывает. Есть ли у нее выигрышная стратегия?
Решение:
Попробуем играть за Киру. Самый естественный первый ход - назвать число «2». Если мы не угадали, и Борино число было нечетным, то назовем «3». Если мы опять не угадали, то, по крайней мере, Борино число станет четным. К сожалению, число «2» мы уже называть не можем, поэтому будем действовать хитрее.
Чтобы понять, какие возможные Борины числа мы уже отсеяли, рассмотрим возможные остатки от деления исходного числа на 6 (6 = НОК(2, 3); см. факт 7). Если остаток был равен 0, 2 или 4, то Кира выиграла первым ходом. Если остаток был 5, то после первого хода он стал 3, и Кира выиграла вторым ходом. Таким образом, игра будет продолжаться, только если исходное Борино число давало остаток 1 или 3 при делении на 6. После двух ходов из него вычтется $2 + 3 = 5$, и остаток при делении на 6 станет 2 или 4.
Третьим ходом попробуем назвать просто следующее число - это «4». Рассмотрим возможные остатки Бориного числа перед этим ходом при делении на 12 ($12 = НОК(2, 3, 4)$). Возможные остатки при делении на 6 - это 2 или 4, значит, при делении на 12 могут получиться остатки 2, 4, 8 или 10. Игра будет продолжаться, если этот остаток равен 2 или 10 (иначе число делилось бы на 4), значит, после вычитания 4 остаток от деления на 12 станет 10 или 6.
Теперь, если мы назовем «6», то либо сразу выиграем (если остаток был 6), либо остаток от деления Бориного числа на 12 станет равным 4. Теперь Борино число де¬лится на 4, но «4» мы уже называли. Но если из числа, которое при делении на 12 дает в остатке 4, вычесть 16, то полученное число будет делиться на 12. А 12 мы еще не называли! Итак, называем 16, а потом 12 и выигрываем, так как после пятого хода Боря мог вычесть из своего числа лишь $2 + 3 + 4 + 6 + 16 = 31$, т. е. Борино число не могло стать отрицательным.
В табл. 1 представлены ходы Киры и возможные числа Бори. Посмотрим теперь на процесс игры, зная заранее, что достаточно рассматривать остатки при делении Бориного числа на 12 (табл. 2).
Каждым ходом Кира «отсеивает» некоторые остатки. Уже перед пятым ходом становится ясно, что Борино число имеет вид $12k + 4$, но приходится назвать «16», чтобы привести его к виду $12k$, а уже затем назвать «12».
Ответ: Есть.
Боря задумал целое число, большее чем 100. Кира называет целое число, большее чем 1. Если Борино число делится на это число, Кира выиграла, иначе Боря вычитает из своего числа названное, и Кира называет следующее число. Ей запрещается повторять числа, названные ранее. Если Борино число станет отрицательным, Кира проигрывает. Есть ли у нее выигрышная стратегия?
Решение:
Попробуем играть за Киру. Самый естественный первый ход - назвать число «2». Если мы не угадали, и Борино число было нечетным, то назовем «3». Если мы опять не угадали, то, по крайней мере, Борино число станет четным. К сожалению, число «2» мы уже называть не можем, поэтому будем действовать хитрее.
Чтобы понять, какие возможные Борины числа мы уже отсеяли, рассмотрим возможные остатки от деления исходного числа на 6 (6 = НОК(2, 3); см. факт 7). Если остаток был равен 0, 2 или 4, то Кира выиграла первым ходом. Если остаток был 5, то после первого хода он стал 3, и Кира выиграла вторым ходом. Таким образом, игра будет продолжаться, только если исходное Борино число давало остаток 1 или 3 при делении на 6. После двух ходов из него вычтется $2 + 3 = 5$, и остаток при делении на 6 станет 2 или 4.
Третьим ходом попробуем назвать просто следующее число - это «4». Рассмотрим возможные остатки Бориного числа перед этим ходом при делении на 12 ($12 = НОК(2, 3, 4)$). Возможные остатки при делении на 6 - это 2 или 4, значит, при делении на 12 могут получиться остатки 2, 4, 8 или 10. Игра будет продолжаться, если этот остаток равен 2 или 10 (иначе число делилось бы на 4), значит, после вычитания 4 остаток от деления на 12 станет 10 или 6.
Теперь, если мы назовем «6», то либо сразу выиграем (если остаток был 6), либо остаток от деления Бориного числа на 12 станет равным 4. Теперь Борино число де¬лится на 4, но «4» мы уже называли. Но если из числа, которое при делении на 12 дает в остатке 4, вычесть 16, то полученное число будет делиться на 12. А 12 мы еще не называли! Итак, называем 16, а потом 12 и выигрываем, так как после пятого хода Боря мог вычесть из своего числа лишь $2 + 3 + 4 + 6 + 16 = 31$, т. е. Борино число не могло стать отрицательным.
В табл. 1 представлены ходы Киры и возможные числа Бори. Посмотрим теперь на процесс игры, зная заранее, что достаточно рассматривать остатки при делении Бориного числа на 12 (табл. 2).
Каждым ходом Кира «отсеивает» некоторые остатки. Уже перед пятым ходом становится ясно, что Борино число имеет вид $12k + 4$, но приходится назвать «16», чтобы привести его к виду $12k$, а уже затем назвать «12».
Ответ: Есть.
