С. Артёмов,   Ю. Гиматов,   В. Фёдоров Много битов из ничего

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

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

– Я, пожалуй, не могу сказать, чему равны задуманные числа.	(π1)
– Я заранее знал, что Вы этого не сможете.	(σ1)
– А ведь тогда я их знаю.	(π2)
– А тогда и я их знаю.	(σ2)

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

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

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

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

Обозначим задуманные числа через k₀ и l₀, причём пусть для определённости k₀ ≤ l₀. Обозначим ещё произведение k₀·l₀ через p₀, сумму k₀ + l₀ через s₀.

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

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

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

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

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

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

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

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

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

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

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

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

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

(π1),	очевидно, означает, что p0 не однозначно разлагается в произведение двух множителей, удовлетворяющих неравенствам (1), (2);	(π′1)
(σ1)	означает, что При любом разложении числа s0 сумму двух слагаемых, удовлетворяющих неравенствам (1), их произведение обладает свойством (π′1).	(σ′1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

годятся: 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 не обладает свойством (σ′₁), должно быть 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 действительно не обладает свойством (σ′₁): 51 = 17 + 34, и произведение 17·34 при разложении на два множителя даёт только одну сумму, меньшую ста. Таким образом, его можно выбросить из списка «кандидатов в s₀».

Числа 27 и 53 удовлетворяют условию (σ′₁): 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, причём все они обладают свойством (σ′₁).

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

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

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

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

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

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

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

Значит, в случае s₀ ≥ 33, S и после (π₂) не смог бы точно назвать k₀, l₀, т.е. не смог бы произнести (σ₂).

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

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

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

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

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

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

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

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

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

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

Итак, s₀ = 17, p₀ = 52, k₀ = 4, l₀ = 13.