ANDREYICH @ 21.4.2015
Для начала с 14 и 3 изложи будь ласка про "подходят "
Предложу свой вариант нахождения решения.
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).
Из этой же серии есть такая задача: в вагоне едут 10 мудрецов в шляпах, у некоторых из них шляпы испачканы. Каждый видит шляпы всех соседей но не видит свою. Поезд останавливается на станциях и на каждой станции можно сходить почистить шляпу. Мудрец не снимает свою шляпу, чтобы посмотреть грязная ли она, а только размышляет. :) Заходит проводник и говорит: "Среди вас есть мудрецы в грязных шляпах". И на 5й остановке после этого все мудрецы с грязными шляпами идут на станцию их чистить.
Вопрос: "Сколько было мудрецов в грязных шляпах".
Этот вопрос не сложный.
А вот интересный вопрос: "Какую информацию сообщил проводник мудрецам?". Он сказал им что среди них есть мудрецы в грязных шляпах, но это они знали и без него (грязных было больше одного, так что каждый видел хотя бы одного грязного).. Что же нового сказал им проводник?