Решение задачи о двух мудрецах и числах от 1 до 100


Недавно на Хабре промелькнула интересная задачка про двух мудрецов. Здесь я хочу предложить свой вариант решения и рассказать, как к этому решению можно прийти. Напомню условие:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Султан сказал Али произведение, а Вали – сумму. Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному султану задуманные им числа.
Назовите эти числа.

Существует похожая задача, которая тоже была на Хабре. Она значительно проще.
Задача о Дне рождения:
Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат: 15 мая, 16 мая, 19 мая, 17 июня, 18 июня, 14 июля, 16 июля, 14 августа, 15 августа и 17 августа. Затем Шерил сказала Альберту месяц своего рождения, а Бернарду — день. После этого состоялся диалог.
Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Бернард: Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
Альберт: Теперь я тоже знаю, когда у Шерил день рождения.
Когда у Шерил день рождения?

При ближайшем рассмотрении можно увидеть, что эти две задачи совершенно идентичны.
Некоторым дням соответствуют несколько возможных месяцев, также, как некоторым произведениям соответствует несколько сумм (например, произведению 60 соответствуют суммы 15+4=19, 12+5=17 и т.д.). Некоторым месяцам соответствуют несколько дней, также, как некоторым суммам соответствуют несколько произведений (например, сумме 10 соответствуют произведения 6*4=24, 7*3=21 и т.д.). Смысл диалогов тоже совершенно одинаковый.

Это значит, что, если мы составим работающий алгоритм решения задачи о дне рождения, то сможем использовать его и для задачи о мудрецах. Разница лишь в количестве возможных комбинаций день-месяц и сумма-произведение, которые требуется перебрать. Если день рождения можно вычислить вручную на бумаге, то для поиска чисел от 1 до 100 нужно использовать программные средства. Поэтому мы сначала составим алгоритм для более простой задачи, чтобы убедиться в его правильности, а затем подставим туда исходные данные из более сложной.

Для решения я использовал MATLAB. Да, я стреляю из пушки по воробьям, но с Матлабом я часто сталкиваюсь в работе, так что пусть каждый использует инструмент, который ему привычнее.

Итак, решение.

1. Запишем исходные условия: вектор с возможными значениями дней, вектор с возможными значениями месяцев и прямоугольную матрицу, в которой на местах возможных сочетаний стоят единицы.



days = [14; 15; 16; 17; 18; 19];
months = [5; 6; 7; 8]; 
matrix = [ 0 0 1 1;  1 0 0 1;  1 0 1 0;  0 1 0 1;  0 1 0 0;  1 0 0 0 ];

2. Проанализируем первую фразу Альберта, который знает месяц:
Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Из неё можно сделать вывод, что любым дням, допустимым для этого месяца, могут соответствовать больше одного месяца.
Такая ситуация невозможна для мая (ведь если день рождения 19 мая, то Бернард уже знает ответ) и для июня (если ответ – 18 июня, то Бернард тоже знает точную дату).
Чтобы исключить невозможные месяцы, нам нужно найти строки, в которых только одна единица (дни 18 и 19), найти столбцы где стоят эти единицы (месяцы 5 и 6) и вычеркнуть эти столбцы.



На Матлабе это действие будет выглядеть так:
unique_days = find(sum(matrix,2)==1);
[~, months_with_unique_days] = find (matrix(unique_days,:)==1);
months_with_unique_days = unique(months_with_unique_days);
matrix(:,months_with_unique_days) = [];
months(months_with_unique_days) = [];

3. После первой фразы Бернард, которому известен день, ответил:
Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.

Значит, тому дню, который знает Бернард, соответствует только один месяц.
Такая ситуация возможна для чисел 15, 16 и 17.
Все строки матрицы, в которых больше одного решения или нет ни одного, нужно удалить.



non_unique_days = find(sum(matrix,2)~=1);
matrix(non_unique_days,:) = [];
days(non_unique_days) = [];

4. Альберт, знающий месяц, ответил:
Теперь я тоже знаю, когда у Шерил день рождения.
Значит, в оставшейся части матрицы остался столбец, в котором есть только один вариант. Этот столбец соответствует июлю. Выбросим все столбцы, где больше одного варианта.



non_unique_months = find(sum(matrix)~=1);
matrix(:,non_unique_months) = [];
months(non_unique_months) = [];

