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