Много битов из ничего

С. Артёмов, Ю. Гиматов, В. Фёдоров

Он думал, что уснула я

И всё во сне стерплю.

Иль думал, что я думала,

Что думал он «я сплю».

С. Маршак. Из Ковентри Патмора.

Предлагаем вниманию читателей задачу, требующую для решения весьма изощрённой логики:

Математик R сказал математикам P и S: «Я задумал два натуральных числа. Каждое из них больше единицы, а сумма их меньше ста. Математику P я сейчас сообщу – по секрету от S – произведение этих чисел, а математику S я сообщу – по секрету от P – их сумму». Он выполнил обещанное и предложил отгадать задуманные числа. Между P и S произошёл следующий диалог (высказывания P мы обозначаем буквой π с индексами, высказывания S – буквой σ):

Попробуйте теперь и вы отгадать задуманные числа.

1. Неужели их можно отгадать?

При первом взгляде на задачу она представляется неразрешимой: как можно отгадать числа, когда про них ничего не сказано?

Попробуем на примере. Пусть R задумал 7 и 42. Тогда он сообщил P число 294, S – 49. Ну, а что дальше? Р сказал, что он не может отгадать задуманные числа. Ну, конечно же не может – он знает только их произведение. Хотя, впрочем, он знает ещё, что они натуральные, больше единицы и их сумма меньше ста. А что это даёт?

Обозначим задуманные числа через k0 и l0, причём пусть для определённости k0 ≤ l0. Обозначим ещё произведение k0·l0 через p0, сумму k0 + l0 через s0.

Итак, P сообщили, что p0 = 294.

Тогда k0 может равняться 2, 3, 6, 7 и 14, а l0 будет при этом равно, соответственно, 147, 98, 49, 42 и 21. Первые два значения для k0 нам не подходят – при них s0 > 100. Всё равно остаются ещё три возможности. Значит, P действительно не может отгадать задуманные числа.

Идём дальше. S утверждает, что он заранее знал, что P не сможет отгадать k0 и l0. Как S пришёл к такому выводу? Наверняка он попробовал всеми возможными способами представить известное ему s0 в виде суммы двух допустимых слагаемых:

49 = 2 + 47 = 3 + 46 = ... = 24 + 25.

R мог задумать любую из этих пар чисел. Он сообщил P какое-то из произведений i·(49 – i), и S утверждает, что ни по одному из них P не может отгадать задуманные числа.

А если при некотором i оба числа i, 49–i – простые? Например, если R задумал 2 и 47, то P он сообщил 94, и P прекрасно может отгадать задуманные числа.

Следовательно, если R задумал 7 и 42, то S, получив s0 = 49, не имел бы права произнести (σ1). Значит, R не мог задумать 7 и 42.

Таким образом, кое-что о задуманных числах сказать всё-таки можно.

Преодолев первоначальные сомнения, подумаем, в каком направлении двигаться. Один способ отгадывания уже виден: брать всевозможные пары чисел k0, l0, удовлетворяющие неравенствам

и проверять, «выдерживают» ли они диалог (π1) – (σ2).

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

Прежде всего давайте сначала искать не k0 и l0, а их сумму s0: для пары (k0, l0) возможных вариантов больше двух тысяч, а для s0 – меньше ста. Впрочем, и на этом пути лобовой перебор длинен и скучен.

2. Около гипотезы Гольдбаха-Эйлера

Какую информацию можно извлечь из (π1) и (σ1)? Что они означают?

Высказывание (π′1) позволяет отбросить некоторые произведения, (σ′1) – некоторые суммы.

Из (σ′1) вытекает, что s0 не представимо в виде суммы двух простых чисел: если s0 = q1 + q2, где q1, q2 – простые, то число q1·q2 единственным образом разлагается в произведение двух множителей, удовлетворяющих неравенствам (1), (2), и, следовательно, не обладает свойством (π′1).

