Диалог математиков.

[ER*]

Задачка в самом деле интересная. Мне понравилась. Раньше похожих не встречал.

Есть очень известная похожая задача. Она ещё интересней, но у неё огромный недостаток: в Интернете легко найти решение.

Хотя не стал бы называть ее детской.

Для решения достаточно знаний в объёме общеобразовательной школы. Значит, детская.

[Гришин Станислав Григорьевич]

Есть очень известная похожая задача. Она ещё интересней, но у неё огромный недостаток: в Интернете легко найти решение.

Да это самая классная задача такого рода. В 1976 году в "Кванте" опубликована. 3 автора.
{Правда есть и куда как круче - про установление кода сейфа. Запредельной сложности.
Её вряд ли кто бесплатно станет решать. Мои даже за 300 долларов в решении разбираться не стали}.
А эту я на всю жизнь запомнил с восхищением.
Решил по-своему. Там в конце под подозрением оказывается 13 парных сумм.
Вышел как-то, теперь не помню, на то, что одно число должно быть 2^к>1, а второе - простое.
Таких пар в 13 суммах оказалось 4. Дальше - без проблем. В ответе оказались 4 и 13.

[ER*]

Да это самая классная задача такого рода (хотя есть и куда крепче - про установление кода сейфа.
Её вряд ли кто бесплатно станет решать). В 1976 году в "Кванте" опубликована. 3 автора.
Логика на порядок сложнее, чем в этой. Пришлось с ней поковыряться.
Я её на всю жизнь запомнил с восхищением.
Решил по-своему. Там в конце под подозрением оказывается 13 парных сумм.
Вышел как-то, теперь не помню, на то, что одно число должно быть 2^к>1, а второе - простое.
Таких пар в 13 суммах оказалось 4. Дальше - без проблем. В ответе оказались 4 и 13.

Да, задачка неплохая. Я, в своё время, не стал решать её аналитически, подумал, что программно будет проще. Но, при написании программы, внезапно понимаешь: нахрена я не попробовал аналитически, наверняка было бы проще и быстрее, чем этот гемор...

[Иван Горин]

Повторение пройденного.
На БФ эта задача была несколько раз. 
Маленьний Гном и ER решили её программным путём.
Я эту задачу решил аналитически и программным путём.
Повторим решение аналитически, без использования программ.
Первое слово для аналитического анализа предоставляю Анаксагору.

[Иван Горин]

Анаксагор, это твоё решение прошу не предлагать

Задачка не для 4-5 классов, как утверждал Анаксагор.
И его решение я также вычислил логически.
Подгон под ответ для учеников 4-го класса.
Возможный вариант его решения.
Он мне в своей задаче пронумеровал последовательность диалога.
И говорит Анаксагор. Чего тут решать, надо складывать и умножать, следуя диалогу.
Следуем логике Анаксагора.
Диалогов всего 4. Значит одна из цифр равна 4.
Шаг 1. P не знает числа.
Шаг 2. Ход S. Анаксагор складывает номера формул 1+2=3
Шаг 3. Ход P. Анаксагор перемножает предыдущий результат с номером этой формулы 3*3=9
Шаг 4. Ход S. Анаксагор складывает предыдущий результат с номером этой формулы 9+4=13
И получает числа 4 и 13

[Иван Горин]

Исследования решений программным путём.
Программу я написал в 2013 году. Возможно в ней есть ошибки.
Но тем не менее я провожу результаты.
0. s<37  нет решений
1. s<339 4,13 одно решение
2. s<440 + 4,61 два решения
3. s<758  +32,131
4. s<992   +16,73
5. s<1268  +16,111
6. s<1926  +32,311
7. s<2024   +64,73
8. s<2228   +64,309    Под вопросом. 309 не простое число.
9. s<2324   4,229
10. s<2372  +67,82 Это дополнительное решение под вопросом. Возможно программная ошибка.
10. s<3908  +8,239 десять решений.
Er, если у тебя сохранилась программа, проверь пожалуйста.
Затем продолжу.
Но тем не менее видно,что одно из чисел кратно четырём, второе число - простое.
(Это в том случае, если в моей программе нет ошибок)

