|
24.11.02 19:00 |
Два мудреца (полная версия) |
Условие
Некто сказал мудрецам П и С: 'Я задумал два натуральных числа. Каждое из них больше единицы, а сумма их меньше ста. Мудрецу П я сейчас сообщу - по секрету от С - произведение этих чисел, а мудрецу С я сообщу - по секрету от П их сумму'. Он выполнил обещанное и предложил отгадать задуманные числа. Между П и С произошел следующий диалог
П: 'Я не могу определить числа'.
С: 'Я заранее знал, что ты не сможешь определить числа'.
П: 'Тогда я знаю числа'.
С: 'Тогда я тоже знаю числа'.
Определите и вы задуманные числа.
Подсказка
Конечно, можно решить задачу перебором или написать программу для компьютера. Но хотелось бы решить задачу путем рассуждений. Именно такое решение и предлагается ниже. Отметим, например, что, проанализировав лишь первые два высказывания ('Я не могу определить числа' - 'Я заранее знал, что ты не сможешь определить числа') можно показать, что S - сумма искомых чисел - нечетное число, вида (составное + 2) и меньшее 55, что оставляет для S лишь 11 возможностей. Но и дальше можно избежать перебора и двигаться путем рассуждений.
Решение
Ответ: 4 и 13.
Обозначим задуманные числа K и L, S = K + L, P = K * L, а высказывания мудрецов П.1, С.1, П.2 и С.2, соответственно. Тогда, разумеется, справедливо:
1 < K, L < 98; 3 < S < 100 (1).
Из П.1 и С.1 вытекает, что при любом разбиении S в сумму двух слагаемых, их произведение неоднозначно разлагается на множители, удовлетворяющие (1).
В частности, S не представимо в виде суммы двух простых чисел. Любое четное число (в интересующем нас интервале 3 < S < 100) представимо в виде суммы двух простых чисел (гипотеза Гольдбаха-Эйлера, она не доказана, но и не обнаружено четных чисел, не удовлетворяющих ей). Следовательно, S - нечетное, причем такое, что (S-2) - составное (иначе S = (S-2) + 2 - разложение на два простых числа).
Кроме того, S < 55. Иначе S = (S-53) + 53 и (S-53)*53 - единственным образом разлагается на два множителя, сумма которых меньше 100, поскольку 53 - простое число.
В итоге на основе анализа П.1 и С.1 (S - нечетное число, равное (составное + 2) и меньшее 55) для S остается 11 возможностей:
11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53.
Далее заметим, что с учетом С.2 и того, что уже после С.1 известно, что S < 55, можно получить, что S < 33.
Действительно, пусть S>=33. Тогда, зная, что S < 55 П может единственным образом разложить произведение (S-31)*31 на два множителя, сумма которых меньше 55, поскольку 31 - простое число. То же самое справедливо для разложения (S-29)*29. Значит, если бы было S>=33, то С не смог бы определить K и L.
Итак,S < 33 - остается 5 кандидатов: 11, 17, 23, 27, 29.
Если Р имеет вид A*2n, где А - простое число, то Р однозначно определяет K и L (равные A и 2n), поскольку из всех сумм 2n-t + A*2t - нечетна только одна (2n + A), а четные суммы - 'запрещены'.
Поэтому, если S двумя способами представимо в виде (2n + A), то S не смог бы назвать K и L. Это соображение позволяет отсеять числа:
11 = 4 + 7 = 8 + 3; 23 = 4 + 19 = 16 + 7; 21 = 2 + 19 = 4 + 17.
Из аналогичных соображений можно отсеять число 29, поскольку
29 = 16 + 23 = 4 + 25.
Если Р = 4 *25, то можно определить K и L (4 и 25), поскольку из всех соответствующих сумм кроме 29 нечетна еще только 25 = 20 + 5, но 25 - 'запрещенная' сумма, так как 25-2 - простое число.
Итак, S = 17. С учетом П.2 находим разложение 17 = 4 + 13, Р = 4*13 - единственным образом (в интересующем нас смысле) разлагается на произведение двух множителей.
MMOnline
[все задачки]
|
Анекдот часа
|
Только в общаге Политеха вместо веревочки на смывном бачке можно увидеть…
>>>
[свежие]
последний: 10.01 10:02
всего анекдотов: 1255
[прислать свой]
|
|
|
ММЗадачка
|
|
|
|