Но любое чётное число, удовлетворяющее неравенствам (2), представимо в виде суммы двух простых (это доказывается последовательной проверкой чисел 4, 6, 8, .... 98).

Следовательно, s0 – нечётное. Кроме того, s0–2 – составное: иначе s0 = 2 + (s0 – 2) представлялось бы в виде суммы двух простых. После отбрасывания чисел, не удовлетворяющих этим двум условиям, для s0 остаётся 24 возможности.

Выше мы воспользовались тем, что все чётные числа от 4 до 98 представимы в виде суммы двух простых.

В 1742 г. член Петербургской Академии наук Христиан Гольдбах в письме к Леонарду Эйлеру высказал предположение, что любое нечётное число, большее пяти, может быть представлено в виде суммы трёх простых чисел. В ответном письме Эйлер выдвинул гипотезу, что каждое чётное число, большее двух, представимо в виде суммы двух простых чисел. (Из гипотезы Эйлера гипотезу Гольдбаха вывести очень легко – сделайте это!)

В течение почти двухсот лет гипотезы Гольдбаха и Эйлера казались совершенно недоступными для доказательства, хотя непосредственным перебором математик Миле проверил их до 9 000 000.

В 1930 г. замечательный советский математик Л. Г. Шнирельман доказал существование такого k, что каждое натуральное число n > 1 может быть представлено в виде суммы не более k простых чисел. Число k у Шнирельмана было довольно велико. В настоящее время доказано, что теорема Шнирельмана верна при k = 20.

В 1934 г. академик И. М. Виноградов доказал существование такого n0, что любое нечётное число n > n0 представимо в виде суммы трёх простых чисел. Казалось бы, в век ЭВМ можно было бы поручить машине проверить «остальные» числа (от 7 до n0), но «постоянная Виноградова» n0 так велика (по последним оценкам n0 > 265536), что эта проверка превосходит возможности современных ЭВМ.

В доказательстве же гипотезы Эйлера до сих пор не достигнуто никакого существенного успеха.

3. Дальше в лес

Оказывается, из (σ′1) можно вывести, что

В самом деле, предположим, что s0 ≥ 55. Тогда s0 не обладает свойством (σ′1): можно так разложить его в сумму двух слагаемых, удовлетворяющих неравенствам (1), что для их произведения не будет выполнено условие (π′1). Это разложение: s0 = (s0 – 53) + 53. Из s0 ≥ 55 вытекает s0 – 53 ≥ 2. Произведение (s0–53)·53 единственным образом разлагается на два множителя, сумма которых меньше ста: поскольку 53 – простое число, один из множителей обязательно имеет вид 53d; так как 53·2 > 100, d = 1. Но по условию s0 обладает свойством (σ′1). Противоречие!

После (3) для s0 остается уже 11 возможностей:

Попробуем теперь без перебора установить, какие из чисел (4) удовлетворяют условию (σ′1). Пусть s – произвольное из чисел (4). Поскольку s нечётно, всякое его разложение в сумму имеет вид s = 2а + m. Допустим, s не обладает свойством (σ′1). Тогда найдётся такое а, что произведение 2a·m «расшифровывается» однозначно.

Это a не может равняться единице, так как в этом случае s = 2 + m, а произведение 2m двояко разлагается в произведение. В самом деле, поскольку m = s–2 – составное нечётное число, m = pq, где р > 2 и q > 2. Оба разложения

2m = 2·pq = 2p·q

годятся: 2 + pq = 2 + m = s < 100 и 2p + q = 2 + pq – (p – 1)(q – 2) < 2 + pq < 100.

Значит, a ≥ 2.

Если a ≠ m, то 2a·m и 2m·a – два различных разложения. Поскольку 2a + m = s < 100 и s не обладает свойством (σ′1), должно быть 2m + a ≥ 100. Так как s = 2a + m ≤ 53, имеем m ≤ 53 – 2a, 2m + a ≤ 106 – 3a. Из 2m + a ≥ 100 и 2m + a ≤ 106 – 3a вытекает a ≤ 2. Следовательно, a = 2. Из 2m + a ≥ 100 и m ≤ 53 – 2a получаем теперь m = 49. Итак, в этом случае s = 53, причём «подозрительным» является разложение 53 = 4 + 49.