Далее условия, которые не зависят от моей программы.
Из первого пункта диалога следует ,что у математика P, произведение не является произведением простых чисел.
Из второго пункта диалога следует, что у матаматика S, сумма не раскладывается на суммы простых чисел.
То есть S не может быть чётной.
(S-2) не может быть простым числом.

[ER*]

Er, если у тебя сохранилась программа, проверь пожалуйста.
Затем продолжу.

Программа не сохранилась, но, снова написать несложно. Это только в первый раз нелегко. Займусь на днях, сообщу результаты, сравним.

[Иван Горин]

Но тем не менее видно,что одно из чисел кратно четырём, второе число - простое.
(Это в том случае, если в моей программе нет ошибок)

Далее условия, которые не зависят от моей программы.
Из первого пункта диалога следует ,что у математика P, произведение не является произведением простых чисел.
Из второго пункта диалога следует, что у матаматика S, сумма не раскладывается на суммы простых чисел.
То есть S не может быть чётной.
(S-2) не может быть простым числом.

Пока начинаю аналитический анализ.
Сумма чисел нечетная
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
Жирным шрифтом обозначенны простые числа.
Из этого списка исключаем суммы, у корорых (s-2) простые числа
Остаются суммы:
11 17 23 27 31 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97
Сумму 11 сразу можно исключить. Здесь по крайней мере - двойственность
2+9 2*9, 3*6 S=3+6=9;  9-2=7 простое число.
3+8 3*8, 2*12, 4*6 две суммы - чётные.
Дальше можно не проверять
То есть у математика P остаются по крайней мере числа 2,9 или 3,8
Но на последнем пункте диалога математик S не сможет назвать одну пару чисел,так как он не знает произведение.
Остаются суммы:
17 23 27 31 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97
Найдем суммы, у которых (s-4) - простые числа
17 23 31 35 41 47 51 57 65 71 77 83 87 93
суммы, у которых (s-8) - простые числа
27 31 35 41 51 67 87 97
суммы, у которых (s-16) - простые числа
23 27 35 37 47 53 57 59 77 79 83 87 89 95
суммы, у которых (s-32) - простые числа
35 37 51 59 79 93
суммы, у которых (s-64) - простые числа
67 71 77 83 87 95
Исключаем суммы, которые повторяются в пяти вышеприведённых вариантах,иначе получим неоднозначность.
Остаются суммы
17 53 65 89 97
Все должны быть проверены вручную.
17 проверяется без проблемм. Это числа 4 и 13 и они проходят проверку на однозначность диалогу.
Для остальных четырёх сумм - трудоёмкая ручная работа.

[Иван Горин]

Остаются суммы
17 53 65 89 97
Все должны быть проверены вручную.
17 проверяется без проблемм. Это числа 4 и 13 и они проходят проверку на однозначность диалогу.
Для остальных четырёх сумм - трудоёмкая ручная работа.

Никакой трудоёмкой работы.
Проверяются пара строчек.
Проверм сумму 97
Для начала проверяем только простые числа, уменьшая 97
P        S=97
712     8+89      P=2*356; 4*178; 8*89. чётные суммы исключаем. Остаётся 1 вариант
1162   14+83    P=2*581; 7*166; 14*83. суммы >100 исключаем. Остаётся 1 вариант
Неоднозначность. Сумма 97 для диалога не подходит

Проверм сумму 89
Для начала проверяем только простые числа, уменьшая 89
P        S=89
498     6+83    P=2*249; 3*166; 6*83. суммы >100 исключаем. Остаётся 1 вариант
790   10+79    P=2*395; 5*158; 14*83. суммы >100 исключаем. Остаётся 1 вариант
Неоднозначность. Сумма 89 для диалога не подходит

...

[Иван Горин]

Проверм сумму 65
Для начала проверяем только простые числа, уменьшая 65
P        S=65
244     4+61     Остаётся 1 вариант
354     6+59    P=2*177; 5*158; 3*118; 6*59. суммы >100 исключаем. Остаётся 1 вариант
Неоднозначность. Сумма 65 для диалога не подходит

