Размышляя об одной олимпиадной задаче

37

Значит, если вы собирались делать построения циркулем и линейкой и забыли дома линейку, не беда — можно обойтись одним циркулем; если же вы забыли циркуль — попросите его утоварища и нарисуйте им одну окружность, предварительно пометив ее центр; после этого вы можете построить что угодно одной линейкой. (Хуже, конечно, если вы забыли дома и циркуль, и линейку — здесь уже наука бесcilна вам помочь.)

Размышляя об одной оптимальной задаче

В. Я. САННИНСКИЙ

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

Я показую это на примере следующей задачи на доказательство, встречающейся во многих конкурсных сборниках:

Если все простые числа, начная с 5, запутеваны в порядке возрастания, то каждое запутеванное простое число будет больше своего утренного номера.

Попробуйте доказать это самостоятельно. Это не очень трудно, я, например, придумал доказательство довольно быстро*. Однако после этого я не бросил задачу, а стал размышлять над ее формулировкой. И сразу возник вопрос: причем здесь числа 5 и 3, нельзя ли взять другие числа? Это подсказывает об обценке задачи — вместе пары чисел (3, 5) расстоять произвольную пару $(k, p)$, где $k$ — натуральное, а $p$ — простое. Получилось утверждение, которое я назвал

$Y(k, p)$: если все простые числа, начная с $p$, запутевать в порядке

*) Я воспользовался тем, что средние последовательных чисел $9n, 9n+1, \dots, 9n+8, n=1, 2, 3, \dots$, может встретиться не более трех простых.

возрастания, то каждое запутеванное простое число больше чем его номер, умноженный на $k$.

Одна беда. Это утверждение не всегда верно (не для всех $k$ и $p$). Например, $Y(3,3)$ — ложно (простое число 13 меньше, чем его утроенный номер: $13 < 3 \times 5 = 15$). С другой стороны, мы знаем, что $Y(3,5)$ — верно (это утверждение нашей исключной задачи). Ну а тогда возникает задача описания всех хороших пар $(k, p)$, то есть таких пар, для которых $Y(k, p)$ верно.

Чтобы решить ее, я начал пробовать различные небольшие пары, и быстро нашел несколько нежорших (например, $(4,5), (6,3)$) и несколько хороших пар $(\langle 1,2\rangle, (2,3), (2,5), (3,7))$. Советуючитатель превращать чтение на этом месте и тоже пробовать небольших пар.

Далее читатель не последовал моему совету, он легкооймет, что из справедливости $Y(k, p)$ вытекает справедливость $U(k', p')$, если $k' \leq k$ и $p' \geq p$. Я тоже это быстро заметил и поэтому решил не искать все хорошие пары, а искать только неулучшемые пары $(k, p)$, то есть такие, для которых верно $Y(k, p)$, но ложно $Y(k', p')$ при $p' > k$ и ложно $Y(k', p')$ при $p' < p$. Так возникала новая задача: найти все неулучшемые пары.

Упражнение 1. Докажите, что пары $(1,2), (2,3) и (3,5)$ неулучшемые.

Я это доказал, как наверно и читатель, без особого труда и взгляда за следующее пару — $(4,7)$. Она оказалась не хорошей: $7 > 4 \cdot 1, 11 > 4 \cdot 2, 13 > 4 \cdot 3, 17 > 4 \cdot 4$, но неверно, что $19 > 4 \cdot 5$. Я перешел к следующей паре — $(4,11)$ — и начал пробовать $11 > 4 \cdot 1, 13 > 4 \cdot 2, \dots, 29 > 4 \cdot 6, 31 > 4 \cdot 7, \dots$. Вскоре мне это надоело, и я решил, что у меня есть правдоположная гипотеза: пара $(4,11)$ неулучшема. Признаюсь, мне пришлось немало повозиться, преждеем чем я сумел ustановить справедливость этой гипотезы.

38

Рассудал я так. Пусть $p_1 = 11, p_2 = 13, ..., p_n, ...$ интеграция нас нужнация. Чтобы доказать $Y(4, 11)$, нужно установить неравенство $p_n > 4n$ для всех $n \in \mathbb{N}$. Возьмем число $m = 210 = 2 \cdot 3 \cdot 5 \cdot 7$ (произведения всех простых чисел, меньших 11) и разобем множество натуральных чисел $n \geq 11$ на $m$ классов, в зависимости от остатка при их делении на $m$. Именно, к $r$-ому классу $K_r$, $r = 0, 1, ..., m - 1$ отнесем все числа вида $n = tm + r$, где $t \in \mathbb{N}$. тогда каждое натуральное число $n$ попадаетровно в один класс $K_r$ — именно, в класс с номером $r$, равным остатку от деления $n$ на $m = 210$. Выбросим из списка $K_0, K_1, ..., K_{m-1} = K_{209}$ все классы, номера которых — составные числа. Другими словами, остатим в списке лишь те классы, номера которых взаимно просты с $m$. Заметим, что все рассматриваемые простые числа $p_1, p_2, ..., p_n$ … находятся в осташих классах (почему?). Обозначим номера осташих классов через $a_1, a_2, a_3, ...$, например, $a_1 = 11, a_2 = 13, ..., a_{47} = 209$.

