Решение
Найдем наименьший номер страницы N, на которой будут записаны все числа множества
где
– простое число. Покажем, что на новой странице различных чисел будет записано по крайней мере на одно больше, чем на предыдущей. Докажем это утверждение методом от противного.
Пусть А – множество различных чисел, полученных на данный момент:
Далее Дима выбрал два различных числа
и прибавил их ко всем числам множества А, но количество сумм в результате не увеличилось. То есть, прибавив к числам из множества А сначала число
, а затем число
, он получил один и тот же набор сумм:
где
– остаток от деления числа m на число p. Следовательно, для любого
существует такой
, что
Другими словами, верно, что для любого
Значит, для любого
и для всех
верно, что
Но для таких k числа вида
между собой различны. (Действительно, пусть числа
и
совпадают. Значит, разность
делится на p, а следовательно, на p делится произведение
что невозможно, так как каждый сомножитель по абсолютной величине не превосходит
а число p – простое.) Получается, что множество А уже содержит p чисел, что противоречит (1).
Итак, доказано, что каждый раз количество различных чисел увеличивается по крайней мере на 1. Значит, самое позднее на странице с номером
будут записаны все p чисел. Эта оценка достижима: если каждый раз выбирать числа 0 и 1, то все числа впервые будут записаны именно на странице с номером
и не раньше. Следовательно, искомое N равно
Чтобы для получения всех чисел Дима заполнял в тетради максимальное (равное
) количество страниц, ему следует выбирать числа так, чтоб количество новых различных сумм увеличивалось каждый раз ровно на 1. Для этого необходимо и достаточно, чтобы полученные на каждом шаге различные числа образовывали арифметическую прогрессию, то есть
где d – произвольное заранее выбранное число от 1 до
а новые числа
и
надо выбирать так, чтобы
Достаточность очевидна. Необходимость легко доказать по индукции. Действительно, пусть сперва Дима выбрал числа
и
Положим
Затем он выбрал числа
и
и, в результате, получил суммы
Из этих сумм две должны совпадать. Значит, или
или
В обоих случаях
Нетрудно заметить, что получившиеся в результате три новые суммы образуют арифметическую прогрессию. Пусть теперь на m-том шаге получены суммы
образующие арифметическую прогрессию с разностью d. Прибавляя к ней новые числа
и
мы "сдвигаем" всю прогрессию вправо на
и
позиций, и если
то количество новых различных сумм увеличится более чем на 1. Значит,
и новые суммы опять образуют арифметическую прогрессию с той же разностью. Необходимость доказана.