Проверм сумму 53
S=53 относится к строке s-16
16*37  1 вариант
P        S=53
282     6+47    P=2*141; 3*94; 6*83 (s=97). суммы >100 исключаем. Остаются 2  варианта
430   10+43    P=2*215; 5*86(s=91); 10*43. суммы >100  и (s-2) простое исключаем. Остаётся 1 вариант
Неоднозначность. То есть у математика P по крайней мере может быть произведение 16*37 или 10*43
Сумма 53 для диалога не подходит
Осталось проверить сумму 17.
...

[Иван Горин]

Проверка суммы s=17
Для этой суммы делаем полную проверку

P      S         P (разложение на простые)
30    2+15   2*3*5     P=2*15; 3*10 (s=13, 13-2=11 простое число); 5*6  2 варианта
42    3+14   2*3*7     P=3*14; 2*21; 6*7 (s=13)  2 варианта
52    4+13   2*2*13   P=4*13; 2*26 (s чётная)   1 вариант
60    5+12   2*2*3*5 P=5*12; 2*30 (s чётная) ;4*15 (s=19, 19-2=17 простое число);
                                    6*10 (s чётная); 3*20             2 варианта
66    6+11   2*3*11   P=6*11; 2*33; 3*22 (s чётная); 3*22(s=25, 25-2=23 простое)  2 варианта
70    7+10   2*5*7     P=7*10; 2*35 (s=37); 5*14 (s-2=17 простое)  2 варианта
72    8+9     2*2*2*3*3   P=8*9; 2*36 (s чётная); 4*18 (s чётная); 3*24; 6*12 (s чётная)  2 варианта
Из строки P=70 видно, что при s<37 нет решений для данной задачи.

Итак, загаданы числа 4 и 13.

[ER*]

Er, если у тебя сохранилась программа, проверь пожалуйста.
Затем продолжу.

Написал программу. Всё по чесноку - тупой перебор, никакой аналитики, типа гипотезы Гольдбаха-Эйлера. Это и хорошо. Тупо, кондово, но зато ошибочные решения практически исключены. К сожалению, проверить удалось пока только до s = 759, когда появляются три решения. Нужен мощный комп, такая возможность появится только после праздников (после 22 апреля). Но, до  s = 759 всё сходится.

[ER*]

Что бы проверить конкретные решения, перебор и быстродействие не нужно. Проверил твои конкретные решения на ноутбуке, компyтер говорит ja, richtig.

Исследования решений программным путём.
Программу я написал в 2013 году. Возможно в ней есть ошибки.
Но тем не менее я провожу результаты.
0. s<37  нет решений

да

1. s<339 4,13 одно решение

да

2. s<440 + 4,61 два решения

да

3. s<758  +32,131

да

4. s<992   +16,73

да

5. s<1268  +16,111

да

6. s<1926  +32,311

да

7. s<2024   +64,73

да

8. s<2228   +64,309    Под вопросом. 309 не простое число.

Работает. А, почему должно быть простое число? 16, 111, например, работает, но 111 - не простое число.

9. s<2324   4,229

ja

10. s<2372  +67,82 Это дополнительное решение под вопросом. Возможно программная ошибка.

Работает, ошибки нет

10. s<3908  +8,239

да

Но тем не менее видно,что одно из чисел кратно четырём, второе число - простое.

Второе число может быть и не простым (16,111), (64,309). Интересное решение представляет также (67,82). Выбивается из общей колеи. Первое число не является степенью двойки, а второе - чётное.

Но, в целом, задача прекрасна именно в своём классическом виде, когда сумма чисел не превышает 100. Даже после третьего высказывания остаётся ещё более 400 вариантов. Но, четвётрое высказывание приводит к единственному решению 4,13.

Интересно, как была придумана эта задача? Решить её очень не просто, смогут лишь не все, а придумать задачу, которую аcлилят лишь не все - во сто крат труднее, чем решить.

[Иван Горин]

Er, спасибо за проверку. Значит у меня в программе за 2013 год нет ошибок.
Тогда, чтобы понять мой алгоритм аналитического решения я продолжу исследование сумм больших 100.
Перехожу с андроида на другой комп, где есть латекс.

[Король Альтов]

Проверка суммы s=17
Для этой суммы делаем полную проверку

