На доске записано некоторое количество последовательных натуральных чисел, среди которых ровно пять делятся на 20.
а) Могло ли среди записанных чисел быть больше пяти чисел, делящихся на 21?
б) Могло ли среди записанных чисел быть меньше пяти чисел, делящихся на 15?
в) Найдите наибольшее возможное число k такое, что среди записанных чисел больше пяти чисел делятся на k.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Пусть ровно q кратных d имеют вид td,(t+1)d,…,(t+q−1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td,(t+q−1)d] и содержится в длинном I=[(t−1)d+1,(t+q)d−1]. В обоих ровно q кратных d. Поэтому для возможности большого количества других кратных достаточно I, а для малого - J.
q=5
D=20
Шаг 2. Количество кратных m в отрезке [A,B] равно ⌊mB⌋−⌊mA−1⌋. При сдвиге t на НОД(d,m)m обе границы сдвигаются на кратное m, поэтому число кратных не меняется. Достаточно t=1,…,НОД(d,m)m; эти положительные положения охватывают все возможные остатки.
M=21
Шаг 3. Указываем интервалы, числа или допустимые переходы.
T=((21;139;6))
Шаг 4. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Пусть ровно q кратных d имеют вид td,(t+1)d,…,(t+q−1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td,(t+q−1)d] и содержится в длинном I=[(t−1)d+1,(t+q)d−1]. В обоих ровно q кратных d. Поэтому для возможности большого количества других кратных достаточно I, а для малого - J.
q=5
D=20
Шаг 2. Количество кратных m в отрезке [A,B] равно ⌊mB⌋−⌊mA−1⌋. При сдвиге t на НОД(d,m)m обе границы сдвигаются на кратное m, поэтому число кратных не меняется. Достаточно t=1,…,НОД(d,m)m; эти положительные положения охватывают все возможные остатки.
M=15
Шаг 3. Указываем интервалы, числа или допустимые переходы.
T={}
Шаг 4. Нет. Необходимое ограничение или полный конечный разбор исключает такую возможность.
Шаг 1. Пусть ровно q кратных d имеют вид td,(t+1)d,…,(t+q−1)d. Любой отрезок с этими кратными содержит короткий отрезок J=[td,(t+q−1)d] и содержится в длинном I=[(t−1)d+1,(t+q)d−1]. В обоих ровно q кратных d. Поэтому для возможности большого количества других кратных достаточно I, а для малого - J.
Шаг 2. Количество кратных m в отрезке [A,B] равно ⌊mB⌋−⌊mA−1⌋. При сдвиге t на НОД(d,m)m обе границы сдвигаются на кратное m, поэтому число кратных не меняется. Достаточно t=1,…,НОД(d,m)m; эти положительные положения охватывают все возможные остатки.
Шаг 3. Длина I равна (q+1)d−1. Для более чем q кратных m отрезок должен иметь длину не меньше qm+1. Значит, m≤⌊q(q+1)d−2⌋. Для всех m в этой конечной области проверяем длинные отрезки за полный период. Наибольший подходящий m достигается приведённым отрезком.