Ровно заданное число кратных в отрезке

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Самый короткий и самый длинный отрезки
  2. Конечное число положений

    Сначала: Самый короткий и самый длинный отрезки

  3. Конструкция

    Сначала: Конечное число положений

  4. Ответ: да

    Сначала: Конструкция

  5. Самый короткий и самый длинный отрезки

    Сначала: Ответ: да

  6. Конечное число положений

    Сначала: Самый короткий и самый длинный отрезки

  7. Конструкция

    Сначала: Конечное число положений

  8. Ответ: нет

    Сначала: Конструкция

  9. Самый короткий и самый длинный отрезки

    Сначала: Ответ: нет

  10. Конечное число положений

    Сначала: Самый короткий и самый длинный отрезки

  11. Наибольший возможный делитель

    Сначала: Конечное число положений

  12. Ответ

    Сначала: Наибольший возможный делитель

Разобранный пример

На доске записано некоторое количество последовательных натуральных чисел, среди которых ровно пять делятся на 20.

а) Могло ли среди записанных чисел быть больше пяти чисел, делящихся на 21?

б) Могло ли среди записанных чисел быть меньше пяти чисел, делящихся на 15?

в) Найдите наибольшее возможное число kk такое, что среди записанных чисел больше пяти чисел делятся на kk.

Посмотреть решение

Предварительное решение, не проверено экспертом.

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

Шаг 1. Пусть ровно qq кратных dd имеют вид td, (t+1)d, …, (t+q−1)dtd,\,(t+1)d,\,\ldots,\,(t+q-1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td, (t+q−1)d]J=[td,\,(t+q-1)d] и содержится в длинном I=[(t−1)d+1, (t+q)d−1]I=[(t-1)d+1,\,(t+q)d-1]. В обоих ровно qq кратных dd. Поэтому для возможности большого количества других кратных достаточно II, а для малого - JJ.
q=5q=5
D=20D=20
Шаг 2. Количество кратных mm в отрезке [A, B][A,\,B] равно ⌊Bm⌋−⌊A−1m⌋\left\lfloor \frac{B}{m}\right\rfloor -\left\lfloor \frac{A-1}{m}\right\rfloor. При сдвиге tt на mНОД(d, m)\frac{m}{\text{НОД}(d,\,m)} обе границы сдвигаются на кратное mm, поэтому число кратных не меняется. Достаточно t=1, …, mНОД(d, m)t=1,\,\ldots,\,\frac{m}{\text{НОД}(d,\,m)}; эти положительные положения охватывают все возможные остатки.
M=21M=21
Шаг 3. Указываем интервалы, числа или допустимые переходы.
T=((21;139;6))\mathcal T=\left(\left(21;139;6\right)\right)
Шаг 4. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Пусть ровно qq кратных dd имеют вид td, (t+1)d, …, (t+q−1)dtd,\,(t+1)d,\,\ldots,\,(t+q-1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td, (t+q−1)d]J=[td,\,(t+q-1)d] и содержится в длинном I=[(t−1)d+1, (t+q)d−1]I=[(t-1)d+1,\,(t+q)d-1]. В обоих ровно qq кратных dd. Поэтому для возможности большого количества других кратных достаточно II, а для малого - JJ.
q=5q=5
D=20D=20
Шаг 2. Количество кратных mm в отрезке [A, B][A,\,B] равно ⌊Bm⌋−⌊A−1m⌋\left\lfloor \frac{B}{m}\right\rfloor -\left\lfloor \frac{A-1}{m}\right\rfloor. При сдвиге tt на mНОД(d, m)\frac{m}{\text{НОД}(d,\,m)} обе границы сдвигаются на кратное mm, поэтому число кратных не меняется. Достаточно t=1, …, mНОД(d, m)t=1,\,\ldots,\,\frac{m}{\text{НОД}(d,\,m)}; эти положительные положения охватывают все возможные остатки.
M=15M=15
Шаг 3. Указываем интервалы, числа или допустимые переходы.
T={}\mathcal T=\left\{\right\}
Шаг 4. Нет. Необходимое ограничение или полный конечный разбор исключает такую возможность.
Шаг 1. Пусть ровно qq кратных dd имеют вид td, (t+1)d, …, (t+q−1)dtd,\,(t+1)d,\,\ldots,\,(t+q-1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td, (t+q−1)d]J=[td,\,(t+q-1)d] и содержится в длинном I=[(t−1)d+1, (t+q)d−1]I=[(t-1)d+1,\,(t+q)d-1]. В обоих ровно qq кратных dd. Поэтому для возможности большого количества других кратных достаточно II, а для малого - JJ.
Шаг 2. Количество кратных mm в отрезке [A, B][A,\,B] равно ⌊Bm⌋−⌊A−1m⌋\left\lfloor \frac{B}{m}\right\rfloor -\left\lfloor \frac{A-1}{m}\right\rfloor. При сдвиге tt на mНОД(d, m)\frac{m}{\text{НОД}(d,\,m)} обе границы сдвигаются на кратное mm, поэтому число кратных не меняется. Достаточно t=1, …, mНОД(d, m)t=1,\,\ldots,\,\frac{m}{\text{НОД}(d,\,m)}; эти положительные положения охватывают все возможные остатки.
Шаг 3. Длина II равна (q+1)d−1(q+1)d-1. Для более чем qq кратных mm отрезок должен иметь длину не меньше qm+1qm+1. Значит, m≤⌊(q+1)d−2q⌋m\leq\left\lfloor \frac{(q+1)d-2}{q}\right\rfloor. Для всех mm в этой конечной области проверяем длинные отрезки за полный период. Наибольший подходящий mm достигается приведённым отрезком.
T=((1;1;119);(2;1;119);(3;1;119);(4;1;119);(5;1;119);(6;1;119);(7;1;119);(8;1;119);(9;1;119);(10;1;119);(11;1;119);(12;1;119);(13;1;119);(14;1;119);(15;1;119);(16;1;119);(17;1;119);(18;1;119);(19;1;119);(21;21;139);(22;21;139);(23;21;139))\mathcal T=\left(\left(1;1;119\right);\left(2;1;119\right);\left(3;1;119\right);\left(4;1;119\right);\left(5;1;119\right);\left(6;1;119\right);\left(7;1;119\right);\left(8;1;119\right);\left(9;1;119\right);\left(10;1;119\right);\left(11;1;119\right);\left(12;1;119\right);\left(13;1;119\right);\left(14;1;119\right);\left(15;1;119\right);\left(16;1;119\right);\left(17;1;119\right);\left(18;1;119\right);\left(19;1;119\right);\left(21;21;139\right);\left(22;21;139\right);\left(23;21;139\right)\right)
Шаг 4. Записываем найденное значение.
2323

Открыть задачу целиком

Попробовать самостоятельно