Комментарии к колодцу Феруэлла

14 и 3, 13 и 16

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}] единственным способом.

Только автор этого поста почему то проглядел вторую пару 13 и 16.

1. Али (А) - я не знаю решения.

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

2. Вали (В) - я это знал.

Значит среди всех вариантов как можно сумму разбить на пару чисел нет ни одной пары одновременно двух простых чисел.
Т.е. ему известна сумма S, ее можно разбить следующими способами:
2+(S-2), 3+(S-3), ... и среди этих вариантов нет ни одного, где слагаемые одновременно два простых числа.
Как найти эти числа?
Например, можно в Excel заполнить в одну строчку все цифры от 2 до 99 и отметить как-то все простые числа.
В строчку ниже заполнить все числа в обратном порядке от 99 до 2 и тоже отметить все простые числа.
Теперь в каждом столбце будут два числа сумма которых одинакова и эту сумму мы проверяем на наше условие. Если ни в одном столбце нет двух простых чисел, то это подходящая сумма. Сдвигая нижнюю строку относительно верхней мы можем быстро проверить все возможные суммы.
Приведу готовый вариант посчитанный на компьютере из поста выше:
Вывод программы:
11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 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 151 153 155 157 159 161 163 165 166 167 169 171 173 174 175 177 178 179 181 182 183 184 185 187 188 189 190 191 192 193 194 195 196 197 198
Т.е. сумма двух чисел, которую знает В, может быть только из этого множества (С).

3. Тогда я знаю эти числа, — обрадовался Али.

Начнем исследовать предполагаемые числа из множества С.
Первое число 11, его можно представить ввиде следующих сумм: 2+9, 3+8, 4+7, 5+6.
- 2*9 = 18, перебираем все варианты, как можно получить это число произведением (3*6) и какая сумма при этом этих чисел (3+6= 9).
Так как число 9 не входит во множество С, то Али может однозначно представить число 18 как произведение 2*9. Это означает что вариант 2+9 подходит под третий критерий. Аналогично проверяем остальные пары.
- 3*8 = 24: 2*12 (2+12=14), 4*6 (4+6=10) в дальнейшем для ускорения счета можем использовать тот факт, что одно умножаемое должно быть нечетным.
- 4*7 = 28: 2*14 (2+14=16).
- 5*6 = 30: 2*15 (2+15=17), 3*10 (3+10=13) - Интересный момент для этой пары чисел 5,6 . Произведение 30 может быть представлено и как 5*6 и как 2*15 и сумма 11 и сумма 17 входит во множество С. Это означает что А не мог бы однозначно разложить число 30. Значит пара чисел 5,6 не удовлетворяет критерию 3. А пары чисел 2,9; 3,8; 4,7 - удовлетворяют.

4. Тогда и я знаю! — воскликнул Вали.

Что нам дает эта информация? А то, что чисел удовлетворяющих критерию 3 не может быть больше одного (иначе будет неоднозначность). Поэтому иследуемое число 11 не удовлетворяет критерию 4 (и решению задачи), так как у него есть аж три пары чисел, удовлетворяющих критерию 3.

Теперь проверим следующее число из множества С - 17. Пары чисел - 2,15; 3,14; 4,13; 5,12; 6,11; 7,10; 8,9.
- 2*15 = 30 ; 5*6=30 (5+6= 11) - 11 из множества С, значит пара не удовлетворяет.
- 3*14= 42; 2*21= 42 (2+21=23) - 23 - не удовлетворяет.
- 4*13 = 52; 2+26=42 (2+26=28) - удовлетворяет.
- 5*12 = 60; 3+20=60 (3+20=23) - 23 = не удовлетворяет.
- 6*11= 66; 2*33=66 (2+33=35) - 35 - не удовлетворяет.
- 7*10=70; 2*35=70 (2+35=37) -37 - не удовлетворяет.
- 8*9=72; 3*24=72 (3+24=27) - 27 - не удовлетворяет.
И так, для суммы 17, только одна пара чисел 4, 13 удовлетворяет всем четырем критериям задачи и поэтому есть ее решением.
Но мы пока не может ответить является ли эта пара единственным решением. Нужно еще аналогичным образом проверить все числа из множества С.
Для ускорения счета, нам не нужно проверять все пары для определенного числа. Достаточно обнаружить два варианта подходящие по критерию 3 и дальше проверять нет смысла - это число не может быть решением.
Я проверил до числа 53 включительно и вариантов не нашел. Далее пошел гуглить и нашел, что компьтерные программы посчитали, что других вариантов решения задачи нет (для чисел меньше 100).