Найти числа по их сумме и произведению
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: "Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа".
Мудрецы задумались. Первым нарушил молчание Али.
- Я не знаю этих чисел, - сказал он, опуская голову.
- Я это знал, - подал голос Вали.
- Тогда я знаю эти числа, - обрадовался Али.
- Тогда и я знаю! - воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Мудрецы задумались. Первым нарушил молчание Али.
- Я не знаю этих чисел, - сказал он, опуская голову.
- Я это знал, - подал голос Вали.
- Тогда я знаю эти числа, - обрадовался Али.
- Тогда и я знаю! - воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Ответ
Рейтинг: : 13 и 4
+161
Комментарии:
:), 2009-11-24
Почему 13 и 4?
Как это можно узнать из условий задания?
я точно НЕ ас в математике
root, 2009-11-25
Вот я не совсем понел ...
я так понел каждый из мудрецов знал только свой финал
1-й знал только сумму.
2-й только результат перемножения .
Так ...?
Если так то я совсем не понимаю как можно найти два статических числа зная только что их сумма равна ... например 84 .
Kira, 2009-11-25
Задача конечно делает должное - заставляет мозг думать, но решения как такогого здесь нет. решением могут быть и другие два числа - например 26 и 2...≈EBГEHИЙ, 2009-11-25
Чтобы можно было угадать числа, зная их произведение, нужно чтобы оно раскладывалось на множители единственным образом.
Bали сказал, что он заранее знал, что Aли не сможет определить числа, значит, сумму чисел нельзя получить суммируя простые числа.
Более того, сумма двух чисел, меньшее из которых по условию может достигать 98 не превосходит 53.flur_deema, 2009-11-26
задача явно попала не в тот раздел.denvit, 2009-11-28
Прикольная задача. Сам решить не смог, но когда узнал ответ, сразу стало ясно.
Вали увидел результат 17. Это нечетное число, его можно получить только в результате сложения четного числа с нечетным, в остальных случаях сумма всегда будет четное число. А это означает что произведение, которое есть у Али (четного с нечетным числом) будет всегда четное. А если произведение четное, то оно всегда имеет как минимум два решения (2n*1 и n*2, где n – это половина произведения), то есть Али точно не сможет точно угадать эти числа.
Когда Вали об этом заявил, Али догадался, что одно число должно быть четное, а другое нечетное. Его произведение 52 имело два решения(так как числа по условия целый и больше 1) 2*26 и 4*13. + подсказка Вали, значить правильный вариант 4*13
Вали поняв, что с вывода про парное и непарное число Али получил точный результат. Считает так: пусть одно число 2х(это четное), второе 2у+1(нечетное), тогда их сумма 2х+2у+1=17, х+у=8. Возможные варианты (х=2,у=6), (х=3,у=5), (х=4,у=4) им соответствуют числа (4,13),(6,11),(8,9). То есть произведения 52,66,72. Так как Али знает числа, значит произведение только одним способом разлаживается на одно четное число и одно нечетное. 52- подходит(проверено выше), 66 –нет(2*33,6*11 – два варианта),72-нет(8*9 и 24*3- два варианта). Значит правильные числа 4 и 13
(извините в первом ответе неправильное мыло)spirt, 2009-11-29
всё равно не понял,как из условия задачи понять что это за числа и при чём тут чётные нечётные,интересно кто то решил её сам?Гога, 2009-11-29
Лажа. Почему Вали услышал 17? Может он услышал 19 или ещё какое-нибудь. А если 17, то числа может 10 и 7. Ваши рассуждения подогнаны под ответ.Рафаиль, 2009-11-30
3 и 6 тоже подходят
для решения нужно знать или сумму или произведения
а так мнгие пары чисел подойдут≈EBГEHИЙ, 2009-11-30
Али(знает произведение):
- Я не знаю этих чисел
\\потому что ему сказали составное число\\
Вали(знает сумму):
- Я это знал
\\потому что ему сказали число, которое не может быть представлено суммой двух простых чисел\\sven, 2009-12-05
Друзья, поправьте, если я неправ, но мне кажется, что задача либо не имеет решения либо условие представлено некорректно. Попробую объяснить свою точку зрения:
Итак, Али, зная произведение чисел, в любом случае скажет, что не знает самих чисел (исключая, конечно, варианты, когда числа вычисляются сразу же: к примеру, произведение равняется 10, то есть в любом случае искомыми числами будут 5 и 2, 14 - 7 и 2 и т.д.) Если же известное Али число имеет несколько делителей ( ну, к примеру, 12 - 4 и 3 или 6 и 2 или, что ближе к ответу задачи, 30 - 5 и 6 или 15 и 2), то он В ЛЮБОМ СЛУЧАЕ скажет, что не знает ответа.
Теперь Вали, услышав ответ Али, должен сказать свое мнение. При этом он знает, что сумма чисел равна (в данном случае) 17. Вариантов - море. Например, Вали может предположить, что это числа 15 и 2. Их произведение дает 30, но и в этом случае Али сказал бы, что не знает ответа, поскольку при его данных возможны 3 варианта: 5 и 6, 10 и 3, 15 и 2. Если бы диапазон искомых чисел ограничивался 30-ю, то мудрецы, безусловно, нашли бы ответ. Но ведь с таким же успехом Вали может предположить, что эти числа - 14 и 3, а их произведение уже будет 42, и Али, зная эту цифру, все равно сказал бы, что не знает ответа, потому что у него были бы варианты 6 и 7 либо 21 и 2. Точно так же с ответом, указанным в задаче: 13 и 4 дает произведение 52, что возможно при умножении как самих 13 и 4, так и 26 и 2. И так далее. То есть, Вали просто не может сделать правильную предпосылку, услышав ответ Али о том, что он не знает загаданных чисел. И, естественно, он также скажет, что не знает ответа. Ну, а каким образом Али догадается, что искомые числа есть 13 и 4 - это уже тайна за семью печатями. При любом из перечисленых мною вариантов ( а также при еще большем количестве мною не перечисленных) каждый из мудрецов должен предполагать не единственный вариант решения, то есть они просто не смогут дать ответ.
С интересом прочитаю другие мнения.mckoy, 2009-12-08
Вся суть в 4 строках (это шаги):
1. Я не знаю этих чисел - ответ который отбрасывает все числа которые есть произведениями простых;
2. Яэто знал - ключевая фраза, Вали не знает пока ответа, но! он по своему числу точно знает,что Али ответа не знает. Как? да очень просто, у него непарное число, которое можно получить только одним способом: сумма парного и непарного, которые в произведении всегда являються парним числом (причем одно из чисел точно не 
);
3. Тогда я знаю эти числа - исходя из ответа Вали, Али понял что число у Вали непарное. А так как эту фразу Али может скажать только! когда есть 2 варианта разложения и 1 он исключает, то соответственно числа выходят 13 и 4 - это единственый вариант! удовлетворяющий условию.
4. Тогда и я знаю - ну а эта фраза ясна сама собой, после всего сказанного.
Вот так вот!Гога, 2009-12-09
"А так как эту фразу Али может сказать только! когда есть 2 варианта разложения и 1 он исключает".
Неубедительно. Эту фразу он может сказать когда и три варианта разложения. И таких вариантов много.abylai, 2009-12-09
я не уверен в своем ответе, но поытаюсь изложить свою точку зрения; так как Али сказал что знает ответ только после того как Вали сказал что он ето знал, Али должно было понимал что ответы у них должный быть одинаковыми, ето означает что сумма и произведение етих чисел одинаковы, а такими числами между 1 и 100 могут быть только 2, т.е. 2+2=4 и 2*2=4
поэтому я считаю что ответом являются 2 и 2mckoy, 2009-12-10
Гога: "Неубедительно. Эту фразу он может сказать когда и три варианта разложения. И таких вариантов много."
какую эту? Он говорит что ТОЧНО знает эти числа. Если вариантов разложения 3, а исключает он один, то точно он никак не будет знать. Соотвественно не сказал бы эту фразу.pont, 2009-12-12
все числа от одного до ста!!!!!!!!!!!!!!!!!!!!!!!!!!sven, 2009-12-17
Ну, не знаю, попробую поспорить с mckoy.
Первые два суждения (шага) в любом случае абсолютно верны. Шаг первый - Али не знает этих чисел и шаг второй - Вали это знает. Но вот предпосылок для того, чтобы Али сказал, что он что-то знает - ну не вижу я абсолютно.
Давайте подойдем к ситуации с позиции Вали: он видит, что сумма цифр равна 17, и у него возникает энное количество вариантов. Али при этом в любом случае говорит, что не знает искомых чисел. Давайте, к примеру, возьмем числа 15 и 2. Чем они не удовлетворяют условию задачи?
Шаг 1-й: Али, видя произведение 30, предполагает, что искомыми числами могут быть 6 и 5, 10 и 3, 15 и 2. И он, естественно, говорит, что не знает этих чисел.
Шаг 2-й: Вали, видя перед собою сумму 17, вполне может предположить, что заданные цифры есть 15 и 2. Предполагая, что это так, он в любом случае понимает, что Али, видя произведение 30, говорит, что не знает искомых чисел (см. выше). И поэтому Вали заявляет, что он это знал. Но, простите, с какого перепугу Али вдруг выстреливает фразу, что ему числа известны? Ведь он всего лишь знает, что сам он в тупике, а Вали об этом знает. А таких вариантов как минимум несколько ( приводить их долго и занудно), в том числе и вариант, указанный в ответе.
Уважаемый mckoy, я не математик, возможно, могу ошибаться. Но, честно говоря, пока не понимаю логики решения задачи.
С уважением.
mckoy, 2009-12-21
Твоя ошибка в том, что ты считаешь что Султан мог загадать лубые числа. ЭТО НЕ ТАК.
Султан загадывает числа, чтобы можно было отгадать, иначе нет смысла проверять мудрецов.
Отгадать можно только, когда число раскладиваеться так чтобы было ТОЛЬКО 2 произведения, одно из которых можно исключить.
В твоем примере таких произвидений 3 - и все ты написал!Эмиль, 2010-01-01
Мне почему-то казалось,что тут дело в их именах.Они звучат противоположно,т.е. цифры должны были быть mn и nm,также как Али-ибн-Вали и Вали-ибн-АлиАлександр, 2010-01-07
Не полный вариант решения.
Фраза Али означает, что загаданные числа не простые.
Фраза Вали означает, что данное ему число (сумма х и у) не может быть представлено суммой простых чисел. Эта фраза отметает кораздо большее число пар чисел, чем фраза Али:
у Вали не может быть четное число (бинарная проблема Гольдбаха - четное число больше 4 представимо суммой простых) и нечетное число типа 7=5+2, 15=13+2 и др.
4 не подходит: Оно представимо в виде суммы пар 3,1 и 2,2. Если бы Вали сказали 4, он бы сразу назвал султану числа.
Следовательно, х или у делится на 2 (но не оба вместе).
Число, данное Али представляет собой произведение некоторого количества простых множителей.
2 множителя быть не может, иначе он бы сразу назвал число.
3 множителя: а,б,в. 3 варианта пар чисел: (в аб) (ва б) (вб а).
Будем искать среди троек, когда два множителя совпадают. Если это не так или множителей больше 3, то слишком много вариантов получается, все кроме одного одним заявлением Вали не отметешь.
Если не найдем среди этих троек, будем искать дальше. Найдем - решим задачу.
Учитывая, что один из множителей - 2, получаем пары чисел вида:
(2 аа) (4 а) (2а а)
Причем, число, данное Вали представимо этими числами единственным образом. В противном случае он бы не угадал искомые числа.
Например для 11:
11=2+3*3 (первый вид). У Али 18. 6 и 3 он отбрасывает, потому что 9=2+7 - представимо в виде суммы простых чисел, а ему сказали, что это не так.
11=4+7 (второй вид). У Али 28. 14 и 2 он отбрасывает, потому что 16- четное, представимо в виде простых чисел.
Перебираем. Первое число, которое представляется в указанном виде единственным образом - это 17.
17=13+4. У Али 52
26+2=28 - четное число, пара (2 26) отбрасывается после заявления Вали.
Ответ - 4 и 13.
Как я и предупреждал, вариант решения - не полный. Например, не доказана единственность решения. Предложен метод перебора с ограниченным числом вариантов.
Наталья, 2010-01-20
Всем кажется, что ответ неполный, потому что никто(кроме Александра) не обращает внимание на четвертое условие. Заявление "Тогда и я знаю". Оно для проверки самое сложное, если идти прямым перебором. Разумеется чисел удовлетворяющих первым трем условиям гораздо больше, важно что и Вали(которому бедному пришлось делать гораздо больше вычислений, чем Али) смог узнать эти числа. А это значит, что все, кроме одного разбиения его числа на сумму двух слагаемых(исключая 1 + n-1) не удовлетворяют цепочке из первых трех условий.
Задача классная. Думаю, что решается она перебором, исключая сразу достаточное число вариантов. Степень смекалки пропорциональна количеству исключений. vanadium23, 2010-01-22
Решение этой задачи полностью написано в книжке Уфнаровский В. А. Математический аквариум, так что если чего-то не поняли гугл в помощь)фаридун, 2010-02-22
я не совсем понял этими числами могут быт и другие числа например 4 и 7nkul, 2010-03-13
На мой взгляд 19 и 4 подходят также. 23 - не представимо суммой двух простых чисел, 76 раскладывается на два множителя только двумя способами - (19, 4) и (38, 2).nkul, 2010-03-13
To vanadium23: D книжке Уфнаровский В. А. Математический аквариум приведено решение совсем другой задачиnkul, 2010-03-13
43 и 4, 61 и 4, 67 и 4, 73 и 4, 79 и 4, 83 и 4, 89 и 4, 93 и 4, 97 и 4.pshenya, 2010-04-27
Nkul, 23 как сумма не подходит. Мудрец Вали (знающий сумму) в конце не сможет определить, равно ли произведение 76=4*19 или 112=7*16. Виктория, 2010-07-08
Логику я поняла четко, но вот только не могу понять, почему под эту логику не подходит пара чисел 3 и 8? Объясните, пожалуйста....nkul, 2010-07-08
To Виктория: Вали в конце не может выбрать между парами (8,3) и (9,2)Виктория, 2010-07-08
согласно denvit, предложившему(ей) наиболее на мой взгляд удобоваримое решение, "Вали поняв, что с вывода про парное и непарное число Али получил точный результат. Считает так: пусть одно число 2х(это четное), второе 2у+1(нечетное), тогда их сумма 2х+2у+1=17, х+у=8. Возможные варианты (х=2,у=6), (х=3,у=5), (х=4,у=4) им соответствуют числа (4,13),(6,11),(8,9). То есть произведения 52,66,72. Так как Али знает числа, значит произведение только одним способом разлаживается на одно четное число и одно нечетное. 52- подходит(проверено выше), 66 –нет(2*33,6*11 – два варианта),72-нет(8*9 и 24*3- два варианта)." А если следовать этой логике, по-моему 3 и 8 тоже подходят.Виктория, 2010-07-09
Просто получается, что 3 и 8 - произведение 24, которое дает чет*нечет только 3*8 [2*12 и 4*6 - по два четных], а 2 и 9 - произведение 18, которое дает два таких варианта - 2*9 и 3*6!! Вот по идее так Вали в конце и должен отобрать из этих двух вариантов...nkul, 2010-07-10
To Виктория: 3*6 отбрасывается т.к. 9 представимо в виде суммы двух простых чисел 2+7, следавательно после "- Я это знал, - подал голос Вали" Али, если у него 18, может смело сказать, что искомые числа 2 и 9. А вот Вали со своими 11 не сможет выбрать между (2,9) и (8,3).Виктория, 2010-07-10
упс...дошло=((leotrubach, 2010-07-23
Задачка очень красивая. Итак, решим ее.
В каких случаях эти числа можно было бы угадать? В том случае, если произведение этих чисел раскладывается на два простых множителя.
Раз Вали знал, что Али не отгадает, значит сумма, сказанная ему султаном, не является суммой двух простых чисел.
Находим суммы всех простых чисел, не превышающие 100:
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97]
pos_sums = set(range(4, 100))
lps_lt_100 = []
for x in primes:
for y in primes:
r = x + y
if r < 100:
lps_lt_100.append(r)
ps_lt_100 = set(lps_lt_100)
sums_s = pos_sums - ps_lt_100
В множество sums_s входят числа, которые не могут быть суммой двух простых чисел. Таковыми являются:
11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97
Теперь рассмотрим реплику Али - тогда я знаю эти числа, и ответ Вали - тогда и я знаю.
Создадим множества произведений всех возможных слагаемых из которых состоит каждое из вышеуказанных чисел. Угадать оба мудреца смогли бы в том случае, если в множестве существует одно и только одно число, которое не встречается в других множествах. Вот код, который это выполняет:
def possible_pairs(n):
for i in range(2, n//2 + 1):
yield (i, n-i)
mults = []
for n in sums_s:
mults.append(list(possible_pairs(n)))
pos_mults = [set([x*y for x, y in l]) for l in mults]
for i in range(len(pos_mults)):
s1 = pos_mults[i]
others = pos_mults[:i] + pos_mults[i+1:]
s2 = set.union(*others)
print(s1 - s2)
И вот что выдала нам программа:
{24, 18, 28}
{52}
{112, 76}
{176, 152, 50, 140, 92}
{208, 100, 54, 198}
{96, 294, 234, 304, 216, 250, 124}
{160, 232, 336}
{288, 418, 238, 400, 148, 348, 414}
{480, 172, 496, 246, 280, 442, 510}
{608, 578, 644, 230, 518, 650, 620, 98, 494, 144, 308, 344, 468, 188, 638}
{672, 646, 520, 682, 492, 430, 592, 700}
{800, 432, 260, 806, 392, 810, 812, 782, 656, 722, 212, 470, 740, 506, 572, 350}
{864, 688, 738, 868, 220, 814, 528, 564, 598, 760, 828, 318}
{1056, 1026, 676, 1014, 456, 874, 1036, 354, 846, 784, 1000, 1044, 750, 406, 984, 244, 636}
{192, 1120, 742, 1032, 940, 366, 912, 1012, 472, 1116, 990}
{448, 1248, 610, 1188, 1078, 880, 1128, 1258, 268, 558, 1104, 754, 1204, 918, 1240, 708, 954, 1150}
{1410, 1426, 1300, 1176, 670, 1440, 930, 292, 1062, 426, 1452, 1462, 1210, 832, 1476, 1480, 976, 726, 1372, 222, 1392, 1272}
{960, 1504, 1378, 804, 438, 1288, 748, 1098, 1548, 1488, 1320, 1558, 568, 228, 1008, 1180, 1530, 1404}
{1216, 1072, 1666, 1590, 1416, 316, 1612, 730, 1680, 600, 1716, 1342, 1302, 1720, 852, 666, 1692, 1722, 1566, 1632}
{1802, 1550, 1682, 1430, 1190, 1586, 1850, 1340, 1472, 962, 836, 1862, 1736, 332, 1872, 1620, 1880, 1886, 1760, 1892, 486, 1136, 1652, 632, 1022}
{258, 1924, 1798, 1674, 1168, 1938, 790, 1824, 1960, 1708, 1968, 1330, 1974, 1848, 1978, 574, 1600, 1474, 1224, 1740, 1870, 720, 1638, 1770, 498, 1908, 1278}
{1922, 2052, 902, 1040, 2072, 1562, 1952, 1700, 2090, 1460, 2106, 830, 1856, 2120, 1610, 972, 1742, 1232, 1106, 2132, 2006, 356, 2150, 2156, 2030, 2160, 2162, 1406}
{1794, 774, 2184, 534, 2200, 2074, 1444, 2214, 1704, 1200, 2226, 2100, 2236, 1984, 2244, 1606, 2250, 2124, 2254, 2256, 1876, 1750, 1500, 2016, 2146, 996, 1134, 1264, 2166, 1914}
{2310, 1800, 1162, 1932, 1422, 1296, 2322, 2196, 2332, 2080, 2340, 2346, 2220, 2350, 2352, 1972, 1846, 1596, 2112, 2242, 712, 460, 1360, 2262, 1752, 2010, 2280, 372, 2296, 2170}
Множество с одним элементом у нас одно - {52}
Решаем систему уравнений:
xy=52
x+y=17
Находим, что числа - 13 и 4 sven, 2010-10-28
Подводя итоги. Один товарищ на суде, отстаивая свою точку зрения, выдал: "Юриспруденция не признает такого понятия, как здравый смысл..." (Оговорка: фраза передана дословно, но вырвана из контекста). Как я понял, математика - тоже.Димон, 2010-11-19
Решил, эту задачу сам, правда пропарился над ней пару дней на парах =) Ход рассуждений таков:
1. если Али не знает чисел, значет произведение имеет минимум 2 варианта (перебираем эти числа)
2. если Вали это знал, значит его произведение раскладывается только на многовариантные призведения (перебираем)
3. если Али это помогло, значит в его произведении только один вариант даёт такую сумму как в пункте 2
4. если теперь и Вали знает числа, значит только один вариант чисел из его суммы имеет только одно решение соглласно пункту 3, а остальные - многовариантные...
В итоге пришёл к числам 4 и 13
Надеюсь всё понятно написал?))Владимир, 2010-12-06
Объясните пожалуйста, почему не подходят числа 16 и 13?Ред, 2010-12-14
Объясните, пожалуйста, момент, связаннный с этой задачей.
Вариант 4 и 13.
Первый визирь не знает числа, так как 52 может делиться также на 26 и 2, что в сумме дает 28.
Второй говорит, что знает, что тот не знает.
Первый понимает, что у второго сумма равна 11 или 17 или т.д. из списка. То есть он отметает 26 и 2, т.к. в сумме они дают не 17. Следовательно, первый понмиает, что числа - 4 и 13.
Однако как данный вывод сделать ещё второму?
Ведь он знает только сумму. 17. А она может состоять из слагаемых 6 и 11. И таким образом у первого может быть произведение 66.
Объясните, плиз, а то второй день голову ломаю.Настя, 2011-01-08
Задача супер!!!
Сложная конечно, но за час я её решила!!!Евгений, 2011-02-01
Али сказали 52(26*2 или 13*4) их сумма (28 или 17)соответственно. Вали сказали 17. По-моему они так догнали что к чемуНадежда, 2011-02-13
из 1)-го следует, что произведение имеет более 2-х простых множителей
из 2)-го следует, что сумма нечетная
из 3)-го следует, что первое число имеет вид 2^k, а второе - простое
из 4) - следует, что представление суммы в виде у+2^k возможно едиственным образом
и из этого всего можо не сложно найти ответ777, 2011-03-04
я не понела!!!777, 2011-03-04
настя как ты задачу решилаaserel, 2011-03-13
задача элементарная
решали всю ночь бригадой
мое решение следующее: любое число можно делить на простые числа до тех пор, пока не останется простое число. следовательно, произведение двух простых чисел a*b можно легко разложить на множители...
у Али сомнения возникли потому, что в произведении было как минимум три множителя... следовательно он не мог выделить из них два числа...
дальше посложнее...
сумма...
имея как минимум три простых множителя в произведении a*b*c можно составить следующие выражения сложения: a*b+c, a*c+b, c*b+a... !
если бы у Вали с разложением слагаемого, состоящего из двух множителей и возникли проблемы, следовало бы, что оно состояло бы из трех множителей минимум, а такого не возникло... "я знал" - сказал он. знал, что множителей у Али три и не больше, но вариантов несколько...
но! все три числа простые... стоят в ряду простых чисел... и при вычитании из суммы, сказанной Вали, всегда получается произведение еще двух простых чисел... можно сделать вывод, что это 4 и 13... где 4=2*2... в этом легко убедиться иных вариантов нетaserel, 2011-03-13
при вычитании из суммы имеется ввиду вычитание из любого числа из ряда простых чисел... потому что всё решение сведено к простым числам...aserel, 2011-03-13
де блин... вычитание из суммы любого числа из ряда простых чисел... Мария, 2011-03-16
напишите полное решение задачи!!!
Sasha, 2011-06-21
Товарищи, на самом деле вы не решаете задачу доконца, а доходите до середины, а дальше проверяете ответ. Я встретил эту задачу на другом сайте и (как я считаю решил), но в поисках сравнения своего варианта с альтернативными, набрел на этот сайт. Начало моих рассуждений совпадает с вашими, потому не буду очень сильно расписывать
1) мудрец А видит число которое раскаладывается более чем на два простых множителя.
2) мудрец В видит непарное число и потому понимает что одно из чисел в любом случае непарная, а значит из произведения нельзя однозначно назвать эти числа.
3) мудрец А понимает что у мудреца В непарное число и тогда он может назвать свои числа только в том случае. если он может разложить свое чело на непарный и парный множитель только одним способом. Что это дает? То что если разложить число на простые множители среди них не должно оказаться 2 простых (и более) числа отличных от двойки и хотябы одна двойка (мы помним что множителя должно быть хотя бы 3). Двойка нам нужна чтобы получить парное число при умножении. Почему только одно простое число отличное от двойки? Потому что при наличии хотя бы 2 простых чисел отличных от двойки, мы получим хотя бы два варианта пары чисел парное+непарное. А в этом условии нам накладывается однозначность. Таким образом среди множетелей должно бить должно быть только одно простое число отличное от двойки и 2+n двоек, где n - натуральное число от 0 и ...(верхнюю границу не будем определять пожалуй).
Вариантов много на єтом этапе:
3 2 2 (двойки можно дописывать)
5 2 2 ...
7 2 2....
и т.д.
3) Следующее ограничение. Мудрец В понял что это за числа тоже. Что это означает? Что его сумма содержит только один вариант из множества чисел описанных выше.
И того:
решением нашей задачи будет пара чисел произвелдение которых раскладывается на хотябы 3 простых множителя, а сума однозначно раскладывается на на одино простое число отличное от двойки и степень двойки, начиная с 4 (то есть 4,8,16,32 и т.д.)
Решение далеко не одно. Я не стал искать всех, остановился только на первых:
3 и 4
5 и 8
13 и 4
и т.д.
Можете еще попробовать подобрать. Алгоритм довольно простой. можно даже написать программу.Kropotkin, 2011-07-21
Sasha, забавно, но я тоже на днях столкнулся с этой задачей и я тоже, не заглядывая в ответы, пришел к похожему на твой алгоритму. Однако мой критерий - более жесткий. У меня получилось, что одно из чисел должно быть равно 2 в натуральной степени большей единицы (обозначим его z), а второе число либо простое, либо составное, но такое, что при умножении любого его множителей на z получается число меньшее 100. Соответственно, сумма этих чисел должна быть нечетным числом, единственным образом разлагающиееся на два подобных числа и НЕ разлагающееся на два и простое число большее двух (иначе возникает возможность однозначно разлагаемого произведения). Соответственно, в начале числового ряда сразу отбрасываем 5, 7,9, 13, 15 по проостейшему критерию (допускают разложение на 2 и простое число) и уже 17 единственным способом разлагается на два в степени и простое число (4 и 13). Дальше, действительно, непонятно. Ведь таким же образом, этому критерию соответствуют, скажем, 8 и 29 или 37 и 16. Kropotkin, 2011-07-21
Ошибка: "такое, что при умножении любого его множителей на z получается число БОЛЬШЕЕ 100"Stix, 2012-01-11
Sasha, ваши рассуждения выглядят наиболее убедительными, вопрос в том, что вариант 3 и 4 не похож на правду, потому что в таком случае Али знал ответ сразу после первой фразы Вали, т.к. сумма 7 могла получиться только как 5+2 или 3+4, но так как Али не знает ответа сразу, то это точно не 5+2 (сумма 10 получается единственным способом), а значит Вали не нужно условие, что Али догадался, что это за числа (3-е утверждение), т.к. он знал ответ уже после первой фразы Вали, то есть его ответ был бы не "Тогда я знаю!" а что-то вроде "Я и так знал"
Я пытался решать эту задачу сам и нашёл ответ 8 и 5, почитав комменты увидел другой, но так и не смог убедиться, что мой неверный
Возможно для единственности ответа необходимо ещё дополнительное условие от Султана, например, в каком диапазоне лежит сумма загаданных им чисел, например, от 5 до 16, если не знать хода решения, то вариантов всё равно предостаточно и полный перебор будет довольно утомительнымАндрей, 2012-01-20
Введем понятие хорошего числа.
Натуральное число от 5 до 197 (минимальная и максимальная суммы в рамках нашей задачи) называется хорошим, если путем
разложения этого числа на два слагаемых (каждое из которых больше единицы) нельзя получить пару простых чисел.
Например:
== 7 ==
7 = 2 + 5; 2 * 5 = 10
7 = 3 + 4; 3 * 4 = 2 * 6 = 12
Пару (2, 5) образуют два простых числа, следовательно, 7 не является хорошим числом.
== 11 ==
11 = 2 + 9; 2 * 9 = 3 * 6 = 18
11 = 3 + 8; 3 * 8 = 2 * 12 = 4 * 6 = 24
11 = 4 + 7; 4 * 7 = 2 * 14 = 28
11 = 5 + 6; 5 * 6 = 2 * 15 = 3 * 10 = 30
Таким образом, 11 - хорошее число - ни одно из разложений числа 11 по слагаемым не дало пары простых чисел.
Согласно гипотезе Гольдбаха, проверенной до 18-го порядка натуральных чисел, каждое четное число представимо в виде суммы
двух простых. Отсюда вывод - все четные числа не являются хорошими.
В силу того, что четное число 2 является простым, мы также можем заключить, что все числа из нашего диапазона,
удовлетворяющие условию n = p + 2, где p - простое, также не являются хорошими.
Очевидно, что исключив из чисел 5 .. 197 все четные, а также нечетные вида p+2, у нас останутся лишь хорошие числа.
Полный список выглядит немного громоздко, приведу лишь его начало:
11 17 23 27 29 35 37 41 47 51 53 57 59...
Перейдем непосредственно к задаче.
1. Али не знает n и m, что означает, что хотя бы одно число из пары является составным (не простое).
2. Вали говорит, что знает об этом. Отсюда следует, что сумма, полученная Вали от султана - хорошее число, т.к. если
число Вали не является хорошим, то он не может быть убежден в том, что Али не может определить числа по произведению.
Например, у Вали не может быть числа 31, т.к. 31 можно представить как 29 + 2 - парой простых чисел. Их произведение 58
однозначно подсказало бы Али ответ задачи, что противоречит пункту 1.
3. Али определил исходную пару чисел после ответа Вали. Введем еще одно понятие. Пусть натуральное число n имеет k различных разложений на два неравных множителя больших единицы: n = a1 * b1 = a2 * b2 = ... = ak * bk. Тогда n будем называть красивым числом, если из множества чисел Si = ai + bi, i = 1..k, ровно одно Si является хорошим числом. Рассмотрим, к примеру, число 18. Оно имеет два разложения по множителям: 18 = 2 * 9 = 3 * 6; 2 + 9 = 11; 3 + 6 = 9. 11 - хорошее число, 9 - нет, следовательно, 18 - красивое число.
Из условия данного пункта очевиден тот факт, что произведение Али - красивое число. Али известен тот факт, что сумма Вали - хорошее число, таким образом для однозначного определения пары искомых чисел он вначале методом перебора определяет эту сумму исходя из всевозможных сумм делителей своего числа. Если среди сумм его делителей хорошего числа не найдется либо будет больше одного, он не сможет определить загаданные числа наверняка.
Поиск красивых чисел является довольно трудоемким занятием, предложу такой алгоритм для определения первых нескольких значений: выписываем в строчку всевозможные произведения слагаемых для нескольких первых хороших чисел:
11 -- 18, 24, 28, 30
17 -- 30, 42, 52, 60, 66, 70, 72
23 -- 42, 60, 76, 90, 102, 112, 120, 126, 130, 132
27 -- 50, 72, 92, 110, 126, 140, 152, 162, 170, 176, 180, 182
29 -- 54, 78, 100, 120, 138, 154, 168, 180, 190, 198, 204, 208, 210
35 -- 66, 96, 124, 150, 174, 196, 216, 234, 250, 264, 276, 286, 294, 300, 304, 306
37 -- 70, 102, 132, 160, 186, 210, 232, 252, 270, 286, 300, 312, 322, 330, 336, 340, 342
...
Если какое-либо число появляется более, чем в одном ряду - вычеркиваем его.
Все невычеркнутые числа, не превосходящие 2 * (2z - 2) будут красивыми, где z - последнее взятое для выборки хорошее число.
В нашем случае z = 37, а 2 * (2z - 2) = 70 - это первое число последнего ряда.
После вычеркивания повторных чисел у нас останется набор:
18 24 28 50 52 54 ...
4. Вали определил загаданные числа после того, как Али подтвердил, что знает их. По аналогии с предыдущими определениями дополним нашу теоретическую базу отличными числами. Хорошее число n называется отличным, если из всех k разложений числа n на два слагаемых: n = a1 + b1 = a2 + b2 = ... = ak + bk, ровно одно число Pi = ai * bi является красивым. Как нетрудно догадаться, число Вали удовлетворяет этому условию. По аналогии с пунктом 3, Вали перебирает все возможные варианты произведений, которые могут быть у Али и дает ответ лишь в случае, когда ровно одно произведение удовлетворяет условиям, описанным выше, т.е. когда ровно одно число является красивым.
Таким образом, задача сведена к следующей: найти два натуральных числа от 2 до 99, чья сумма является отличным числом.
Обращаясь к проделанным выше вычислениям, можно видеть, что 11 определенно не является отличным числом, а 17 является. Что касается остальных чисел, их следует обрабатывать при помощи компьютера либо предложить аналитический алгоритм.
Поскольку "сопряженным" красивым числом для отличного числа 17 является число 52, можно составить систему уравнений и вычислить одну пару решений - 4 и 13.
Открытым остается вопрос о существовании отличных чисел, превосходящих 17. В силу того, что в последовательности простых чисел нельзя выделить аналитическую закономерность, то же самое можно сказать и о хороших/красивых/отличных числах. Наиболее оптимальным вариантом мне видится обработка всех чисел вида 10k + 7 (все они являются хорошими), после чего следует изучить все оставшиеся хорошие числа. Андрей, 2012-01-20
При копировании из блокнота все переносы строк исчезли 
Но вдруг кто-то все-таки осилит все равно =)Виктория, 2012-03-04
2 и 2alex, 2012-03-10
попробуйте проанализировать другой ответ - 3 и 4Ivan A. Kosarev, 2012-03-26
Задачка замечательная. Ответ есть, он действительно единственный и это действительно пара (13 4).
Ключевой момент в решении задачи -- понять, что ее нужно решать не так, как она сформулирована султаном для мудрецов, а так, как сформулирована для вас в форме истории для мудрецов.
Обозначим произведение искомой пары чисел буквой M, а сумму -- S.
Читаем условие:
> Мудрецы задумались. Первым нарушил молчание Али.
> - Я не знаю этих чисел, - сказал он, опуская голову.
Это значит, есть больше одной пары, произведение чисел в которых равно M.
> - Я это знал, - подал голос Вали.
Значит, для всех пар, сумма чисел в которых равна S произведение этих же чисел будет равно числу M' такому, что есть больше одной пары, произведение чисел в которых равно M'.
> - Тогда я знаю эти числа, - обрадовался Али.
Значит, для M есть всего две подходящие пары, причем сумма чисел в одной из этих пар равна S' такому, что для всех пар, сумма чисел в которых равна S' произведение чисел в паре равно числу M'' такому, что есть больше одной пары, произведение чисел в которых равно M''.
Перебором получаем следующие пары, отвечающие этим трем условиям:
(7 4) (9 2) (13 4) (19 4) (22 19) (23 4) (25 2) (25 10) (29 8) (31 4) (31 10) (31 16) (31 22) (34 7) (34 13) (34 19) (37 4) (37 10) (37 16) (41 6) (41 12) (43 4) (43 10) (47 6)
> - Тогда и я знаю! - воскликнул Вали.
> И мудрецы сообщили пораженному царю задуманные им числа.
Значит, искомая пара такая, что зная S и зная, что решение существует и оно единственное можно назвать эту пару. Другими словами, из всех подходящих пар решением будет та пара, сумма чисел в которой не равна сумме чисел в любой другой подходящей паре.
Легко проверить, что из приведенных пар только пара (13 4) имеет уникальную сумму. Все остальные пары имеют суммы, каждая из которых равна сумме какой-либо другой пары.
Vic, 2012-04-16
Уважаемые математики! Не подскажете, почему, к примеру, числа(цифры) 2 и 9 не подойдут в качестве ответа? Заранее спасибо.Vic, 2012-04-16
Отбой...Ответ на свой вопрос нашёл в предыдущем посте.Иван Горин, 2012-06-29
Задача имет 13 решений.
Первое число всегда 4
второе число: 13 19 31 37 43 47 53 61 67 73 79 83 89
Решение я привёл в Большом форуме, Альтернативная наука, тема: Бинарная логика и озарениеDenniSib, 2012-09-18
Иван А Косарев, а почему 19 и 4 исключили ? Суммы 23 в парах больше не встречается...Эльмира, 2012-10-30
Какой смысл сообщать о том, что эти числа <100, если это не влияет на ответ.
Я считаю, ято ответ 19 и 12.
Сергей М., 2012-11-20
Задача попалась в 80-х в журнале "Наука и жизнь". На решение ушло несколько дней. Решение действительно единственное: 4 и 13. В оригинале ограничение было, что числа не более 60.Тьма, 2013-02-18
ФігняГога, 2013-04-07
Максимальная сумма 197(99+98), максимальное произведение 9702(99*98). Есть масса вариантов, при которых Али не может назвать числа, а Вали скажет что знал это. Конечно, если Али увидел произведение 9702, то он сразу скажет что это множители 99 и 98, потому что используя множители меньше 100 получить 9702 можно только в одном случае.
А если он увидел 180, то конечно он не знает этих чисел, в то время когда Вали пялится на свои 28(например 18+10) и тоже не может понять какими слагаемыми оно получено. Просчитывая все варианты Вали сообщает(фразой "я знал это", что он понял,что вариантов много, поэтому ты не сможешь дать ответ. На этом тупик.
Все рассуждения умных математиков подогнаны под ответ. Или ввели для себя какие-то дополнительные условия, которые я не понял(типа произведение не может превышать 52, 60, 100 или нечто подобное). Но если опираться на условие задачи, то дать точный ответ нельзя.Евгений, 2013-10-14
Моё решение:
1. Раз Али не знал ответ сразу, то произведение раскладывается минимум на 3 простых множителя.
2. Раз Вали знал это, значит сумма непредставима в виде двух простых чисел. Это означает, что сумма нечётная, так как любоё чётное число кроме 2 представимо в виде суммы двух простых чисел. Вообще-то в общем виде это ещё не доказано (проблема Гольдбаха), но в нашем случае это так.
3. Нечётное число можно получить только суммой чётного и нечетного, значит одно из искомых чисел чётное, другое нечетное.
4. Рассмотрим простые делители нашего искомого нечётного числа. Очевидно, что среди них нет ни одного чётного делителя, иначе бы число бы чётным.
5. Али взглянул на простые делители своего произведения и понял, что все чётные делители должны принадлежать только одному числу. То есть искомое нечётное число состоит только из простых нечётных чисел, а чётное число из простых чётных чисел количеством минимум 1 и нечётных чисел количеством минимум 0. То есть в искомом чётном числе также может быть несколько нечётных простых делителей.
6. Раз Али, получив информацию из пункта 3, сразу понял ответ, значит у него был только один нечётный делитель. Ведь если бы нечётных делителей было два, то искомое нечётное число могло бы быть как любым из них, так и их произведением, то есть у Али было минимум два варианта нечётного числа и он бы не смог догадаться. А раз он догадался, значит искомое нечётное число - это единственный простой нечётный делитель. Раз нечётных делителей не осталось, значит чётному числу остались только чётные простые числа. Есть только одно чётное простое число, это 2. Из пункта 1 следует, что этих двоек в произведении минимум 2. То есть возможные варианты 4, 8, 16, 32, 64.
7. Итак, загаданные числа это какое-то нечётное простое число и одно из чисел {4, 8, 16, 32, 64}. Раз Вали, получив эту информацию, догадался, значит его сумма представима в виде [нечётное простое число + {4, 8, 16, 32, 64}] единственным способом. Вот почему не подходит, например, 11:
11 = 4 + 7
или
11 = 8 + 3.
(а не 2 + 9, как ошибочно писали выше).
Ну а дальше перебор, который дал несколько решений:
4 13
4 37
4 61
8 89
16 13
16 37
16 43
16 73
16 97
32 89
64 43
64 53
64 59
64 61
64 67
64 71
64 73
64 79
64 83
64 97
Похоже, что в условии задачи пропущено, что, числа, которые были сказаны мудрецам, меньше 100. С этим условием получается только одно решение:
4 13Creator, 2013-12-08
Супер задача! Решение действительно могло бы быть не одно, но... там есть еще и 5-ое условие, кот. и ставит все на свои места - это последняя строка: "и мудрецы сообщили пораженному царю задуманные им числа" - т.е. они правильно их вычислили. из этого постулата следует, что у Али было лишь 2 возможных решения: либо произведение четного на четное, либо 1 единственно возможное произведение четное на нечетное (пока Вали не сообщил ему, что одно из чисел четное, а другое нечетное), и именно в этом случае остается четное число произведения получаемое единственным вариантом умножения 13*4. Мда... задачка хороша! ))Эмиль?, 2015-01-16
Это я-Адиль!Nick, 2015-02-25
Могли быть и другие числа.Например,Али получил какое-то круглое число, предполагающее несколько возможных сомножителей, допустим 600. Варианты 20*30 или 60*10. Вали сообщили соответственно 50 или 70. Короче, математически это не решить, только перебором чисел.Shaman, 2015-04-21
Хорошая задача.
Решение единственно.
Вот если бы султан сказал "меньше тысячи", то решений было бы 4 ))Иван Горин, 2016-03-25
Если сумма меньше 1000, то какие это 4 решения?
У меня есть два решения для суммы меньше 440.
Это числа 4, 13 и 4,61
А для суммы меньше 37 нет решений.
Для суммы меньше 758 имеется 3 решения.
Это числа 4, 13 или 4,61 или 32 131.
Если я правильно составил программу.
Сравним результаты?
дед, 2016-05-10
N - нечетное простое число
Ч1 и Ч2 - искомые числа
П - число АЛИ
S - число ВАЛИ
По условию: П = Ч1 * Ч2; S = Ч1 + Ч2
2. Не знать Ч1 и Ч2 АЛИ может только если П содержит более 2-х простых множителей
3. Подтвердить, что тоже видит это, ВАЛИ может только в случае, если
при любом возможном Ч1 и соответствующем ему Ч2 = S - Ч1
выражение Ч1 * Ч2 содержит более 2-х простых множителей.
Если бы S было четным, то вседа нашлось хотя бы одно его разложение на простые.
Значит S - нечетное.
4. Именно нечетность S помогла АЛИ отбросить все варинты разложения П на множители
за исключением одного и определить Ч1 и Ч2.
Пошагово:
- нечетность S приводит к разной четности Ч1 и Ч2, а значит к четности П
- если П содержит только одну 2-ку, то все виды его разложения на множители имеют вид - (чет*нечет)
и информация ВАЛИ не проясняет ситуацию. Поэтому 2-ек должно быть минимум две.
- именно при таком условии АЛИ вправе отбросить все варианты разложения (чет*чет)
- для того, чтобы остался только один необходимо и достаточно, чтобы удовлетворялось условие
П = 2^k * N где k - натуральное число больше единицы. Ч1=2^k Ч2=N
5. ВАЛИ услышав, что АЛИ нашел решение, понимает и алгоритм его нахождения.
Поэтому переходит к рассмотрению всех вариантов уравнения S = 2^k + N
Ему надо удостовериться, что только при одном из всех допустимых значений (k) N-простое.
Ищем Ч1 и Ч2
Находим такое первое нечетное число, чтобы предыдущее ему нечетное было составным.
Это 11.
***Отнимаем от него 4. Получаем 7. Убеждаемся, что оно простое.
АЛИ сообщаем 4*7=28, ВАЛИ 4+7=11.
АЛИ скажет "Не знаю"(2*14 или 4*7)
ВАЛИ ответит "Я это вижу"(2и9,3и8,4и7,5и6)
АЛИ найдет решение.
Но ВАЛИ выбрать между 3и8, и 4и7 невозможно.
Надо было в строке с *** продолжить -отнимаем от него 2^3=8. Получаем 3, тоже простое и значит 11 не годится.
13 не подходит из-за простоты 11
15 не подходит из-за простоты 13
17-4=13 простое. 17-8=9 - составное.
Значит 4 и13 решения задачи.
Следующие 13 и 16
Потом 37 4, 37 16, 43 16, 61 4, 73 16, 89 8, 103 16, 73 64 ит.д.
Sub Макрос1()
'
i = 1
For n = 3 To 10000 Step 2
Call ПростоеЧисло(n - 2, m)
If m <> 1 Then
n2 = 0
n1 = 4
Do While n1 < n - 1
Call ПростоеЧисло(n - n1, m)
If m = 1 Then
n2 = n2 + 1
n3 = n1
If n2 = 2 Then
Exit Do
End If
End If
n1 = 2 * n1
Loop
If n2 = 1 Then
Cells(i, 1) = n - n3
Cells(i, 2) = n3
i = i + 1
End If
End If
Next n
End Sub
Function ПростоеЧисло(n, m)
m = Int(Sqr(n))
Do While m > 1
If n / m = n \ m Then Exit Do
m = m - 1
Loop
End Function
Получится 863 пары чисел
Последние 7949 и 2048
Дмитрий, 2017-08-01
Все упёрлись в ответ 13 и 4. Но он не верный. Единственно верный это 3 и 4. Потому что сумма 17 создает много пар чисел, которые при умножении создадут сложные числа, такие как: 2*15=30. 3*14=42. 4*13=52. 5*12=60. 7*10=70. 8*9=72. Даже ближайшая пара чисел к 3 и 4, это 4+5=9. А 9 уже создает 3 пары чисел (2+7,3+6 и 4+5) и уже 3+6 и 4+5 создают сложные числа, т.е. они создали сложных чисел больше одного. Уже они б не решили эту задачу. Дмитрий, 2017-08-01
Слишком сильно вы заморочились. Ответ на поверхности)Nick, 2018-08-11
По-моему, при числах 13 и 4 не мог произойти такой диалог. 1-му мудрецу задано произведение 52, он предполагает 2 суммы: 28 и 17. Если это 28, то расклад на суммы предполагает 18 возможных сумм (26 и 2,25 и 3 …19 и 9), ни одну из которых нельзя исключить. Если это 17, то получится 7 возможных сумм (15 и 2,14 и 3…9 и 8). Если первую фразу 1-го мудреца можно понять, т.к. имеется минимум 2 варианта сомножителей, и вторую фразу диалога 2-го мудреца, т.к. он столкнулся с указанными суммами (28 или 17), то «теперь я знаю» 1-го мудреца и «тогда я знаю» 2-го необоснованны, т.к. не предполагают единственное решение.
Возможен такой диалог, например, в следующем случае: 1-му мудрецу сообщено произведение 12. Это 6*2 или 4*3. 2-му названа сумма 8 или 7. Если 8, то это 4+4, 6+2 или 5+3. Последний случай имеет единственное решение (15) и потому исключается. Если 7, то это 4+3 или 5+2 (который тоже исключается). Тогда 1-му названо 12, и он действительно не знает 6 и 2 или 4 и 3. 2-му названа сумма 8, и он согласен, что 1-й испытывает трудности, т.к. и 16 (4+4), и 12 предполагают не единственное решение. Поскольку 2-й мудрец пока не дает ответа, то 1-й мудрец понимает, что сумма не 7, а 8, и потому говорит «тогда я знаю», имея ввиду 6 и 2. Третья фраза этого диалога, 1-го мудреца, ключевая. Поэтому 2-й мудрец понимает, что при варианте 16 (4*4) 1-й мудрец не нашел бы решения (16 это 8+2, т.е. 10 (8*2, 6*4, и исключаемые 7*3 и 5*5) или 4+4, т.е. 8 (6*2,4*4 и не учитываемое 5*3)). И 2-му остается один вариант: произведение 12 и сомножители и слагаемые 6 и 2. Таким образом, решение возможно только, если произведение предполагает 2 варианта и сумма предполагает тоже 2 варианта, из которых второй (7) очевиден и потому исключается.
Гаргашмель, 2018-12-10
2*2=4
Ктото , 2019-01-03
Фсмыслиииии????????????Nataliya, 2020-04-17
3 и 6 тоже подходят
для решения нужно знать или сумму или произведения
а так мнгие пары чисел подойдут
Согласна
А не повернуты ли мозги у математиков.Придумываетет ограничения где их нет.
