Задача 166. Игра в «Числа»-I
Числа от 1 до 20 выписаны в строчку. Двое игроков играют в следующую игру. Они по очереди расставляют между ними плюсы и минусы. После того, как все места заполнены, подсчитывается результат. Если он четен, то выигрывает первый игрок, если нечетен, то второй. Кто может выиграть, как бы ни играл другой?
Ответ:
Первый
Решение:
Это игра-шутка. Чётность результата не зависит от расстановки плюсов и минусов, а зависит только от количества нечётных чисел в первоначальном наборе. Так как в данном случае их 10 (то есть чётное число), то выигрывает первый игрок.
Задача 167. Игра в «Числа»-II
На доске написаны числа 35 и 36. За ход разрешается дописать еще одно натуральное число — разность любых двух имеющихся на доске чисел, если она еще не встречалась. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре: начинающий игру или его партнер?
Ответ:
Второй
Решение:
В процессе игры на доске может появиться любое число от 1 до 34 с помощью единицы, которая появляется после первого хода. Так как 34 четное, то выпишет последнее число именно второй, он и победит.
Задача 168. Игра в «Числа»-III
Вначале на доске написано число 1000000. Андрей за ход должен уменьшить его, разделив нацело на нечетное число от 2 до 100, Борис — на четное от 2 до 10. Проигрывает тот, кто не сможет ходить. Кто из них выиграет при правильной игре?
Решение:
Заметим, что 1000000=2^6×5^6, то есть Андрей может делить только на 5 или 5^2, а Борис — только на 2, 2^2, 2^3 или 2×5. То есть Андрей проигрывает, когда заканчиваются все 6 пятерок, а Борис — когда заканчиваются все 6 двоек. Причем Андрей может забирать только свои пятерки, а Борис может забирать как двойки, так и пятерки. Значит, Борис может быстрее приблизить Андрея к проигрышу, когда будет забирать его пятерки. Действительно, если каждым ходом Борис будет делить число на 10 (пока делится, то есть пока еще есть пятерки), то не более, чем через 3 хода Андрея и 3 хода Бориса пятерок не останется (но двоек будет хотя бы 3, так как забирает их только Борис), значит, Андрей не сможет походить, а Борис выиграет.
Ответ:
Борис
Задача 169. Игра в «Числа»-IV
Двое играют в следующую игру. Каждый игрок по очереди вычеркивает 9 чисел (по своему выбору) из последовательности 1, 2, …, 100, 101. После одиннадцати таких вычеркиваний останутся 2 числа. Первому игроку присуждается столько очков, какова разница между этими оставшимися числами. Докажите, что первый игрок всегда сможет набрать по крайней мере 55 очков, как бы ни играл второй.
Подсказка 1
Есть ли какие-то числа из последовательности 1, 2, ..., 101, которые заведомо не могли быть среди 2 последних, если их разница ≥55?
Подсказка 2
Числа 47, 48, ..., 55 не могут ни с каким другим из 1, 2, ..., 101 давать разницу ≥55. Разумно стереть их первым ходом первого игрока. Что делать дальше?
Подсказка 3
Вспомним про стандартные стратегии: симметрию и дополнение. Стоит попробовать разбить оставшиеся числа на пары каким-то образом.
Подсказка 4
Разобьем оставшиеся после хода первого числа на пары 1-56, 2-57, ..., 46-101. Разница чисел в паре равна 55. Как бы теперь ходить первому игроку, чтоб разница 2 чисел в конце ≥55?
Решение:
Пусть первым ходом первый вычеркнет 9 чисел от 47 до 55. Тогда остальные числа разбиваются на пары с разностью 55: 1-56, 2-57, …, 46-101. После каждого хода второго игрока, первый может вычеркнуть числа таким образом, чтобы в каждой паре было вычеркнуто либо оба числа, либо ни одного (довычеркивает числа из неполных пар — их нечетное количество, не больше 9 и вычеркивает еще несколько пар полностью). Таким образом, в конце останется пара чисел, разность которых равна 55.
Задача 170. Игра в «Числа»-V
На столе лежат 18 карточек, пронумерованных числами от 1 до 18. Андрей и Борис по очереди берут по одной карточке, пока не заберут все. Начинает Андрей. Борис будет счастлив, если в конце сумма чисел на его карточках окажется составным числом. Может ли Андрей помешать Борису быть счастливым?
Подсказка 1
Что такое составное число? Это число, которое имеет делитель, отличный от 1 и самого числа! Как тогда Борис может пытаться сделать сумму составным числом? Правильно - добиться делимости на какое-то другое число:)
Подсказка 2
Рядом с делимостью за ручку идут остатки. Борису стоит обратить внимание на остатки при делении на какое-то p.
Подсказка 3
Что если взять такое нечетное p, чтобы сумма чисел от 1 до 18 делилась на него? И вспомним про всеми любимую стратегию: симметрию! Можно ли теперь простым способом сделать сумму чисел Бориса, кратной p?
Подсказка 4
Борис мог бы брать числа с такими же остатками при делении на p, что и Андрей. Если сумма чисел делится от 1 до 18 делится на p, а число Андрея и Бориса имеют одинаковый остаток при делении на нечетное число p, то эти остатки должны быть 0! Ура, Борис получил делимость на p! Тогда сумма чисел на карточка почти наверняка составная. Осталось подобрать p
Подсказка 5
Возьмем p = 3. Сумма чисел от 1 до 18 делится на 3. Дело за малым: проверить, почему Борис всегда сможет взять число, дающее тот же остаток при делении на 3, что и у Андрей?
Решение:
Будем играть за Бориса. Всегда будем брать число, дающее тот же остаток при делении на 3 что и число, взятое Андреем на предыдущем шаге. Каждый остаток при делении на 3 встречается ровно 6 раз, поэтому мы всегда сможем сделать ход. Заметим, что сумма всех чисел от 1 до 18 делится на 3, а две полученных суммы дают одинаковый остаток при делении на 3 поэтому на самом деле они обе делятся на 3. Значит, наша сумма будет составным числом.
Ответ:
Не может.