Однажды султан вызвал к себе двух мудрецов, А и Б, и сказал:
- Я задумал два целых числа, каждое из которых больше единицы. Их произведение я сообщу А, а их сумму скажу Б. Ещё я добавлю, что число, которое знает Б, не больше 60. После этого вы должны будете назвать задуманные мной числа.
Когда султан сообщил им сумму и произведение, мудрецы задумались.
- Я не знаю этих чисел, - нарушил молчание А.
- Я знал, что ты не знаешь, - ответил Б.
- Тогда я знаю их! - воскликнул А.
- Ну тогда и я знаю, - заключил Б.
Назовите эти числа.
Решение
Что будет делать мудрец А, узнав произведение двух целых чисел, больших единицы? Конечно, он начнёт раскладывать его на множители. Поскольку он не смог сразу назвать два числа, получается, что произведение раскладывается на множители более чем одним способом.
Что начнёт делать мудрец Б, узнав сумму? Без сомнения, он примется раскладывать её на слагаемые. Поскольку он заранее знает, что А не сможет вычислить числа, то известная Б сумма должна обладать следующим свойством: при любом разбиении на слагаемые, большие единицы, произведение слагаемых должно раскладываться на множители более чем одним способом.
Если немного подумать, то станет ясно, что для этого необходимо и достаточно, чтобы сумма, известная Б, не была представима в виде суммы двух различных простых чисел.
Таких возможных сумм, если приглядеться, не так много. Попробуем найти несколько первых из них:
Почему, услышав реплику Б, А смог уверенно заявить, что знает задуманные два числа? Потому что из всех известных ему разложений ровно одно даёт сумму, которая удовлетворяет требованию из предыдущего абзаца.
Например, если султан загадал 2 и 9, то из двух разложений на множители только одно, 2*9, даёт обладающую нужным свойством сумму (2+9=11), а второе, 3*6, - нет (потому что 3+6=9).
С другой стороны, если царь загадал 5 и 6, то А мог бы разложить их произведение на 2*15, и тогда он получил бы две пары чисел, каждая из которых давала бы нужную сумму, и не смог бы назвать числа.
Можно взять несколько первых вариантов и составить табличку:
После этого Б тоже смог вычислить задуманные султаном числа. Смог бы он это сделать, если бы известная ему сумма была равна 11? Очевидно, что нет, потому что у него не было бы никаких оснований, чтобы выбрать между вариантами 2+9, 3+8 и 4+7.
Получается, что из всех разбиений суммы на слагаемые ровно одно должно удовлетворять условию. Например, это могла бы быть сумма 17 с разложением 4+13=17.
Вот мы и пришли к ответу: султан задумал 4 и 13. После этого он сообщил А произведение 52, а Б сумму 17.
Быстрая проверка:
1. А не может выбрать между 4*13 и 2*26 и говорит об этом.
2. Б знает, что при любом разбиении на слагаемые (2+15, 3+14, 4+13, 5+12, 6+11, 7+10, 8+9) получаются произведения, которые раскладываются более чем одним способом.
3. Это позволяет А отбросить вариант 2*26. Если бы султан задумал 2*26, то Б мог бы разбить сумму 28 на 23+5, а произведение 5*23 раскладывается однозначно.
4. В свою очередь это позволяет Б отбросить все варианты, кроме 4+13. Во всех остальных случаях получаются произведения, в которых А не смог бы сделать выбор.
Доказательство единственности решения оставляем читателю.
- Я задумал два целых числа, каждое из которых больше единицы. Их произведение я сообщу А, а их сумму скажу Б. Ещё я добавлю, что число, которое знает Б, не больше 60. После этого вы должны будете назвать задуманные мной числа.
Когда султан сообщил им сумму и произведение, мудрецы задумались.
- Я не знаю этих чисел, - нарушил молчание А.
- Я знал, что ты не знаешь, - ответил Б.
- Тогда я знаю их! - воскликнул А.
- Ну тогда и я знаю, - заключил Б.
Назовите эти числа.
Решение
Что будет делать мудрец А, узнав произведение двух целых чисел, больших единицы? Конечно, он начнёт раскладывать его на множители. Поскольку он не смог сразу назвать два числа, получается, что произведение раскладывается на множители более чем одним способом.
Что начнёт делать мудрец Б, узнав сумму? Без сомнения, он примется раскладывать её на слагаемые. Поскольку он заранее знает, что А не сможет вычислить числа, то известная Б сумма должна обладать следующим свойством: при любом разбиении на слагаемые, большие единицы, произведение слагаемых должно раскладываться на множители более чем одним способом.
Если немного подумать, то станет ясно, что для этого необходимо и достаточно, чтобы сумма, известная Б, не была представима в виде суммы двух различных простых чисел.
Таких возможных сумм, если приглядеться, не так много. Попробуем найти несколько первых из них:
| Сумма | Подходит? |
|---|---|
| 1 | Нет, слагаемые должны быть больше 1 |
| 2 | Нет, слагаемые должны быть больше 1 |
| 3 | Нет, слагаемые должны быть больше 1 |
| 4 | Нет, 4=2+2 |
| 5 | Нет, 5=2+3 |
| 6 | Нет, 6=3+3 |
| 7 | Нет, 7=2+5 |
| 8 | Нет, 8=3+5 |
| 9 | Нет, 9=2+7 |
| 10 | Нет, 10=3+7 |
| 11 | Да, 2+9=3+8=4+7=5+6 |
| 12 | Нет, 12=5+7 |
| 13 | Нет, 13=2+11 |
| 14 | Нет, 14=3+11 |
| 15 | Нет, 15=2+13 |
| 16 | Нет, 16=3+13 |
| 17 | Да, 17=2+15=3+14=4+13=5+12=6+11=7+10=8+9 |
| 18 | Нет, 18=5+13 |
| 19 | Нет, 19=2+17 |
| 20 | Нет, 20=3+17 |
| 21 | Нет, 21=2+19 |
| 22 | Нет, 22=3+19 |
| 23 | Да, 23=2+21=3+20=4+19=5+18=6+17=7+16=8+15=9+14=10+13=11+12 |
| 24 | Нет, 24=5+19 |
| 25 | Нет, 25=2+23 |
| 26 | Нет, 26=3+23 |
| 27 | Да |
| 28 | Нет, 28=5+23 |
| 29 | Да |
| 30 | Нет, 30=7+23 |
| 31 | Нет, 2+29 |
| 32 | Нет, 3+29 |
| 33 | Нет, 2+31 |
| 34 | Нет, 3+31 |
| 35 | Да |
| 36 | Нет, 5+31 |
| 37 | Да |
Почему, услышав реплику Б, А смог уверенно заявить, что знает задуманные два числа? Потому что из всех известных ему разложений ровно одно даёт сумму, которая удовлетворяет требованию из предыдущего абзаца.
Например, если султан загадал 2 и 9, то из двух разложений на множители только одно, 2*9, даёт обладающую нужным свойством сумму (2+9=11), а второе, 3*6, - нет (потому что 3+6=9).
С другой стороны, если царь загадал 5 и 6, то А мог бы разложить их произведение на 2*15, и тогда он получил бы две пары чисел, каждая из которых давала бы нужную сумму, и не смог бы назвать числа.
Можно взять несколько первых вариантов и составить табличку:
| Число | Число | Сумма | Произведение | Подходит? |
|---|---|---|---|---|
| 2 | 9 | 11 | 18 | Да, 18=3*6, 3+6=9 |
| 3 | 8 | 11 | 24 | Да, 24=4*6, 4+6=10 |
| 4 | 7 | 11 | 28 | Да, 28=2*14, 14+2=16 |
| 5 | 6 | 11 | 30 | Нет, 30=2*15, 2+15=17 |
| 2 | 15 | 17 | 30 | Нет, 30=5*6, 5+6=11 |
| 3 | 14 | 17 | 42 | Нет, 42=2*21, 2+21=23 |
| 4 | 13 | 17 | 52 | Да, 52=2*26, 2+26=28 |
| 5 | 12 | 17 | 60 | Нет, 60=3*20, 3+20=23 |
| 6 | 11 | 17 | 66 | Нет, 66=2*33, 2+33=35 |
| 7 | 10 | 17 | 70 | Нет, 70=2*35, 2+35=7 |
| 8 | 9 | 17 | 72 | Нет, 72=3*24, 3+24=27 |
После этого Б тоже смог вычислить задуманные султаном числа. Смог бы он это сделать, если бы известная ему сумма была равна 11? Очевидно, что нет, потому что у него не было бы никаких оснований, чтобы выбрать между вариантами 2+9, 3+8 и 4+7.
Получается, что из всех разбиений суммы на слагаемые ровно одно должно удовлетворять условию. Например, это могла бы быть сумма 17 с разложением 4+13=17.
Вот мы и пришли к ответу: султан задумал 4 и 13. После этого он сообщил А произведение 52, а Б сумму 17.
Быстрая проверка:
1. А не может выбрать между 4*13 и 2*26 и говорит об этом.
2. Б знает, что при любом разбиении на слагаемые (2+15, 3+14, 4+13, 5+12, 6+11, 7+10, 8+9) получаются произведения, которые раскладываются более чем одним способом.
3. Это позволяет А отбросить вариант 2*26. Если бы султан задумал 2*26, то Б мог бы разбить сумму 28 на 23+5, а произведение 5*23 раскладывается однозначно.
4. В свою очередь это позволяет Б отбросить все варианты, кроме 4+13. Во всех остальных случаях получаются произведения, в которых А не смог бы сделать выбор.
Доказательство единственности решения оставляем читателю.
Комментариев нет:
Отправить комментарий