Решение
Найдем наименьший номер страницы N, на которой будут записаны все числа множества

где

– простое число. Покажем, что на новой странице различных чисел будет записано по крайней мере на одно больше, чем на предыдущей. Докажем это утверждение методом от противного.
Пусть А – множество различных чисел, полученных на данный момент:
Далее Дима выбрал два различных числа

и прибавил их ко всем числам множества А, но количество сумм в результате не увеличилось. То есть, прибавив к числам из множества А сначала число

, а затем число

, он получил один и тот же набор сумм:
, \dots ,r_p (a_m+b_1 )\} = \{r_p (a_1+b_2 ), \dots ,r_p (a_m+b_2 )\},})
где
})
– остаток от деления числа m на число p. Следовательно, для любого

существует такой

, что
=r_p (c+b_1 ).})
Другими словами, верно, что для любого
)=r_p (c)=c\in A.
})
Значит, для любого

и для всех

верно, что
)\in A. })
Но для таких k числа вида
) })
между собой различны. (Действительно, пусть числа
) })
и
) })
совпадают. Значит, разность
)- (a+k_2(b_2-b_1)) })
делится на p, а следовательно, на p делится произведение
(b_2-b_1),})
что невозможно, так как каждый сомножитель по абсолютной величине не превосходит

а число p – простое.) Получается, что множество А уже содержит p чисел, что противоречит (1).
Итак, доказано, что каждый раз количество различных чисел увеличивается по крайней мере на 1. Значит, самое позднее на странице с номером

будут записаны все p чисел. Эта оценка достижима: если каждый раз выбирать числа 0 и 1, то все числа впервые будут записаны именно на странице с номером

и не раньше. Следовательно, искомое N равно

Чтобы для получения всех чисел Дима заполнял в тетради максимальное (равное

) количество страниц, ему следует выбирать числа так, чтоб количество новых различных сумм увеличивалось каждый раз ровно на 1. Для этого необходимо и достаточно, чтобы полученные на каждом шаге различные числа образовывали арифметическую прогрессию, то есть
 \},})
где d – произвольное заранее выбранное число от 1 до

а новые числа

и

надо выбирать так, чтобы

Достаточность очевидна. Необходимость легко доказать по индукции. Действительно, пусть сперва Дима выбрал числа

и

Положим

Затем он выбрал числа

и

и, в результате, получил суммы

Из этих сумм две должны совпадать. Значит, или

или

В обоих случаях

Нетрудно заметить, что получившиеся в результате три новые суммы образуют арифметическую прогрессию. Пусть теперь на m-том шаге получены суммы

образующие арифметическую прогрессию с разностью d. Прибавляя к ней новые числа

и

мы "сдвигаем" всю прогрессию вправо на

и

позиций, и если

то количество новых различных сумм увеличится более чем на 1. Значит,

и новые суммы опять образуют арифметическую прогрессию с той же разностью. Необходимость доказана.