P      S         P (разложение на простые)
30    2+15   2*3*5     P=2*15; 3*10 (s=13, 13-2=11 простое число); 5*6  2 варианта
42    3+14   2*3*7     P=3*14; 2*21; 6*7 (s=13)  2 варианта
52    4+13   2*2*13   P=4*13; 2*26 (s чётная)   1 вариант
60    5+12   2*2*3*5 P=5*12; 2*30 (s чётная) ;4*15 (s=19, 19-2=17 простое число);
                                    6*10 (s чётная); 3*20             2 варианта
66    6+11   2*3*11   P=6*11; 2*33; 3*22 (s чётная); 3*22(s=25, 25-2=23 простое)  2 варианта
70    7+10   2*5*7     P=7*10; 2*35 (s=37); 5*14 (s-2=17 простое)  2 варианта
72    8+9     2*2*2*3*3   P=8*9; 2*36 (s чётная); 4*18 (s чётная); 3*24; 6*12 (s чётная)  2 варианта
Из строки P=70 видно, что при s<37 нет решений для данной задачи.

Итак, загаданы числа 4 и 13.

Логика железная,
 но я только не понял сочетание:
Проверка суммы s=17 & Из строки P=70 видно, что при s<37 нет решений для данной задачи.

[Иван Горин]

Александр,
шах мог дать другое задание сумма чисел меньше 37.
Тогда у математика P могут быть произведения 52 или 70.
И эти произведения у него имеют только по одному варианту разложения.
Но на последнем пункте диалога математик s не сможет сделать выбор.
У него будут два варианта чисел 4,13 или 7,10

[Иван Горин]

В интернете аналитического решения этой задачи нет.
3 автора привели решение в статье "Много битов из ничего"
Но это была их шутка на внимательность читателей.

[Король Альтов]

Александр,
шах мог дать другое задание сумма чисел меньше 37.
Тогда у математика P могут быть произведения 52 или 70.
И эти произведения у него имеют только по одному варианту разложения.
Но на последнем пункте диалога математик s не сможет сделать выбор.
У него будут два варианта чисел 4,13 или 7,10

Я все таки думаю, что там надо букву s заменить на букву P ?

[Иван Горин]

Я все таки думаю, что там надо букву s заменить на букву P ?

После второго пункта диалога математика S,  "Я заранее знал,что вы не сможете назвать эти числа", оба математика имеют таблицы разложения чисел, которые я привёл.

А этот пункт диалога математика S, обозначает, что
1. сумма чисел не может быть чётной
2. сумма чисел минус 2 не может быть простым числом
3. и условие шаха сумма чисел меньше 100.
И в этом случае задача легко решается аналитически без применения программ.
Это решение я и привёл.
Но будет продолжение анализа для S_max>100
Шах мог сказать математику P число 70. При условии, что сумма чисел меньше 37.
У математика S будет неоднозначность при этом условии. Или 4,13 или 7,10 . Обе суммы равны 17. Он не сможет сделать выбор. И задача не имеет решений.

[Иван Горин]

S_max>100
Проверим суммы от 100 до 149

Нечётные суммы:
101, 103, 105,107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149

Исключаем суммы, у которых (s-2) простое число. Остаются суммы:
101, 107, 113, 117, 119, 121, 123, 125, 127, 131, 135, 137, 143, 145, 147, 149    16 сумм

Из этого списка выделяем суммы, у которых:
1. s-4 простые числа:
101, 107, 113, 117, 121, 135, 143    7 сумм

2. s-8 простые числа:
117, 121, 135, 145    4 суммы

3. s-16 простые числа:
113, 117, 119, 123, 125, 143, 147    7 сумм

4. s-32 простые числа
121, 135, 145    3 суммы

5. s-64 простые числа
101, 107, 117, 123, 125, 131, 135, 137, 143, 147  10 сумм

6. s-128 простые числа
131, 135, 145, 147   4 суммы

Исключаем суммы, которые встречаются более одного раза в разложениях 1. - 6.
Остаются однозначные суммы по диалогу:
119, 127,137, 149    4 суммы.
Эти суммы подлежат проверке.
Заметим, что суммы 127 и 149 не относятся к пунктам от 1. до 6.
И что это за исключения?
S=127=16+111  программа выдала решение при  s<1268  имеется 5 решений. И это пятое решение.
S=149=82+67    67 простое число. Программа выдала решение при  s<2372  имеется 10 решений. И это десятое решение. Но я в нём не уверен. Надо проверить вручную.