?

Log in

No account? Create an account

masterok


Мастерок.жж.рф

Хочу все знать


Previous Entry Share Next Entry
А теперь сложнее, чем вчера
masterok


Вчера я пытался разобраться в логическом решении задачки, которую как то решал весь интернет. Разобрался. Спасибо всем комментаторам.

Однако есть подобная задачка и сложнее и интереснее. Это уж тем более мне не "по зубам", но знаю, что среди читателей есть любители такого:

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».

Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

В интернете встречаются программные алгоритмы решения этой задачки, но можно и чисто логикой. Разберем процесс рассуждения...

Подсказка 1: Я не знаю этих чисел

Это значит, что произведение неоднозначно раскладывается на произведение двух множителей, меньших 100.
Рассмотрим те произведения, которые так раскладываются единственным образом, назовем их однозначными.

Выделим несколько важных классов однозначных произведений:
Произведение двух простых.
Куб простого числа — представляется только как произведение этого числа на его квадрат.
Произведение простого числа больше 50 на что-то еще — при любом другом разбиении на множители один из них окажется больше 100.

Примеры:
По произведению 15 можно однозначно сказать, что загаданы 3 и 5.
По произведению 125 можно однозначно сказать, что загаданы 5 и 25.
По произведению 2130 = 2 * 3 * 5 * 71 можно однозначно сказать, что загаданы 71 и 30.


Подсказка 2: Я это знал

Это значит, что как ни разбей загаданную сумму на два слагаемых, их произведение будет неоднозначным.

Займемся прореживанием множества потенциально подходящих сумм:
Для четных чисел, меньших 200, можно не проверять гипотезу Гольдбаха, т. е. их можно представить в виде суммы двух простых.
Все числа больше 54 можно представить как 53 + x, x > 1. Произведение 53 и x будет однозначным, т. к. 53 — простое больше 50.
Если p — простое число, то p + 2 — неподходящая сумма, т. к. представляется в виде суммы двух простых.

Таким образом остаются нечетные числа S < 54 такие, что (S-2) — составное:
11, 17, 23, 27, 29, 35, 37, 41, 47, 51


Подсказка 3: Тогда я знаю эти числа

Это значит, что для данного произведения есть единственное разложение на множители, сумма которых находится в нашем списке. Назовем такие произведения хорошими.
Заметим, что все суммы в списке нечетные, а значит одно из чисел должно быть четным, а второе — нечетным.
Частный случай хорошего произведения — произведение степени двойки и простого числа, сумма которых лежит в нашем списке. Действительно, как ни разбей на множители по-другому, они оба окажутся четными и их сумма не сможет оказаться подходящей.
Пример: 8 * 19 = 4 * 38 = 2 * 76, только сумма первых двух множителей подходящая.


Подсказка 4: Тогда и я знаю!

Это значит, что сумму можно единственным образом разбить на два слагаемых, дающих хорошее произведение.
Проверять отсутствие или единственность такого разложения будет сложно, так что заметим, что если для какой-то суммы нашлось хотя бы два разложения, она нас не устраивает.
Снова прореживаем множество сумм, используя частный случай из предыдущей подсказки:
11 = 4 + 7 = 8 + 3
17 = 4 + 13 =?
23 = 4 + 19 = 16 + 7
27 = 4 + 23 = 8 + 19
29 = 16 + 13 =?
35 = 4 + 31 = 16 + 19
37 = 8 + 29 = 32 + 5
41 = 4 + 37 =?
47 = 4 + 43 = 16 + 31
51 = 4 + 47 = 32 + 19

Суммы, для которых пока нашлось единственное хорошее произведение: 17, 29, 41.
29 = 25 + 4
25 * 4 = 100 = 20 * 5, но 25 — неподходящая сумма, а значит 100 — хорошее произведение.
41 = 16 + 25
16 * 25 = 400 = 80 * 5, но 85 — неподходящая сумма, а значит 400 — хорошее произведение.

Остается число 17:
17 = 2 + 15, 2 * 15 = 5 * 6 (сумма 11) — плохое произведение
17 = 3 + 14, 3 * 14 = 21 * 2 (сумма 23) — плохое
17 = 4 + 13 — хорошее
17 = 5 + 12, 5 * 12 = 20 * 3 (сумма 23) — плохое
17 = 6 + 11, 6 * 11 = 33 * 2 (сумма 35) — плохое
17 = 7 + 10, 7 * 10 = 35 * 2(сумма 37) — плохое
17 = 8 + 9, 8 * 9 = 24 * 3 (сумма 27) — плохое

Значит, число 17 можно единственным образом представить в виде суммы двух чисел, произведение которых можно единственным образом разложить на два множителя меньше 100, сумму которых нельзя представить в виде суммы двух чисел, которые однозначно определяются своим произведением.

А загаданные числа — 4 и 13.

Вот тут источник этого объяснения



Subscribe to  masterok

Posts from This Journal by “Задача” Tag

  • Задачка с хитростью, но раскрою ее сразу

    Итак, вот по сети начала ходить задачка. С одной стороны неплохие задачки, но с другой стороны непонятно для чего в них начинают прятать какие то…

  • В какой коробке автомобиль?

    Имеется три коробки, в одной из которых находится автомобиль. На каждой коробке написано утверждение, но лишь одно из трех утверждений является…

  • Схватить гуся в полете

    Что то подзабыл как с научной точки зрения будет выглядеть объяснения такой ситуации.: вот например разогнался ты до скорости пули и летишь рядом…


promo masterok январь 2, 12:00 46
Buy for 300 tokens
Вот так выглядит ушедший от нас 2017 год. А вот кстати, начало 2018 года показывает еще больший трафик, чем декабрь 2017: И вот один из дней - рекордсменов за всю историю журнала тоже уже в 2018 году: Красная цифра - это общее количество уникальных посетителей попавших в блог. В…

  • 1
Это ты уже постил. Окстись!

проверил - нет не было

Оставляют без средств к существованию.
http://tchaykovskiy.info/blog_b/obsksvso.htm

Ефим Чеповецкий

Шах и Ахмет

Шах и Ахмет.jpg

Однажды старый грозный шах
Вошёл в дворцовый зал
И, грусти не тая в глазах,
Придворным так сказал:
- Мы, мудрый шах Махмуд-палван,
О том скорбим душой,
Что пухнет наша голова
От мудрости большой.
Кто нынче шуткой облегчит
Страданья мудреца,
Тому дадим в награду чин
Придворного глупца.

- О, шах, я пред тобой пигмей, -
Сказал слуга Ахмед. –
Сравниться с мудростью твоей
Не может белый свет,
И всё ж прогнать осмелюсь я
Твою печаль долой,
Лишь отгадай, что у меня
В кармане под полой?
И если сможешь отгадать,
Что груши там лежат,
То половину их отдать
Тебе я буду рад.
На рынке не найти таких,
Прекрасен плод любой,
А отгадаешь сколько их,
То весь десяток твой… -
И мудрый шах склонил чело,
И долго ждал народ,
Пока сказал он: - Их число
Мой казначей сочтёт.
Но ты скажи мне сам, Ахмед,
Слуга покорный мой,
Что за таинственный предмет
Ты прячешь под полой?


Edited at 2018-08-15 05:52 pm (UTC)

  • 1