Если же a = m, то s = 3a делится на 3. В (4) таких чисел два: 27 и 51. «Подозрительными» являются разложения 27 = 9 + 18 и 51 = 17 + 34.

Число 51 действительно не обладает свойством (σ′1): 51 = 17 + 34, и произведение 17·34 при разложении на два множителя даёт только одну сумму, меньшую ста. Таким образом, его можно выбросить из списка «кандидатов в s0».

Числа 27 и 53 удовлетворяют условию (σ′1): 9·18 = 2·81 и 2 + 81 < 100; 4·49 = 7·28 и 7 + 28 < 100.

Итак, для дальнейшего исследования осталось 10 кандидатов: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53, причём все они обладают свойством (σ′1).

4. «Тогда и я их знаю»

Используем, наконец, (π2) и (σ2).

Можно было бы истолковать (π2) и (σ2) подобно тому, как мы это сделали с (π1) и (σ1). Мы попробуем обойтись без этого.

Из (σ2) и (3) можно вывести

Допустим противное: s0 ≥ 33. Тогда математик S, разлагая всеми возможными способами s0 в сумму двух слагаемых, имел бы среди этих разложений s0 = (s0 – 31) + 31 = (s0 – 29) + 29.

Если бы P было сообщено произведение (s0–31)·31, то он мог бы, сообразив (3) и учтя, что 31 – простое число, понять, что (s0–31)·31 единственным образом разлагается в произведение двух множителей, сумма которых удовлетворяет (3). В этом случае P отгадал бы k0 и l0.

Аналогичная возможность была у P, если ему было сообщено произведение (s0–29)·29,.

Значит, в случае s0 ≥ 33, S и после (π2) не смог бы точно назвать k0, l0, т.е. не смог бы произнести (σ2).

После (5) остается 5 кандидатов: 11, 17, 23, 27, 29.

Если p0 имеет вид 2n·p, где p – нечётное простое число, то P однозначно определяет k0 и l0, потому что из всех сумм 2n–t + 2tp нечётна только одна: 2n + p. Поэтому, если s0 двумя способами представимо в виде 2n + p, то S опять-таки не может произнести (σ2).

Это соображение позволяет отсеять ещё 3 кандидата: 11 = 4 + 7 = 8 + 3, 23 и 27.

Остались 2 кандидата: 17 и 29.

5. Тогда и мы их знаем

29 тоже не годится, поскольку 29 = 4 + 25 = 16 + 13: если бы P имел p0 = 16·13, он бы отгадал k0 и l0, так как среди сумм 24–t + 2t·13 нечётна только одна; если бы P имел p0 = 4·25, он бы тоже отгадал k0 и l0: среди соответствующих сумм нечётна, кроме 29, ещё только 25 (4·25 = 5·20), но 25–2 – простое число.

Итак, либо s0 = 17, либо задача не имеет решений.

Какое же p0 могло быть у P при s0 = 17? Переберём все разложения числа 17 в сумму двух слагаемых:

17 = 2 + 15 = 3 + 14 = ... = 8 + 9.

При любом из произведений, кроме 4·13, P не смог бы произнести (π2). Например, если бы P имел p0 = 30, он среди разложений числа 30 в произведение двух множителей увидел бы и 30 = 2·15, и 30 = 5·6, но как 17, так и 11 обладают свойством (σ′1).

Остается единственный кандидат для p0: 52. Этот кандидат дает возможность P произнести (π2): среди всех разложений числа 52 в произведение двух множителей существует ровно одно: 52 = 4·13, дающее нечётную сумму.

Итак, s0 = 17, p0 = 52, k0 = 4, l0 = 13.