Статья: Много битов из ничего
Он думал, что уснула я
И всё во сне стерплю.
Иль думал, что я думала,
Что думал он «я сплю».
С. Маршак. Из Ковентри Патмора.
Предлагаем вниманию читателей задачу, требующую для решения весьма изощрённой логики:
Математик 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) |
означает, что --> ЧИТАТЬ ПОЛНОСТЬЮ <-- К-во Просмотров: 215
Бесплатно скачать Статья: Много битов из ничего
|