Две оценки, которые понадобятся везде

Разберёмся, как связаны длина набора и количество кратных.

Сколько чисел нужно, чтобы поместилось \(t\) кратных числу \(d\). Самый короткий набор начинается кратным \(d\) и им же заканчивается. Между первым и \(t\)-м кратным ровно \(d(t-1)\) шагов, а чисел на одно больше:

\[k \geqslant d(t-1) + 1.\]

Сколько кратных обязательно найдётся среди \(k\) подряд идущих чисел. Разобьём набор на блоки по \(d\) чисел, начиная с первого. В каждом полном блоке ровно одно число кратно \(d\), а в хвосте остаётся не больше \(d-1\) числа. Значит кратных не меньше чем

\[\frac{k - (d-1)}{d}.\]

Важно! Эти две оценки смотрят с разных сторон: первая говорит, какой длины набор нужен, чтобы кратных было много; вторая — сколько кратных неизбежно найдётся в длинном наборе. Вся задача построена на их столкновении.

Пункт а

Достаточно привести пример. Возьмём числа от 23 до 92 включительно.

Кратных 23 здесь четыре: \(23,\ 46,\ 69,\ 92\). Кратных 20 ровно три: \(40,\ 60,\ 80\). Три меньше четырёх — условие выполнено.

Да, могло.

Пункт б

Пусть кратных 20 ровно десять. По условию кратных 23 больше, то есть их не меньше одиннадцати. Применим первую оценку к \(d = 23\) и \(t = 11\):

\[k \geqslant 23\cdot 10 + 1 = 231.\]

Теперь применим вторую оценку к \(d = 20\) и этому \(k\):

\[\text{кратных 20} \geqslant \frac{231 - 19}{20} = \frac{212}{20} = 10{,}6.\]

Количество кратных — целое число, значит их не меньше одиннадцати. А по предположению ровно десять. Противоречие.

Нет, не могло.

Пункт в. Оценка сверху

Пусть кратных 20 ровно \(a\) штук. Кратных 23 тогда не меньше \(a+1\), и по первой оценке

\[k \geqslant 23a + 1.\]

Подставим это во вторую оценку для \(d = 20\):

\[a \geqslant \frac{k - 19}{20} \geqslant \frac{23a + 1 - 19}{20} = \frac{23a - 18}{20}.\]

Умножаем на 20 и собираем слагаемые:

\[20a \geqslant 23a - 18, \qquad 18 \geqslant 3a, \qquad a \leqslant 6.\]

Итак, кратных 20 не больше шести. Осталось понять, какой длины может быть набор, содержащий не больше шести кратных 20. По уже знакомому рассуждению самый длинный такой набор — это шесть кратных плюс по 19 «хвостовых» чисел слева и справа… точнее, из второй оценки:

\[6 \geqslant \frac{k-19}{20}, \qquad 120 \geqslant k - 19, \qquad k \leqslant 139.\]

Пункт в. Пример на 139

Возьмём числа от 161 до 299 включительно. Их ровно

\[299 - 161 + 1 = 139.\]

Кратные 23 здесь — это \(23m\) при \(m\) от 7 до 13, то есть \(161,\ 184,\ 207,\ 230,\ 253,\ 276,\ 299\); их \(13 - 7 + 1 = 7\).

Кратные 20 — это \(20m\) при \(m\) от 9 до 14, то есть \(180,\ 200,\ 220,\ 240,\ 260,\ 280\); их \(14 - 9 + 1 = 6\).

Шесть меньше семи — условие выполнено, и длина набора равна 139.

Ответ: а) да, могло;   б) нет, не могло;   в) 139.