Задача
Паша выбрал 2017 (не обязательно различных) натуральных чисел a1, a2, ..., a2017 и играет сам с собой в следующую игру. Изначально у него есть неограниченный запас камней и 2017 больших пустых коробок. За один ход Паша добавляет в любую коробку (по своему выбору) a1 камней, в любую из оставшихся коробок (по своему выбору) – a2 камней, ..., наконец, в оставшуюся коробку – a2017 камней. Пашина цель – добиться того, чтобы после некоторого хода во всех коробках стало поровну камней. Мог ли он выбрать числа так, чтобы цели можно было добиться за 43 хода, но нельзя – за меньшее ненулевое число ходов?
Решение
2017 = 43·46 + 39. Пусть среди Пашиных чисел будут 39 двоек, 46 чисел, равных 44, а остальные – единицы.
Чтобы добиться требуемого за 43 хода, Паша выбирает 39 коробок, в которые он всегда кладёт по 2 камня – через 43 хода в них окажется по 43·2 = 86 камней. Остальные коробки он разбивает на 43 группы по 46 коробок; на i-м ходу он кладёт по 44 камня во все коробки i-й группы и по одному камню – в коробки остальных групп. Тогда через 43 хода в каждой коробке каждой группы будет по 44 + 42·1 = 86 камней, то есть во всех коробках будет поровну камней.
Пусть Паша сделал k < 43 ходов. Тогда в какую-то коробку A попало 44 камня за один ход, и в ней будет не меньше, чем 44 + (k – 1)·1 = 43 + k камней. С другой стороны, поскольку 46k < 2017, в какую-то коробку B ни на одном из ходов не попадёт 44 камня, то есть в ней будет не больше 2k камней. Поскольку k < 43, то 2k < k + 43, а значит, в коробке B меньше камней, чем в A. Таким образом, Паша ещё не добился требуемого.
Ответ
Мог.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь