На доске написаны числа 1, 2, 3, ..., 2025. Александр и Борис по очереди стирают по одному числу, пока на доске не останется только два числа. Начинает Александр. Если одно из оставшихся чисел делится на второе, то побеждает Александр, если нет – Борис. Кто побеждает при правильной игре?
Первым ходом Александр стирает число 2025
Ответ: побеждает Александр Покажем, что, если после очередного хода Александра остается $2N$ чисел, то он сможет образовать $N$ пар $(k, mk)$, в каждой паре второе число делится на первое, причем каждое число входит не более чем в две пары и в этом случае один раз в качестве делителя и один раз в качестве делимого. Первым ходом Александр стирает число 2025 Затем он образует пары чисел (1;2), (2;4), (3;6), ... $(k;2k)$, ... (1012, 2024). Всего 2024 числа, 1012 пар, причем каждое число входит не более чем в две пары. Пусть после очередного хода Александра осталось $2N$ чисел, он смог образовать $N$ пар $(k, mk)$, в каждой паре второе число делится на первое, причем каждое число входит не более чем в две пары. У Бориса есть три возможности: – стереть число, которое не входит ни в одну пару; – стереть число, которое входит в одну пару (тем самым разрушить одну пару); – стереть число, которое входит в две пары. Если Борис стирает число, которое не входит ни в одну пару, то Александр стирает самое большое число в парах (оно входит только в одну пару) и остается $2N-2$ чисел и $N-1$ пар, причем каждое число входит не более чем в две пары. Если Борис стирает число, которое входит в одну пару и тем самым разрушает эту пару, то остается $N-1$ пара, $2N-1$ чисел и Александр может стереть число, которое не входит ни в одну пару. После хода Александра остается $2N-2$ чисел и $N-1$ пар, причем каждое число входит не более чем в две пары. Если Борис стирает число, которое входит в две пары, он разрушает пары $(k,km)$ и $(n,np)$, причем $n=km$. Тогда Александр организует пару $(k,np)=(k,kmp)$, в которой по-прежнему второе число делится на первое. Имеется $N-1$ пар, $2N-1$ чисел и Александр может стереть число, которое не входит ни в одну пару. После хода Александра остается $2N-2$ чисел и $N-1$ пар, причем каждое число входит не более чем в две пары. В соответствии с алгоритмом, когда останется два числа, Александр сможет обеспечить, что это будет пара $(k, mk)$, в которой одно число делится на другое
