С. Артёмов, Ю. Гиматов, В. Фёдоров
Он думал, что уснула я
И всё во сне стерплю.
Иль думал, что я думала,
Что думал он «я сплю».
С. Маршак. Из Ковентри Патмора.
Предлагаем вниманию читателей задачу, требующую для решения весьма изощрённой логики:
Математик 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. | (3) |
В самом деле, предположим, что 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. | (5) |
Допустим противное: 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 – простое число.