ZXNet эхоконференция «zx.talking»

Get Msg, Ally!

=============================================================================
Прислал: Cтанислав Тихоход (Slowspeed)
=============================================================================

А вот тебе задачка. Ж)

У некоторого царя было два мудреца: Али ибн Вали и Вали ибн Али. Желая
убедиться в их мудрости царь призвал, мудрецов к себе и сказал: "Я задумал 2
числа. Оба они целые, каждое больше единицы. Я перемножил эти числа, и
результат сообщу Али, при этом Вали я сообщу сумму этих чисел. Еще я скажу Али,
что число, которое знает Вали не больше 60. Если вы и вправду мудры, как о вас
говорят, можете сообщить мне эти числа". Мудрецы задумались. Первым нарушил
молчание Али: " я не знаю этих чисел" - сказал он, опуская голову. "Я это
знал!" - подал голос Вали. " Тогда я знаю эти числа" - обрадовался Али. " Тогда
и я знаю!" - воскликнул Вали. И мудрецы сообщили пораженному царю эти числа.
Определите их и вы.

=============================================================================

> Какой ответ?

13 и 4

> А почему?

=============================================================================

Hу я примерно так рассуждал:

Али говорит, что зная произведение он не может сказать числа. То-есть
произведение раскладывается на множители более чем одним способом,
а значит по крайней мере один из множителей - не простое число (очевидно:
не простой множитель сам раскладывается на множители и после перегруппировки
множителей в исходном произведении получаем два других множителя).
Бали в ответ на это говорит, что знал это. Сказать так он может только в том
случае, если известная ему сумма заведомо не может быть суммой двух
простых чисел. Все простые числа - нечетные, за исключением двойки.
Сумма двух нечетных чисел - четное число. Соответственно, сумма, которую знает
Бали - нечетное число (что обеспечивает невозмножность ее получение из двух
простых чисел, не равных двойке) и при этом эта сумма минус 2 не должна
давать простое число.
Тут можно определить множество возможных сумм (они меньше 60, их будет чуть
больше десятка).

11,17,23,27,29,37,...

Далее Али говорит, что в этом случае он знает что это за числа. Так он может
сказать, потому что Бали, сказав, что знал заранее дал Али возможность
определить это множество сумм. Али может представить каждую возможную сумму
из этого набора в виде:

11=2+9,3+8,4+7,5+6 (далее симметрично, игнорируем)
17=2+15,3+14,4+13,...


Далее, перемножая слагаемые (тут я стал писать программку :) он может отыскать
в них известное ему произведение.

11: 2*9=18, 3*8=24, 4*7=28, 5*6=30
17: 2*15=30, 3*14=42, 4*13=52,...

(Всего будет где-то 200 произведений).
То, что он говорит, "тогда я знаю" свидетельствует о том, что известное ему
произведение не появляется после перемножения в строках разных сумм (например,
произведение не может быть равно 30 - 11: 5*6 и 17: 2*15)

Таким образом, мы можем (при помощи программки) вычеркнуть все дублирующиеся
произведения (что-то около
сотни).

После чего Бали говорит "тогда и я знаю". Это значит, что проделав ту же
операцию
он для известной ему суммы нашел только одно произведение (52), и это дало ему
(и нам) 13 и 4.

Возможно объяснение не совсем четкое, но мне его хватило, чтобы с достаточной
долей уверенности быть уверенным в ответе :-)

=============================================================================

* Crossposted in 4311.LOCAL
* Crossposted in ZX.TALKING
* Crossposted in 675.CHAT




[I.ZX] [VR1] ----------------------------> С горячим приветом, Слава!
mailme: copper_feet@mail.ru icq#me: 81191986
[Попробуй нашу бету -- zone.msn.com/fighterace/news/tbltnewsFA3CommBeta.asp]