РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 1964 Добавить в вариант

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

Спрятать решение

Решение.

Выигрышная стратегия есть у Пети. Например, такая: он пишет в двух последних клетках 04. Заметим, что если число кончается на 02 или 52, то его квадрат кончается на 04. Докажем, для любого Васиного хода Петя сумеет найти точный квадрат.

Пусть Вася сходил в разряд сотен. Рассмотрим квадраты чисел 2, 52, 102, 152, 202, 252, 302, 352, 402, 452. Найдём разность между двумя соседними квадратами:

$левая круглая скобка 50 a плюс 2 правая круглая скобка в квадрате =2500 a в квадрате плюс 200 a плюс 4$

$левая круглая скобка 50 a плюс 52 правая круглая скобка в квадрате =2500 a в квадрате плюс 5200 a плюс 2704,$

откуда

$левая круглая скобка 50 a плюс 52 правая круглая скобка в квадрате минус левая круглая скобка 50 a плюс 2 правая круглая скобка в квадрате =5000 a плюс 2700 \equiv 700 \bmod 1000.$

Значит, цифра сотен каждого следующего из этих чисел получается из предыдущей увеличением на 7 по модулю 10. Следовательно, цифры сотен во всех этих числах разные (0, 7, 4, 1, 8, 5, 2, 9, 6, 3). Поэтому, если Вася сходит в разряд сотен, Петя сумеет дополнить число до квадрата.

Пусть Вася сходил в разряд тысяч, то есть имеем число ******xy04, где x задано Васей. Рассмотрим ряд чисел

$левая круглая скобка 100 a плюс 2 правая круглая скобка в квадрате =10000 a плюс 400 a плюс 4,$

где $a=0,2, \ldots 24.$ В этих числах xy образуют арифметическую прогрессию с разностью 4 (04, 08, 12, ..., 96), поэтому для каждого x найдётся подходящий y.

Если Вася сходил в десятки тысяч, то рассуждения аналогичные: среди квадратов

$1|004| 004, \quad 4|008| 004, \quad 9|012| 004, \quad 16|016| 004, \quad 25|020| 004, \quad \ldots, \quad 576|096| 004$ $1|004| 004, \quad 4|008| 004, \quad 9|012| 004, \quad$
$\quad 16|016| 004, \quad 25|020| 004, \quad \ldots, \quad 576|096| 004$

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

Заметим, что квадраты соседних чисел в ряду

$2, 52, \ldots, 902, 952$

различаются менее чем на 100 000 (это следует из формулы квадрата суммы), а $952 в квадрате больше 900 000,$ поэтому цифра сотен тысяч пробегает в них все значения от 0 до 9. В ряду

$2, 52, \ldots, 2902, 2952, 3002$

квадраты соседних чисел различаются менее чем на миллион, а последний превышает 9 миллионов; значит, цифра миллионов пробегает все значения от 0 до 9.

Три старших разряда рассмотрим одновременно. В ряду

$2, 52, \ldots, 99 902, 99 952$

квадраты соседних чисел различаются менее чем на 10 миллионов, а в числе

$99 952 в квадрате =9 990 402 304$

во всех трёх старших разрядах стоят девятки. Значит, каждый из трёх старших разрядов пробегает все значения от 0 до 9.

Ответ: у Пети.

Олимпиада «Формула Единства» / «Третье тысячелетие», 10 класс, 2 тур (заключительный), 2018 год

Классификатор: Разное. Игры и стратегии

Спрятать решение · Помощь