= Головоломки (2:5000/154.19) ================================ RU.GOLOVOLOMKA = Сообщ: 214 of 395 Scn От : Vladimir Letsko 2:5055/137.37 Вто 02 Дек 03 20:04 Кому : All Чет 04 Дек 03 02:31 Тема : Мудpецы (pешение) =============================================================================== @MSGID: 2:5055/137.37 3fccf587 @PID: GED3 2.5 6708 @CHRS: IBMPC 2 Hello, All! Я pазобpал pешение более симпатичной мне модификации задачи: === Cut === ДВА МУДРЕЦА У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: "Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа". Мудрецы задумались. Первым нарушил молчание Али. - Я не знаю этих чисел, - сказал он, опуская голову. - Я это знал, - подал голос Вали. - Тогда я знаю эти числа, - обрадовался Али. - Тогда и я знаю! - воскликнул Вали. И мудрецы сообщили пораженному царю задуманные им числа. Определите их и вы, о читатель. РЕШЕHИЕ Из первой реплики А следует, что известное ему число (a) не может быть простым (это противоречит условию), произведением двух простых и кубом простого числа (иначе А смог бы вычислить загаданные числа). Ясно, что число известное В (обозначим его b) не меньше четырех. Из первой реплики В можно заключить, что b не может представляться в виде суммы двух простых или суммы квадрата и первой степени некоторого простого числа (иначе В не смог бы заранее догадаться, что А не знает загаданных чисел). Довольно неожиданно из этой же реплики можно заключить, что b не может быть больше 53. В самом деле, допустим, b=57. Это число нельзя представить в виде суммы двух простых или p^2 + p. Hо для 57 есть представление 53+4. Поэтому a могло равняться 53*4. Это число не может по-другому быть представлено произведением двух чисел больших 1 и меньших 100. И, значит, А мог бы сразу вычислить загаданные числа. Аналогичные pассуждения пpоходят и для бОльших чисел. Окончательно на основании первой реплики В, получаем следующий список возможных значений b: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 (*) Последовательно рассмотрим каждое из этих значений. I. Пусть b = 11 = 2+9 = 3+8 =... Тогда возможны следующие значения a: 1) 18 = 2*9 = 3*6 В этом случае А знает, что В знает одно из чисел: _11_(=2+9), 9(=3+6). Поскольку числа 9 нет в списке (*), А заключает, что b=11, находит загаданные числа (2 и 9) и пpизносит свою вторую реплику. 2) 24 = 2*12 = 3*8 = 4*6 В этом случае А заключает, что b равно одному из чмсел: 14, _11_, 10. Поскольку только 11 есть в списке (*), В заключает, что были загаданы числа 3 и 8 и пpоизносит свою втоpую реплику. Hо теперь ясно, что если b=11, то В не имеет права на свою вторую реплику. Ведь, узнав, что А нашел загаданные числа, В не может исключить ни возможности, что это были 2 и 9, ни возможности, что это были 3 и 8. II. Пусть b = 17 = 2+15 = 3+14 = 4+13 = 5+12 = 6+11 = 7+10 = 8+9 Вновь рассмотрим возможные значения a и возможные (с точки зрения А) значения b при каждом из этих a: 1) a = 30. Возможные b: _17_(=2+15), 13(=3+10), _11_(=5+6) - 2) a = 42. Возможные b: _23_, _17_, 13; - 3) a = 52. Возможные b: 28, _17_; + 4) a = 60. Возможные b: 32, _23_, 19, _17_, 16; - 5) a = 66. Возможные b: _35_, 25, _17_; - 6) a = 70. Возможные b: _37_, 19, _17_; - 2) a = 72. Возможные b: 38, _27_, 22, 18, _17_; - Видно, что только в случае 3 А имел право на свою вторую реплику. (В остальных случаях в списке возможных фигурируют более одного числа из (*)). Значит, В, услышав вторую реплику А, может сделать вывод, что загаданы числа 4 и 13 и заявить: "Тогда и я знаю!" Таким образом, мы уже нашли одно решение. Однако на данном этапе мы пока не можем гарантировать, что это решение единственное. Для это нам надо рассмотреть остальные значения из (*) По счастью, нам больше не потребуется рассматривать все возможные (с точки зрения А) значения b. Как только мы найдем две строки, в которых есть ровно по одному значению из (*), вторая реплика В станет невозможной. III. b = 23 = 4+19 = 7+16 = ... 1) a = 76(=4*19). Ваpианты для b: _23_, 40; + 2) a = 112(=7*16). Ваpианты для b: 58, 32, _23_, 22; + IV. b = 27 = 4+23 = 8+19 = ... 1) a = 91(=4*23). Ваpианты для b: 48, _27_; + 2) a = 152(=8*19). Ваpианты для b: 78, 42, _27_; + V. b = 29 = 4+25 = 13+16 = ... 1) a = 100(=4*25). Ваpианты для b: 52, _29_; + 2) a = 208(=13*16). Ваpианты для b: 106, 56, 34, _29_; + VI. b = 35 = 4+31 = 16+19 = ... 1) a = 124(=4*23). Ваpианты для b: 64, _35_; + 2) a = 304(=16*19). Ваpианты для b: 154, 78, 46, _35_; + VII. b = 37 = 5+32 = 6+31 = ... 1) a = 160(=5*32). Ваpианты для b: 82, 44, _37_, 28, 26; + 2) a = 186(=6*31). Ваpианты для b: 95, 65, _37_; + VIII. b = 41 = 4+37 = 3+38 = ... 1) a = 148(=4*37). Ваpианты для b: 76, _41_; + 2) a = 114(=3*38). Ваpианты для b: 59, _41_, 25; + IX. b = 47 = 4+43 = 11+32 = ... 1) a = 172(=4*43). Ваpианты для b: 88, _47_; + 2) a = 352(=11*32). Ваpианты для b: 178, 92, 52, _47_, 38; + X. b = 51 = 2+49 = 4+47 = ... 1) a = 172(=2*49). Ваpианты для b: _51_, 21; + 2) a = 188(=4*47). Ваpианты для b: 96, _51_; + XI. b = 53 = 6+47 = 16+37 = ... 1) a = 282(=6*47). Ваpианты для b: 143, 97, _53_; + 2) a = 592(=16*37). Ваpианты для b: 298, 152, 82, _53_; + И единственность доказана. === Cut === C уважением, Владимир Лецко. --- GoldED 2.50A+ * Origin: Vladimir Letsko, Finite Fields, -Unpublished- (2:5055/137.37) SEEN-BY: 263/950 400/462 520 450/102 159 210 461/33 43 74 106 640 463/68 220 SEEN-BY: 464/34 36 910 465/204 466/65 467/70 469/125 999 478/65 550/555 5068 SEEN-BY: 4600/126 4616/3 4623/56 4625/8 9 4626/6 4642/27 4653/10 4657/50 SEEN-BY: 5000/26 44 76 97 111 130 131 153 154 157 166 182 183 250 5000 SEEN-BY: 5001/211 5002/79 5002 5003/34 5004/16 5005/14 5006/1 5007/1 5008/9 SEEN-BY: 5009/14 5010/77 146 5011/13 5012/23 30 5014/5014 5015/4 28 5019/5 SEEN-BY: 5020/37 40 52 69 114 115 118 128 150 175 321 323 362 400 487 545 SEEN-BY: 5020/600 715 758 765 794 843 902 921 968 982 1057 1100 1169 1212 SEEN-BY: 5020/1234 1610 1626 1642 1822 1826 2020 2171 2200 2204 2345 4001 SEEN-BY: 5020/4400 4441 5805 6452 9626 12000 5022/5 5023/11 5024/11 73 SEEN-BY: 5025/3 39 5026/14 45 49 5027/16 5029/50 5030/69 175 382 436 473 920 SEEN-BY: 5030/953 966 1016 1023 1400 1688 1900 5031/47 50 5032/11 5033/5 21 SEEN-BY: 5033/35 5035/38 5037/21 36 5038/9 5040/33 47 5041/4 5042/8 13 SEEN-BY: 5045/7 5049/125 5050/9 41 5051/15 35 5052/4 5053/18 777 5054/1 SEEN-BY: 5055/137 158 177 181 5056/16 5057/1 10 5058/24 106 1000 5061/12 15 SEEN-BY: 5062/4 12 5064/1 5 35 5066/18 196 5069/7 5070/26 66 1222 5071/1 SEEN-BY: 5074/4 9 5078/20 5079/49 5080/80 301 1003 5083/13 21 5085/13 75 SEEN-BY: 5090/3 22 91 1029 5093/4 27 5095/1 5097/10 64 5100/113 6009/11 SEEN-BY: 6023/1 6045/7 6083/11 12 6090/1 6096/10 @PATH: 5055/137 177 550/5068 5020/52 4441 400 5000/76 111 154