Остатки ограничивают размер набора

Если наименьшее записанное число mm не должно делить никакую разность, все числа набора имеют разные остатки по модулю mm. Значит их количество не больше mm.

Когда применять

  • Параметры и ограничения взяты из условия.
  • Все перечисляемые значения целые; границы области установлены до перебора.

Почему это работает

  1. При делении на mm возможны ровно mm остатков: 0, 1, …, m−10,\,1,\,\ldots,\,m-1.
  2. Два одинаковых остатка дают разность, кратную mm; если mm само записано и это запрещено, на каждый остаток приходится не больше одного числа.
  3. Соединяем N≤mN\leq m с ограничением промежутков между соседними числами, а затем проверяем достигающий набор по обеим частям условия.

Пример

Набор 3, 5, 73,\,5,\,7 подходит: разности 2 и 4 не делят нечетные числа; ни одно число набора не делит эти разности. Для чисел не больше 7 запрет соседних и N≤mN\leq m дают 7≥m+2(N−1)≥3N−27\geq m+2(N-1)\geq 3N-2, то есть N≤3N\leq 3. Граница достигнута.

Граница применения

Условие о делимости в обе стороны проверяем отдельно. Разные остатки запрещают только деление разности на записанное число; обратный запрет тоже нужен.

В задаче сначала устанавливаем область, затем находим допустимые значения и предъявляем пример достижения ответа.

Учебные основания
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.

Авторский вывод из прочитанных правил; задача банка не объявляется примером из книги.

Задачи по этому правилу