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