Много битов из ничего
С. Артёмов, Ю. Гиматов, В. Фёдоров
Он
думал, что уснула я
И
всё во сне стерплю.
Иль
думал, что я думала,
Что
думал он «я сплю».
С.
Маршак. Из Ковентри Патмора.
Предлагаем
вниманию читателей задачу, требующую для решения весьма изощрённой логики:
Математик
R сказал математикам P и S: «Я задумал два натуральных числа. Каждое из них
больше единицы, а сумма их меньше ста. Математику P я сейчас сообщу – по
секрету от S – произведение этих чисел, а математику S я сообщу – по секрету от
P – их сумму». Он выполнил обещанное и предложил отгадать задуманные числа.
Между P и S произошёл следующий диалог (высказывания P мы обозначаем буквой
π с индексами, высказывания S – буквой σ):
| – Я, пожалуй, не могу сказать, чему равны задуманные
числа. |
(π1) |
| – Я заранее знал, что Вы этого не сможете. |
(σ1) |
| – А ведь тогда я их знаю. |
(π2) |
| – А тогда и я их знаю. |
(σ2) |
Попробуйте
теперь и вы отгадать задуманные числа.
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, удовлетворяющие
неравенствам
| 2 ≤ k0 ≤ l0 ≤ 97, |
(1) |
| 2 ≤ k0 + l0 ≤ 99, |
(2) |
и
проверять, «выдерживают» ли они диалог (π1) – (σ2).
Поскольку
перебор во всех случаях конечен, в принципе можно было бы действовать и так.
Однако решать задачу таким образом скучно. Попробуем сократить перебор.
Прежде
всего давайте сначала искать не k0 и l0, а их сумму s0: для пары (k0, l0)
возможных вариантов больше двух тысяч, а для s0 – меньше ста. Впрочем, и на
этом пути лобовой перебор длинен и скучен.
2.
Около гипотезы Гольдбаха-Эйлера
Какую
информацию можно извлечь из (π1) и (σ1)? Что они означают?
| (π1), |
очевидно, означает, что
p0 не однозначно разлагается в произведение двух множителей,
удовлетворяющих неравенствам (1), (2);
|
(π′1) |
| (σ1) |
означает, что
При любом разложении числа s0 сумму двух слагаемых,
удовлетворяющих неравенствам (1), их произведение обладает свойством (π′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 возможностей:
| 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53. |
(4) |
Попробуем
теперь без перебора установить, какие из чисел (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.