5. Осталось найти в оставшемся столбце единицу.
days = days(matrix == 1);
disp(days);
disp(months);

Ответ: 16 июля.

Вот полный исходный код решения.
% Birthday example
matrix = [ 0 0 1 1;  1 0 0 1;  1 0 1 0;  0 1 0 1;  0 1 0 0;  1 0 0 0 ];
days = [14; 15; 16; 17; 18; 19];
months = [5; 6; 7; 8];

% Remove months with unique days
unique_days = find(sum(matrix,2)==1);
[~, months_with_unique_days] = find (matrix(unique_days,:)==1);
months_with_unique_days = unique(months_with_unique_days);
matrix(:,months_with_unique_days) = [];
months(months_with_unique_days) = [];

% Remove non-unique days
non_unique_days = find(sum(matrix,2)~=1);
matrix(non_unique_days,:) = [];
days(non_unique_days) = [];

% Find 1 month with unique day
non_unique_months = find(sum(matrix)~=1);
matrix(:,non_unique_months) = [];
months(non_unique_months) = [];

% Find the last day
days = days(matrix == 1);

% Result output
disp(days);
disp(months);


Теперь попробуем применить этот алгоритм для задачи с мудрецами.
Месяцы заменим на все возможные суммы двух чисел от 2 до 99. Это будут целые числа от 4 до 198. Дни заменим на все возможные произведения двух чисел от 2 до 99. Таких произведений оказалось 2843. После этого сгенерируем матрицу, где будут стоять единицы на пересечениях возможных пар сумма-произведение.
Небольшой фрагмент этой таблицы (примерно 1/400)
По горизонтальной оси – суммы, по вертикальной – произведения.


