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

12

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

Он думал, что уснула я
И все во сне стерплю,
Иль думал, что я думала,
Что думал он «я сплю».
С. Маршак. Из Ковентри Патмора.

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

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

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

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

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

Бит — двойная единица измерения информации (БСЭ, 3 изд., 2 т.).

можно отгадать числа, когда про них ничего не сказано?

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

Обозначим задуманные числа через 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₀ в виде суммы двух допустимых слагаемых:

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, получив s₀ = 49, не имел бы права произведения (σ₁). Значит, R не мог задумать 7 и 42.

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

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

13

неравенствам
$$2 \leq k_0 \leq l_0 \leq 97,$$
$$4 \leq k_0 + l_0 \leq 99,$$
(1)
(2)

и проверять, «выдерживают» ли они диалог $(\pi_1) - (\sigma_2)$.

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

Прежде всего давайте сначала не $k_0$ и $l_0$, а их сумму $s_0$: для пары $\langle k_0, l_0 \rangle$ возможных вариантов большие двух тысяч, а для $s_0$ — меньшее ста. Впрочем, и на этом пути любой перебор длиен и скучен.

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

Какую информацию можно извлечь из $(\pi_1)$ и $(\sigma_1)$? Что они означают? $(\pi_1)$, очевидно, означает, что $p_0$ не однозначно разладается в произведение двух множителей, удовлетворяющих неравенствам (1), (2);

$(\sigma_1)$ означает, что При любом разложении числа $s_0$ в сумму двух слагаемых, удовлетворяющих неравенствам (1), их произведение обладает свойством $(\pi_1')$.

Высказывание $(\pi_1')$ позволяет отбросить некоторые произведения, $(\sigma_1')$ — неокоторые суммы.

Из $(\sigma_1')$ вытекает, что $s_0$ не представляет в виде суммы двух простых чисел: если $s_0' = q_1 + q_2$, где $q_1, q_2$ — простые, то число $q_1 \cdot q_2$ единственным образом разладается в произведение двух множителей, удовлетворяющих неравенствам (1), (2), и, следовательно, не обладает свойством $(\pi_1')$.

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

Следовательно, $s_0$ — нечетное. Кроме того, $s_0 - 2$ — составное: иначе $s_0 = 2 + (s_0 - 2)$ представлялось бы в виде суммы двух простых.

простых. После отбрасывания чисел, не удовлетворяющих этим двум условиям, для $s_0$ остается 24 возможности.

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

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

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

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

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

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

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

Оказывается, из $(\sigma_1')$ можно вывести $s_0 < 55$. (3)

В самом деле, предположим, что $s_0 \geq 55$. Тогда $s_0$ не обладает свойством $(\sigma_1')$: можно так разложить его в сумму двух слагаемых, удовлетворяющих неравенствам (1), что для их произведения не будет выполнен условие $(\pi_1')$. Это разложение: $s_0 = (s_0 - 53) + 53$. Из $s_0 \geq 55$ вытекает $s_0 - 53 \geq 2$. Произведение $(s_0 - 53) \cdot 53$ единственным образом разладает на два множители, с умом которых меньше эта: поскольку 53 — простое число, один из множителей обязательно имеет вид 53d; так как $53 \cdot 2 > 100$, $d = 1$. Но по условияю $s_0$ обладает свойством $(\sigma_1')$. Противоречие!

14

После (3) для $s_0$ остается уже 11 возможностей:
$$11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53.$$

Попробуем теперь без перебора установить, какие из чисел (4) удовлетворяют условиям ($\sigma'_1$). Пусть $s$ — произвольное из чисел (4). Поскольку $s$ нечетно, всякое его разложение в сумму имеет вид $s = 2a + m$. Допустим, $s$ не обладает свойством ($\sigma'_1$). Тогда найдет такое $a$, что произведение $2a \cdot m$ «расшифровывает» однозначно.

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

$$2m = 2 \cdot pq = 2p \cdot q$$

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

Значит, $a \geq 2$.

Если $a \neq m$, то $s = 2a \cdot m$ и $s = 2m \cdot a$ — два различных разложения. Поскольку $2a + m = s < 100$ и $s$ не обладает свойством ($\sigma'_1$), должно быть $2m + a \geq 100$. Так как $s = 2a + m \leq 53$, имеем $m \leq 53 - 2a$, $2m + a \leq 106 - 3a$. Из $2m + a \geq 100$ и $2m + a \leq 106 - 3a$ вытекает $a \leq 2$. Следовательно, $a = 2$. Из $2m + a \geq 100$ и $m \leq 53 - 2a$ получаем теперь $m = 49$. Итак, в этом случае $s = 53$, причем «подозрительным» является разложение $53 = 4 + 49$.

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

Число 51 действительно не обладает свойством ($\sigma'_1$): $51 = 17 + 34$, и произведение 17·34 при разложении на два множителя дает только одну сумму, меньше стока. Таким образом, его можно выбросить из списка «кандидатов в $s_0$».

Числа 27 и 53 удовлетворяют условиям ($\sigma'_1$): $9 \cdot 18 = 2 \cdot 81$ и $2 + 81 < 100; 4 \cdot 49 = 7 \cdot 28$ и $7 + 28 < 100$.

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

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

Используем, наконец, $(\pi_2)$ и $(\sigma_2)$.

Можно было бы использовать $(\pi_2)$ и $(\sigma_2)$ подобно тому, как мы это сделали с $(\pi_1)$ и $(\sigma_1)$. Мы попробуем обойтись без этого.

Из $(\sigma_2)$ и (3) можно вывести

$$s_0 < 33.$$

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

Если бы $P$ было сообщено произведение $(s_0 - 31) \cdot 31$, то он мог бы сообщить, что 31 — простое число, понять, что $(s_0 - 31) \cdot 31$ единственным образом разлагается в произведение двух множителей, сумма которых удовлетворяет (3). В этом случае $P$ отгадал бы $k_0$ и $l_0$.

Аналогичная возможность была у $P$, если бы было сообщено произведение $(s_0 - 29) \cdot 29$.

Значит, в случае $s = 53$, причем «подозрительным» является разложение $53 = 4 + 49$.

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

Число 51 действительно не обладает свойством ($\sigma'_1$): $51 = 17 + 34$, и произведение 17·34 при разложении на два множителя дает только одну сумму, меньше стока. Таким образом, его можно выбросить из списка «кандидатов в $s_0$».

Числа 27 и 53 удовлетворяют условиям ($\sigma'_1$): $9 \cdot 18 = 2 \cdot 81$ и $2 + 81 < 100; 4 \cdot 49 = 7 \cdot 28$ и $7 + 28 < 100$.

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

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

29 тоже не годится, поскольку, поскольку $29 = 4 + 25 = 16 + 13$: если бы $P$ имел $p_0 = 16 \cdot 13$, он бы отгадал $k_0$ и $l_0$, так как среди сумму $2^{4-t} + 2^t \cdot 13$ нечетна только одна; если бы $P$ имел $p_0 = 4 \cdot 25$, он бы тоже отгадал $k_0$ и $l_0$: среди соответствующих сумм не