Уражение 2. Найдите все номера (их $\varphi(m) = \varphi(210) = 48$) осташих классов и проверите, что для них выполяется неравенство $a_n > 4n$, где $n = 1, 2, ..., 48$.*

Занутем теперь в порядке возрастания все числа, находящиеся в осташих классах. Этот список начинается с уже известных нам чисел $a_1, a_2, a_3, ...$, но не оборвется на $a_{48} = 211$, а поддет дальше: $a_{49} = 217, a_{50} = 221, ...$. Тогда оченьindo, что $a_n \leq p_n$ для всех $n = 1, 2, ...$ (ведь наши простые числа $p_1, p_2, ...$ находятся среди осташих чисел $a_1, a_2, ...$). Поэтому нам достаточно доказать неравенство $a_n > 4n$ (для всех $n$). Для первых 48 чисел $a_1, ..., a_{48}$ оно уже проверено (упражнение 2), для дальнейших $n$ мы его докажем по индукции. Индукцию будет вести по вспомогательному параметру $t$ при фиксированном $r$ ($r = 1, 2, ..., 48$), то есть проверем доказательство для всех чисел из класса с номером $a_r$. Любое число $a_s$ из этого класса представляется в виде $a_s = t \cdot 210 + r$. Начало индукции уже есть (мы проверили, что при $t = 0$ число $a_r$ удовлетворяет неравенству $a_r > 4r$). Пусть (индукционное предложение), $a_s = 210 \cdot t + r > 4s$. Нам нужно установить неравенство $210(t + 1) + r > 4(s + 48)$, либо $s + 48$ — номер следующего числа $210(t + 1) + r$ из рассматриваемого класса (с номером $a_r$). Но оно сразу следует из индукционного предложения и оченьного неравенства $210 > 4 \cdot 48$. Утверждение $Y(4, 11)$ доказано.

Уражение 3. Проверите, что при $k > 5$ утверждение $Y(k, 11)$ неверно.

Так как $Y(4, 7)$ неверно то же, мы установили, что пара $(4, 11)$ действительное неулучшаема.

Проблем продвижется дальше — будем искать неулучшаемую пару вида $(5, p)$.

Уражение 4. Проверите, что пары $(5, p)$ не являются хорошими при $p < 23$, также как и пара $(6, 23)$.

Исследование пары $(5, 23)$ $(23 > 5 \cdot 1, 29 > 5 \cdot 2, 31 > 5 \cdot 3$ и т. д.) приводит к

*) Классы $K_0, K_1, ..., K_{m-1}$ называются классами вычетов по модулю $m$. Число этих классов с номерами взаимно простыми с $m$ обозначается $\varphi(m)$; функция $\varphi$ называется функцией Эйлера.

очередной гипотезе: пара $(5, 23)$ неулучшаема.

Справедливо есть той гипотезы можно установить, рассуждая так же, как для пары $(4, 11)$. То есть взять $m = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 9699690$, рассмотреть классы вычетов по модулю $m$, из них выделить $\varphi(m) = 1658880$ классов, взаимно простых с $m$, занимает в все числа (начиная с 23) из выделенных классов в порядке возрастания $(a_1, a_2, ...)$ и доказать по индукции, что неравенство $a_n > 5n$ (из которого следует $p_n > 5n$ для выбранной номера простых чисел $p_1 = 23, p_2 = 29, ...$) верно для любого числа $a_n$ из данной класса, если оно верно для номера $a_n$ этого класса. Тогда остется «только» проверить, что неравенство $a_n > 5n$ выполняется для всех $n$ от 1 до $\varphi(m) = 1658880$. Конечно, эта проверка неоспользовна для человека. Пришлось ее поручить машине; ЭВМ ЕС — 1045 за 6 минут для ответ; действительно, $a_n > 5n$ при $n = 1, 2, ..., \varphi(m)$. Гипотеза о неулучшаемости пары $(5, 23)$ установлен.

В современной математике такое встречается часто: логическими рассуждениями математик свойит задачу проверки бесконечного набора утверждений (у нас — неравенств) к конечному (но большому) набору, а уже утверждения этого набора проверяет ЭВМ.

Каковы дальнейшие перспективы? Пониск следующей неулучшаемой пары (вида $(6, p)$) приводит к числам, на пределе возможности ЭВМ ЕС — 1045, а пары вида $(7, p)$ — завершено не подаются нашему подходу. Позатем я пробовал иначе обобщить исходную задачу и пришел к следующей формулировке:

Торема. Простые числа растут быстрое любой линейной функции от их номера; иначе говоря, если $p_1 = 2, p_2 = 3, ..., p_n, ...$ последовательность всех простых чисел в порядке возрастания, то для любых $k$ и $b$ неравенство $p_n > kn + b$ выполняется для всех $n$, больших некоторого $n_0$ (зависящего от $k$ и $b$).

Попробyte и вы доказать эту известную дальше? Например, можно было попробовать доказать, что простые числа растут медленнее, чем многолен второй степени от их номера. Но это уже трудная задача: мы приближаем к переднему краю науки, и двигать дальше можно только изучить труды наших великих предшественников — Эйлера, Лагранжа, Гаусса, Римана, Чебышева.