months = 4:198;
days = unique((2:99)'*(2:99));
matrix = false(length(days),length(months));
for i1 = 2:99
    for i2 = 2:99
        matrix(days==(i1*i2),months==(i1+i2)) = true;
    end;
end;

Запустим программу и получим ответ: произведение – 52, сумма – 17.
Это соответствует паре чисел 4 и 13.
Поделиться публикацией

Комментарии 56

    0
    Программирование в ограничениях очень подходит для этой задачи — формируется домен доступных решений, убираются (prune) недопустимые.
      +3
      Вот формальное решение этой задачи на haskell:

      import Data.List
      
      groupedSet :: (Num a, Eq a, Ord a) => (a -> a -> a) -> [a] -> [[(a, a)]]
      groupedSet op xs =
          map (map snd) . groupBy (\(a, _) (b, _) -> a == b) . sort $
              [(x `op` y, (x, y)) | x <- xs, y <- xs, x <= y]
      
      main :: IO ()
      main = do
          let a = groupedSet (+) numbers
              {- i do not know these numbers: -}
              b = filter ((> 1) . length . take 2) $ groupedSet (*) numbers
              {- i know that you do not know them: -}
              c = [x | x <- a, all (`elem` concat b) x]
              {- then i know these numbers: -}
              d = singlets b $ concat c
              {- then i know them too: -}
              e = singlets a $ concat d
          print $ concat e
          where numbers      = [2 .. 99]
                singlets a b = [y | x <- a, let y = b `intersect` x, length y == 1]
      
        +1
        Для решения я использовал MATLAB. Да, я стреляю из пушки по воробьям, но с Матлабом я часто сталкиваюсь в работе

        Я бы тоже выбрал Матлаб, если бы созрел для составления программы по этой задаче. Но не только потому, что сталкиваюсь по работе. Главная причина — развитые возможности отладки в Матлабе. Вы можете не только поставить в скрипте точку останова и посмотреть значения переменных, но и исполнить во время останова произвольные команды, хоть фрагменты своего скрипта, подкорректировать неверные промежуточные результаты и т.д.

        Все сложные алгоритмы, которые реализую, я сначала отлаживаю в Матлабе и потом перевожу на C, C++ или ассемблер.
          +1
          Wolfram Mathematica
          numbers = Union[Sort /@ Tuples[Range[2, 99], 2]];
          goodproducts =   Select[Reap[Sow[Plus @@ ##, Times @@ ##] & /@ numbers, _, List][[2]], (Length[##[[2]]] >= 2) &];
          goodsums =   Select[Reap[Sow[Times @@ ##, Plus @@ ##] & /@ numbers, _,  List][[2]], (Complement[##[[2]], First /@ goodproducts] == {}) &];
          goodproducts =   Select[goodproducts, (Length[Intersection[##[[2]], First /@ goodsums]] == 1) &];
          goodsums =  Select[goodsums, (Length[Intersection[##[[2]], First /@ goodproducts]] == 1) &];
          Select[numbers, And[MemberQ[First /@ goodproducts, Times @@ ##],  Plus @@ ## == goodsums[[1, 1]]] &][[1]]
          
            +1
            А можно для самых маленьких объяснить, почему Али назвал числа 4 и 13, а не 2 и 26 или 1 и 52?
              +1
              1 и 52 не разрешено по условию.

              А вот 2 и 26… если предположить, что загаданы эти числа, то их сумма 28.
              Оно также раскладывается как 5+23.
              5 и 23 — простые, то есть произведение 5*23 нельзя разложить иным способом
              Следовательно, знай Вали это число 28, он бы не мог ответить «я знал» на первую фразу Али.
                0
                Спасибо, теперь стало понятно!
              0
              Вот решение на 1С:

              SELECT 0 AS X
              INTO Bit
              UNION SELECT 1
              ;
              SELECT Bit0.X + 2 * (Bit1.X + 2 * (Bit2.X + 2 * (Bit3.X + 2 * (Bit4.X + 2 * (Bit5.X + 2 * Bit6.X))))) AS X
              INTO Row
              FROM Bit AS Bit6, Bit AS Bit5, Bit AS Bit4, Bit AS Bit3, Bit AS Bit2, Bit AS Bit1, Bit AS Bit0
              ;
              SELECT Row1.X AS X, Row2.X AS Y, Row1.X + Row2.X AS Sum, Row1.X * Row2.X AS XY
              INTO Test
              FROM Row AS Row1, Row AS Row2
              WHERE 1 < Row1.X AND Row1.X < Row2.X AND Row1.X + Row2.X <= 100
              ;
              SELECT DISTINCT Test.Sum
              INTO TabuSumm
              FROM Test AS Test
              WHERE Test.XY IN (SELECT XY FROM Test GROUP BY XY HAVING COUNT(*) = 1)
              ;
              SELECT Test.XY AS Mult
              INTO AliNumbers
              FROM Test AS Test
              WHERE NOT Test.Sum IN (SELECT TabuSumm.Sum FROM TabuSumm)
              GROUP BY Test.XY HAVING COUNT(DISTINCT Test.Sum) = 1
              ;
              SELECT Test.Sum, MAX(AliNumbers.Mult) AS Mult, MAX(Test.X) AS X, MAX(Test.Y) AS Y
              FROM Test AS Test INNER JOIN AliNumbers AS AliNumbers ON Test.XY = AliNumbers.Mult
              WHERE NOT Test.Sum IN (SELECT TabuSumm.Sum FROM TabuSumm)
              GROUP BY Test.Sum
              HAVING COUNT(DISTINCT AliNumbers.Mult) = 1
                +2
                больше похоже на решение на SQL, чем на 1С.
                  0
                  В 1С так язык запросов выглядит, если использовать английский язык разработки. Практически это и есть SQL, точнее, его некоторое подмножество.
                  Кстати, одним из самых подходящих языков для решения этой задачи был бы Пролог.
                  А в Матлабе можно было бы попытаться комплексные числа для повышения компактности решения использовать.
                    0
                    Решение на прологе:

                    uniqueDay(X,D/M) :- select(D/M,X,Y),\+member(D/_,Y).
                    uniqueMonth(X,D/M) :- select(D/M,X,Y),\+member(_/M,Y).
                    monthWithUniqueDay(X,_/M) :- uniqueDay(X,_/M).
                    solve(X,X0) :-
                        exclude(monthWithUniqueDay(X0),X0,X1),
                        include(uniqueDay(X1),X1,X2),
                        include(uniqueMonth(X2),X2,X).
                    
                    birthDays(X) :- X = [15/5,16/5,19/5,17/6,18/6,14/7,16/7,14/8,15/8,17/8].
                    
                    num(D/M) :- numlist(2,99,N),select(X,N,_),select(Y,N,_),D is X * Y,M is X + Y.
                    nums(X) :- setof(Y,num(Y),X).
                    
                    solve1(X) :- birthDays(X0),solve(X,X0).
                    solve2(X) :- nums(X0),solve(X,X0).
                    
                0
                Я решительно не понимаю по чему Вы так легко убрали 5 и 6-ой месяц?
                  0
                  Потому что числу 18 и 19 соответствует только определенный месяц, и если бы Бернард знал что это число 18, то он сразу бы назвал нужный месяц, но он не знает.
                    0
                    Всё понял… Просто рассуждал вот так: если допустим 16 мая — то фраза «Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает» — тоже подходит: Я не знаю, когда у Шерил день рождения — (так как в мае три дня), но я знаю, что Бернард тоже не знает ( это тоже подходит так на 16 число подходит 2 месяца) — но в таком случаи он не может быть уверен, что Бернард не знает, так как 19 попадает на Май.
                      0
                      Вообще это классическое Судоку — только в своеобразно поданной форме :)
                      Принципы исключения примерно такие-же :)
                      0
                      а можете мне тоже объяснить почему вычеркиваются столбцы? я так и не понял
                      18 и 19 числа вычеркиваем потому что Альберт знает, что Бернард не знает месяца
                      но это утверждение не исключает столбцы полностью, только 2 даты
                        0
                        Поясню, почему вычёркиваются столбцы.
                        Предположим, Альберту известно, что д.р. в мае.
                        То есть 15 мая, 16 мая или 19 мая.
                        В этом случае Альберт не может сказать свою первую фразу: "Я знаю, что Бернард не знает", так как есть вероятность, что д.р. 19-го мая.
                        Поэтому май вычёркивается. Аналогично и с июнем.
                          0
                          Смотрите — они оба молчат, значит Бернард не знает. Значит можно сказать, что «я знаю, что Бернард не знает». Почему это не может быть 15 мая?
                            0
                            Допустим, это 15 мая. Значит, Альберту известен месяц «май».
                            Далее следует рассуждение из моего сообщения выше.
                            Ведь он не знает точно, что это именно 15-е. Он допускает, что это может быть 19-е. И не говорит "Я знаю, что Бернард не знает".
                              0
                              Если бы было 19-е, Бернард сказал бы сразу — 19е мая. Но т.к. оба молчат, значит оба друг другу говорят, что это не 19е мая и 18е июня. Разве не так?
                              Как-раз из-за их молчания делается такой вывод, т.е. 19-е мая исключается изначально.
                              Дальше не понял про 15-е мая.
                                0
                                Конечно, 19 мая и 18 июня исключаются изначально. Но вместе с этими датами исключаются и месяцы целиком.
                                Вам не ясно, почему исключаются месяцы?
                                  0
                                  Да, поясните пожалуйста
                                    +1
                                    Попытаюсь.
                                    Альберту известен только месяц. Бернарду день.
                                    Таблица возможных сочетаний месяцев и дней известна обоим. Мы (наблюдатели) знаем только таблицу.
                                    Альберт смотрит, какие дни могут быть в месяце, который ему известен, и думает.

                                    Допустим, он знает, что это июль. Тогда он видит, что ответ — либо 14 июля, либо 16 июля. То есть Бернарду известно либо 14, либо 16 число. И в том, и в другом случае, Альберт видит, что у Бернарда нет однозначного ответа. И тогда Альберт может сказать свою первую фразу.
                                    Противоречия нет, мы делаем вывод, что июль — допустимый месяц.

                                    Теперь допустим, что он знает, что это июнь. Для июня он видит варианты — 17 и 18 июня. То есть Бернарду известно либо 17, либо 18 число. В случае 17-го у Бернарда нет однозначного ответа. В случае 18-го Бернард будет знать ответ наверняка. Получается, что Альберт, зная июнь, не может точно сказать, знает Бернард ответ сразу или нет. И он не может сказать свою первую реплику.
                                    Получаем противоречие и делаем вывод, что июнь — недопустимый месяц.

                                    Таким образом, месяцы, в которых встречаются дни, которым соответствует лишь один месяц, недопустимы. Их мы вычёркиваем.

                                    Надеюсь, я не запутал вас ещё больше.
                                      0
                                      Пожалуйста, не поленитесь, распишите тоже самое, но если это 15 мая, в каком месте реально произойдет затык. Да поблагодарят вас все запутавшиется!
                                        0
                                        Допустим, было загадано 15 мая. Посмотрим, как в этой ситуации размышлял бы Альберт:
                                        «Я знаю, что это май.
                                        Это может быть 15, 16 или 19 — какой-то из этих трёх вариантов.
                                        Значит, число, которое известно Бернарду — 15, 16 или 19.
                                        Если у Бернарда 15, то тогда он сомневается между маем и августом.
                                        Если у него 16, то он колеблется между маем и июлем.
                                        Если у него 19, то он уже знает ответ.
                                        Так что я не могу сказать, знает ли Бернард ответ, или не знает.»

                                        На этом месте происходит «затык». В случае мая он не может сказать первую фразу.
                                          0
                                          Спасибо, разберем дальше:

                                          -Если у него 19, то он уже знает ответ.
                                          Значит Бернард первым скажет, что это 19е мая. А он молчит, поэтому вычеркиваем 19е мая(только этот день!)
                                          Остаются две даты: 15е мая и 16е мая(их мы еще не вычеркнули!)

                                          -Если у Бернарда 15, то тогда он сомневается между маем и августом.
                                          -Если у него 16, то он колеблется между маем и июлем.

                                          Ок, Бернард колеблется, это значит, что Бернард не знает.
                                          Значит точно можно сказать «я знаю, что Бернард тоже не знает.»
                                          Выходит, 15е мая и 16е мая не вычеркиваются.
                                            0
                                            Интересное рассуждение. Я не задумывался над этим, когда публиковал задачу. Как и многие, кто согласился с решением.
                                            Получается, что сторонний наблюдатель может сделать вывод, что раз Альберт заговорил первым, то Бернард не знал ответа.
                                            Чтобы исключить такой ход мыслей, нужно скорректировать условие задачи про день рождения, чтобы реплики были такими же, как в задаче про числа:
                                            Бернард: Я не знаю.
                                            Альберт: Я знал, что ты не знаешь.
                                            В этом случае решение будет корректным.
                    0
                    Из фразы Бернарда:
                    Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.

                    следует, что он уже на втором шаге знал правильный ответ. Хотя это произошло только на третьем. Вобщем текст задачи весьма туманный.
                      0
                      На втором шаге ответ узнал Бернард. На третьем шаге узнал ответ Альберт.
                        0
                        Да как же он узнал… он только смог отсеять май и июнь. На самом деле вся задача построена на предположениях: один на пустом месте утверждает одно, второй, не опровергая это, продолжает сужать рамки и утверждает другое и т.д. хотя на любом шаге кто-то может предположить неверно… Вобщем интересная задача!
                          0
                          Он знал число (16) и отбросив май ему всё стало ясно
                      0
                      Хм, а у меня произведений получилось 4753
                      Кусочек списка комбинаций
                      (91, 97)
                      (91, 98)
                      (91, 99)
                      (92, 93)
                      (92, 94)
                      (92, 95)
                      (92, 96)
                      (92, 97)
                      (92, 98)
                      (92, 99)
                      (93, 94)
                      (93, 95)
                      (93, 96)
                      (93, 97)
                      (93, 98)
                      (93, 99)
                      (94, 95)
                      (94, 96)
                      (94, 97)
                      (94, 98)
                      (94, 99)
                      (95, 96)
                      (95, 97)
                      (95, 98)
                      (95, 99)
                      (96, 97)
                      (96, 98)
                      (96, 99)
                      (97, 98)
                      (97, 99)
                      (98, 99)
                      4753
                        +1
                        Среди возможных пар чисел некоторые дают не уникальное произведение.
                        Например, 5 x 12 = 6 x 10 = 4 x 15. Или 5 x 4 = 10 x 2.
                        В результате произведений меньше, чем пар.
                        +1
                        Эта задача появилась давно. Вот статья из Кванта аж за 1977 год. Здесь целое исследование посвященная поиску таких чисел. Интересно было бы найти следующие решения.
                          0
                          Стоп-стоп, поясните мне, давно мучаюсь:
                          почему на первом же шаге отметается весь май и июнь?
                          19е мая и 18июня отметаются — там всё понятно, но почему из первого выражения следует, что это не могут быть даты 15/05 16/05?

                          Представим, что это 15 мая, или 16 мая значит:
                          — Я не знаю этих чисел, — сказал он, опуская голову.
                          Вполне означает, что она ему сказала «май», ведь из-за молчания была отметена только дата 19.05. остальные две даты остались: 15.06 и 16.05.

                          — Я это знал, — подал голос Вали.
                          значит, что она ему сказала например 15-е или 16-е, что для первого означало бы май/июнь/август

                          — Тогда я знаю эти числа, — обрадовался Али.
                          ну всё, тут логика рушится. почему-то все объяснения(и на хабре и на ГТ) смело отметают весь май и весь июнь только потому, что в июне и мае есть 19.05 и 18.06, которые встречаются один раз, однако почему-то отметаются еще и другие даты — 15.05 и 16.05, про которых ни слова.

                          Спасибо за разъяснения
                            0
                            Пояснил чуть выше, почему отметаются месяцы, а не дни.
                              –1
                              Да нет, совершенно там не объяснили ничего.
                              Цитата:… Предположим, Альберту известно, что д.р. в мае.
                              То есть 15 мая, 16 мая или 19 мая.
                              В этом случае Альберт не может сказать свою первую фразу: «Я знаю, что Бернард не знает», так как есть вероятность, что д.р. 19-го мая… В случае с 19 мая Бернард сказал бы сразу дату. В случае, если Альберту сказали май, а Бернарду — число 15, Альберт бы точно так же мог произнести фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает, потому что: а) первая часть фразы указывает на то, что по уникальности месяца задачу не решить, б) по уникальным числам Бернард решить ее тоже не смог. Фраза позволяет исключить лишь два уникальных числа, но не в коем случае не месяцы. На каком логическом рассуждении вы исключили май — не понятно.
                                0
                                Может быть так будет понятнее?
                                В метод передаём дни для того месяца, к-й знает Альберт. Возвращает true, если Бернард тоже не знает наверняка день рождения при известном Альберту месяце.
                                bool FirstPhraseMethod(int[] days){
                                	bool result = true;
                                	foreach (int day in days){
                                		result = result && IsNotUniqueDay(day);
                                	}
                                	return result;
                                }
                                

                                Если текстом и ещё раз то, что писали выше:
                                Во время первой фразы «Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает. » Альберт знает только месяц. Он знает что у Бернарда есть какое-то число, но не знает какое это число.
                                Альбер перебирает все дни своего месяца и проверяет что каждый из не уникален. Только в таком случае он может сказать свою фразу.
                                Т.е. пускай P(m) — вероятность того, что для месяца m Бернард может сразу определить день рождения.
                                Тогда P(август) =(0+0+0)/3 = 0. Т.к. в августе все дни не уникальны, но, например для мая: P(май) = (0(15 мая)+0(16 мая)+1(19 мая))/3 = 1/3. Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения, а значит Бернард не может наверняка не знать, а значит Альберт не может сказать свою первую фразу, поэтому исключаем мая.
                                  0
                                  … Альбер перебирает все дни своего месяца и проверяет что каждый из не уникален. Только в таком случае он может сказать свою фразу… Он может сказать только первую часть первой фразы.
                                  А вторая часть фразы говорит о том, что и Бернард не знает даты рождения, то есть у Бернарда нет уникального дня.
                                  … Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения… Абсолютная глупость. Если что-либо известно Альберту, то это не говорит о том, что это знает и Бернард. Мы можем оперировать только теми данными и допущениями, что у нас имеются. И они позволяют исключить только две уникальные даты и не более того.
                                  Если бы дата рождения была 15 мая, то первая фраза Альберта была той же самой, потому что есть всего два критерия: знаю и не знаю. Придумывать критерий — наверняка — что это какая-то степень разновидности не знаю — по меньшей мере — обманывать себя.
                                    +2
                                    Как же с вами тяжело.
                                      0
                                      Поменяйте ответ на 15 мая. Что измениться? Будет та же самая первая фраза Альберта. А вот дальше у вас будет затык.
                                        0
                                        Не будет такой же первой фразы. Т.к. в мае есть 19 число. К-е уникально. И потому Альберт не сможет сказать свою фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
                                        Потому что он не будет знать. Он может сказать " я предполагаю, что Бернард тоже не знает", но не «я знаю». Потому что в мае есть уникальное число, блин.
                                          0
                                          Началось… И если Бернард при этом покачал головой и щелкнул два раза пальцами — мы поняли, что май нужно исключить. Чем по вашему отличается фраза " не знаю" от фразы «предполагаю, что не знаю»? Степенью вероятности события? Если вы так думаете, ( или хотя может так оно и есть), то тогда да, признаю, что я туп, и эта задача не для меня.
                                            0
                                            Именно что степенью вероятности события. Я понимаю, что аналогия — не аргумент, но чем отличаются два выражения: я знаю что вы из Москвы и я предполагаю что вы из Москвы. В первом случае я уверен и значит для меня вероятность того, что мы из Москвы = 1. Во втором случае вероятность для меня того, что вы из Москвы 0<p<1.
                                            Спасибо что наконец признались в том, что эта задача не для вас.
                                              –1
                                              Ок. Тогда начнем с начала. Согласно вашей трактовке, фраза Альберта… Я не знаю, когда у Шерил день рождения,… должна звучать… Я предполагаю, что я не знаю. Это софистика чистой воды.
                                                +2
                                                deleted. Мне надоело объяснять.
                                            0
                                            Но ведь Бернард услышав например 19-е число сразу бы сказал, что это май 19е. А раз промолчал и первая фраза за Альбертом, значит Альберт понял, что Бернард не знает и может С УВЕРЕННОСТЬЮ сказать, что ОН НЕ ЗНАЕТ.
                                            И таким образом дата 15е мая вполне подходит под первую фразу и май действительно выкидывается зря.
                                0
                                Абсолютно с вами согласен. Из-за одного уникального числа отметают целый месяц.
                                +1
                                Решение на C#:

                                using System;
                                using System.Linq;
                                class Program
                                {
                                	static void Main()
                                	{
                                		var birthDays = Enumerable.Range(2, 98)
                                			.Join(
                                				Enumerable.Range(2, 98), n => 1, n => 1,
                                				(n1, n2) => new {D = n1*n2, M = n1 + n2})
                                			.Distinct().ToList();
                                		var x1 = birthDays.Where(d => !birthDays.Any(d1 => d.D == d1.D && d.M != d1.M)).ToList();
                                		var x2 = birthDays.Where(d => x1.All(d1 => d1.M != d.M)).ToList();
                                		var x3 = x2.Where(d => !x2.Any(d1 => d1.D == d.D && d1.M != d.M)).ToList();
                                		var solve = x3.Where(d => !x3.Any(d1 => d1.D != d.D && d1.M == d.M)).ToList();
                                		Console.WriteLine(string.Join(", ", solve.Select(d => d.D + " " + d.M)));
                                	}
                                }
                                
                                  +1
                                  Правильно ли я понимаю, что решение задачи о дне рождении возможно только для того кто задачу отгадывает на основе слов Альберта и Бернарда? Альберт ведь не мог прийти к однозначному выводу.
                                  Поначалу вполне логично что остается всего два месяца — июлю, август. Затем Бернард заявляет что знает когда ДР, что вытекает из того что он получил два месяца и зная день рождения узнал месяц. Но на основе чего дальше делает свое заявление Альберт? Он может только сказать что день рождения не 14го числа, а точно назвать цифру сам он не может, ведь так? Зная 15 16 17 Бернард в любом случае узнал бы месяц, соответственно Альберт не может прийти к однозначному выводу.
                                    0
                                    Альберт знал, что месяц июль, следовательно выбор у него только между 14 и 16.
                                      0
                                      Точно, про то что он месяц знает я забыл в процессе решения :)) Спасибо
                                    0
                                    Пара-решение в ограничениях условий задачи и последующего диалога всего одна. Вероятность такого развития событий 1/2843, т.е. загадай султан два любых других числа, и мудрецы неизбежно окажутся посрамлены. Везучие мудрецы.

                                    Добавим к этой вероятности требование, что в одном месте в одно время должно быть два человека, обладающих способностью удерживать в голове матрицу в 10 млрд. элементов и запоминать вычеркнутые строки/столбцы.

                                    Таких людей гарантированно нет даже одного, вероятность из 1/2843 превращается в ноль. Поэтому получаем классический парадокс, а поиск решения лишается смысла ;).

                                    Но задача конечно шикарная.
                                      0
                                      т.е. загадай султан два любых других числа

                                      Он знал! Он знал!
                                        0
                                        Говорят, Дейкстра решил за шесть часов вариант этой задачи в уме, без бумажки и ручки. Конечно, вероятность встречи двух Дейкстр в одном месте в одно время тоже не особо велика :)
                                          0
                                          Не та ссылка. Должна была быть эта

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое