#21441
19 апреля, 02:09
1
Цитата (FMFMAN87 @ 18.4.2015) *
Есть же задача про мудрецов. Попробуйте решить ее таким же перебором))) (это уже адвансед лэвел)
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Спойлер: Спрятать
Действие №1: Али раскладывает своё число на простые множители. Если их всего два, то он сразу знает числа. Раз он не знает, значит их не два, а больше.
Действие №2: Вали знает, что число Али (произведение) не является произведением двух простых чисел. Иными словами, ВСЕ возможные пары двух чисел от 2 до 99, на которые разбивается сообщённая ему сумма, не содержат пары простых чисел.
Действие №3: переберём все числа, которые могли быть сообщены Вали. Это не так долго, если понять пару принципов быстрого отбрасывания. {11, 17, 23, 29, 35, 41 ... } Заметим, что числа идут через 6.
Действие №4: Предположим для простоты, что число, сообщённое Али разбивается ровно на три простых множителя. Попробуем первую тройку: {2,3,5} - не работает (есть 11 и 17). Попробуем вторую {2,3,7} - не работает (есть 17 и 23). Попробуем третью {2,5,7} - работает: есть только 17, а 19 и 37 - нету.
Значит как минимум числа 7 и 10 подходят под условия задачи.
Одно решение я нашёл сходу (минут за 15), но как исследовать его на полноту - пока не придумал, может кто-то продолжит, или я за ночь придумаю
Khishtaki
Khishtaki
Модератор
Рейтинг: +25696
Сообщений: 7746
На сайте: 5 лет
#21442
19 апреля, 02:41
1
Спойлер: Спрятать
придумал как минимум ещё две пары удовлетворяющих условиям чисел: 4+7 и 2+9.
Выходит, что их точно много, но как определить их все - я не знаю.
Вообще, теория чисел - это базис высшей математики, при этом внешне выглядит как жоннглирование цифрами, а по сути - вся завязана на арифметике простых чисел. Простые числа - самая большая загадка Вселенной!
Khishtaki
Khishtaki
Модератор
Рейтинг: +25696
Сообщений: 7746
На сайте: 5 лет
#21443
19 апреля, 02:44
17
Это я же уже лёг спать - и вернулся :). Кажется, заснуть сегодня ночью не получится: сна ни в одном глазу, перебираю простые числа :(((
40 лет же уже, не мальчик, сколько можно хернёй страдать?! 
0
