Ответ:
Обозначим через A(n) множество остатков от деления n на числа от 1 до ⌊n/2⌋. При переходе от n к n + 1 число остатков по каждому уже имеющемуся делителю меняется на 1 по кругу: остаток k − 1 превращается в 0, остальные остатки увеличиваются на 1.
Сравнение этих множеств показывает, что количество различных остатков при таком переходе может увеличиться не более чем на 2. Эта граница достигается: например, при n = 5 остатки по делителям 1 и 2 равны 0, 1, поэтому r(5) = 2. Для 6 остатки по делителям 1, 2 и 3 равны 0, 0, 0, поэтому здесь разность отрицательна; для достижения верхней границы достаточно рассмотреть n = 3: остатки по делителю 1 дают r(3) = 1, а для 4 остатки по 1 и 2 равны 0, 0, то есть разность также не подходит. Следовательно, максимальное увеличение равно 2.
Ответ: 2.
