Недавно на Хабре промелькнула интересная задачка про двух мудрецов. Здесь я хочу предложить свой вариант решения и рассказать, как к этому решению можно прийти. Напомню условие:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Султан сказал Али произведение, а Вали – сумму. Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному султану задуманные им числа.
Назовите эти числа.
Существует похожая задача, которая тоже была на Хабре. Она значительно проще.
Задача о Дне рождения:
Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат: 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. После этого сгенерируем матрицу, где будут стоять единицы на пересечениях возможных пар сумма-произведение.
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.
Комментарии (54)
sheshanaag
21.04.2015 22:21+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]
MichaelBorisov
22.04.2015 02:21+1Для решения я использовал MATLAB. Да, я стреляю из пушки по воробьям, но с Матлабом я часто сталкиваюсь в работе
Я бы тоже выбрал Матлаб, если бы созрел для составления программы по этой задаче. Но не только потому, что сталкиваюсь по работе. Главная причина — развитые возможности отладки в Матлабе. Вы можете не только поставить в скрипте точку останова и посмотреть значения переменных, но и исполнить во время останова произвольные команды, хоть фрагменты своего скрипта, подкорректировать неверные промежуточные результаты и т.д.
Все сложные алгоритмы, которые реализую, я сначала отлаживаю в Матлабе и потом перевожу на C, C++ или ассемблер.
Sander80
22.04.2015 02:59+1Wolfram 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]]
DarkByte
22.04.2015 05:38+1А можно для самых маленьких объяснить, почему Али назвал числа 4 и 13, а не 2 и 26 или 1 и 52?
Sander80
22.04.2015 06:28+11 и 52 не разрешено по условию.
А вот 2 и 26… если предположить, что загаданы эти числа, то их сумма 28.
Оно также раскладывается как 5+23.
5 и 23 — простые, то есть произведение 5*23 нельзя разложить иным способом
Следовательно, знай Вали это число 28, он бы не мог ответить «я знал» на первую фразу Али.
Ildarovich
22.04.2015 12:49Вот решение на 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
OlegTar
22.04.2015 13:22+2больше похоже на решение на SQL, чем на 1С.
Ildarovich
22.04.2015 17:41В 1С так язык запросов выглядит, если использовать английский язык разработки. Практически это и есть SQL, точнее, его некоторое подмножество.
Кстати, одним из самых подходящих языков для решения этой задачи был бы Пролог.
А в Матлабе можно было бы попытаться комплексные числа для повышения компактности решения использовать.
Spiceman
27.04.2015 10:00Решение на прологе:
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).
amaectpo
22.04.2015 14:59Я решительно не понимаю по чему Вы так легко убрали 5 и 6-ой месяц?
Rouse
22.04.2015 15:17Потому что числу 18 и 19 соответствует только определенный месяц, и если бы Бернард знал что это число 18, то он сразу бы назвал нужный месяц, но он не знает.
amaectpo
22.04.2015 15:39Всё понял… Просто рассуждал вот так: если допустим 16 мая — то фраза «Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает» — тоже подходит: Я не знаю, когда у Шерил день рождения — (так как в мае три дня), но я знаю, что Бернард тоже не знает ( это тоже подходит так на 16 число подходит 2 месяца) — но в таком случаи он не может быть уверен, что Бернард не знает, так как 19 попадает на Май.
Rouse
22.04.2015 20:32Вообще это классическое Судоку — только в своеобразно поданной форме :)
Принципы исключения примерно такие-же :)
anton9088
23.04.2015 03:02а можете мне тоже объяснить почему вычеркиваются столбцы? я так и не понял
18 и 19 числа вычеркиваем потому что Альберт знает, что Бернард не знает месяца
но это утверждение не исключает столбцы полностью, только 2 даты
AlexeyStn Автор
24.04.2015 14:09Поясню, почему вычёркиваются столбцы.
Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: "Я знаю, что Бернард не знает", так как есть вероятность, что д.р. 19-го мая.
Поэтому май вычёркивается. Аналогично и с июнем.
TimsTims
26.04.2015 14:19Смотрите — они оба молчат, значит Бернард не знает. Значит можно сказать, что «я знаю, что Бернард не знает». Почему это не может быть 15 мая?
AlexeyStn Автор
26.04.2015 14:37Допустим, это 15 мая. Значит, Альберту известен месяц «май».
Далее следует рассуждение из моего сообщения выше.
Ведь он не знает точно, что это именно 15-е. Он допускает, что это может быть 19-е. И не говорит "Я знаю, что Бернард не знает".TimsTims
26.04.2015 15:09Если бы было 19-е, Бернард сказал бы сразу — 19е мая. Но т.к. оба молчат, значит оба друг другу говорят, что это не 19е мая и 18е июня. Разве не так?
Как-раз из-за их молчания делается такой вывод, т.е. 19-е мая исключается изначально.
Дальше не понял про 15-е мая.AlexeyStn Автор
26.04.2015 15:16Конечно, 19 мая и 18 июня исключаются изначально. Но вместе с этими датами исключаются и месяцы целиком.
Вам не ясно, почему исключаются месяцы?TimsTims
26.04.2015 16:40Да, поясните пожалуйста
AlexeyStn Автор
26.04.2015 17:56+1Попытаюсь.
Альберту известен только месяц. Бернарду день.
Таблица возможных сочетаний месяцев и дней известна обоим. Мы (наблюдатели) знаем только таблицу.
Альберт смотрит, какие дни могут быть в месяце, который ему известен, и думает.
Допустим, он знает, что это июль. Тогда он видит, что ответ — либо 14 июля, либо 16 июля. То есть Бернарду известно либо 14, либо 16 число. И в том, и в другом случае, Альберт видит, что у Бернарда нет однозначного ответа. И тогда Альберт может сказать свою первую фразу.
Противоречия нет, мы делаем вывод, что июль — допустимый месяц.
Теперь допустим, что он знает, что это июнь. Для июня он видит варианты — 17 и 18 июня. То есть Бернарду известно либо 17, либо 18 число. В случае 17-го у Бернарда нет однозначного ответа. В случае 18-го Бернард будет знать ответ наверняка. Получается, что Альберт, зная июнь, не может точно сказать, знает Бернард ответ сразу или нет. И он не может сказать свою первую реплику.
Получаем противоречие и делаем вывод, что июнь — недопустимый месяц.
Таким образом, месяцы, в которых встречаются дни, которым соответствует лишь один месяц, недопустимы. Их мы вычёркиваем.
Надеюсь, я не запутал вас ещё больше.TimsTims
05.05.2015 23:33Пожалуйста, не поленитесь, распишите тоже самое, но если это 15 мая, в каком месте реально произойдет затык. Да поблагодарят вас все запутавшиется!
AlexeyStn Автор
07.05.2015 16:12Допустим, было загадано 15 мая. Посмотрим, как в этой ситуации размышлял бы Альберт:
«Я знаю, что это май.
Это может быть 15, 16 или 19 — какой-то из этих трёх вариантов.
Значит, число, которое известно Бернарду — 15, 16 или 19.
Если у Бернарда 15, то тогда он сомневается между маем и августом.
Если у него 16, то он колеблется между маем и июлем.
Если у него 19, то он уже знает ответ.
Так что я не могу сказать, знает ли Бернард ответ, или не знает.»
На этом месте происходит «затык». В случае мая он не может сказать первую фразу.TimsTims
09.05.2015 15:33Спасибо, разберем дальше:
-Если у него 19, то он уже знает ответ.
Значит Бернард первым скажет, что это 19е мая. А он молчит, поэтому вычеркиваем 19е мая(только этот день!)
Остаются две даты: 15е мая и 16е мая(их мы еще не вычеркнули!)
-Если у Бернарда 15, то тогда он сомневается между маем и августом.
-Если у него 16, то он колеблется между маем и июлем.
Ок, Бернард колеблется, это значит, что Бернард не знает.
Значит точно можно сказать «я знаю, что Бернард тоже не знает.»
Выходит, 15е мая и 16е мая не вычеркиваются.AlexeyStn Автор
12.05.2015 22:34Интересное рассуждение. Я не задумывался над этим, когда публиковал задачу. Как и многие, кто согласился с решением.
Получается, что сторонний наблюдатель может сделать вывод, что раз Альберт заговорил первым, то Бернард не знал ответа.
Чтобы исключить такой ход мыслей, нужно скорректировать условие задачи про день рождения, чтобы реплики были такими же, как в задаче про числа:
Бернард: Я не знаю.
В этом случае решение будет корректным.
Альберт: Я знал, что ты не знаешь.
AndyD
22.04.2015 15:46Из фразы Бернарда:
Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
следует, что он уже на втором шаге знал правильный ответ. Хотя это произошло только на третьем. Вобщем текст задачи весьма туманный.AlexeyStn Автор
22.04.2015 16:25На втором шаге ответ узнал Бернард. На третьем шаге узнал ответ Альберт.
AndyD
22.04.2015 16:34Да как же он узнал… он только смог отсеять май и июнь. На самом деле вся задача построена на предположениях: один на пустом месте утверждает одно, второй, не опровергая это, продолжает сужать рамки и утверждает другое и т.д. хотя на любом шаге кто-то может предположить неверно… Вобщем интересная задача!
imwode
22.04.2015 16:06Хм, а у меня произведений получилось 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)
4753AlexeyStn Автор
22.04.2015 16:22+1Среди возможных пар чисел некоторые дают не уникальное произведение.
Например, 5 x 12 = 6 x 10 = 4 x 15. Или 5 x 4 = 10 x 2.
В результате произведений меньше, чем пар.
TimsTims
26.04.2015 13:42Стоп-стоп, поясните мне, давно мучаюсь:
почему на первом же шаге отметается весь май и июнь?
19е мая и 18июня отметаются — там всё понятно, но почему из первого выражения следует, что это не могут быть даты 15/05 16/05?
Представим, что это 15 мая, или 16 мая значит:
— Я не знаю этих чисел, — сказал он, опуская голову.
Вполне означает, что она ему сказала «май», ведь из-за молчания была отметена только дата 19.05. остальные две даты остались: 15.06 и 16.05.
— Я это знал, — подал голос Вали.
значит, что она ему сказала например 15-е или 16-е, что для первого означало бы май/июнь/август
— Тогда я знаю эти числа, — обрадовался Али.
ну всё, тут логика рушится. почему-то все объяснения(и на хабре и на ГТ) смело отметают весь май и весь июнь только потому, что в июне и мае есть 19.05 и 18.06, которые встречаются один раз, однако почему-то отметаются еще и другие даты — 15.05 и 16.05, про которых ни слова.
Спасибо за разъясненияAlexeyStn Автор
26.04.2015 14:10Пояснил чуть выше, почему отметаются месяцы, а не дни.
Vatslavovich
04.05.2015 12:36-1Да нет, совершенно там не объяснили ничего.
Цитата:… Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: «Я знаю, что Бернард не знает», так как есть вероятность, что д.р. 19-го мая… В случае с 19 мая Бернард сказал бы сразу дату. В случае, если Альберту сказали май, а Бернарду — число 15, Альберт бы точно так же мог произнести фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает, потому что: а) первая часть фразы указывает на то, что по уникальности месяца задачу не решить, б) по уникальным числам Бернард решить ее тоже не смог. Фраза позволяет исключить лишь два уникальных числа, но не в коем случае не месяцы. На каком логическом рассуждении вы исключили май — не понятно.T-D-K
04.05.2015 13:41Может быть так будет понятнее?
В метод передаём дни для того месяца, к-й знает Альберт. Возвращает 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 Бернард знает день рождения, а значит Бернард не может наверняка не знать, а значит Альберт не может сказать свою первую фразу, поэтому исключаем мая.Vatslavovich
04.05.2015 17:28… Альбер перебирает все дни своего месяца и проверяет что каждый из не уникален. Только в таком случае он может сказать свою фразу… Он может сказать только первую часть первой фразы.
А вторая часть фразы говорит о том, что и Бернард не знает даты рождения, то есть у Бернарда нет уникального дня.
… Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения… Абсолютная глупость. Если что-либо известно Альберту, то это не говорит о том, что это знает и Бернард. Мы можем оперировать только теми данными и допущениями, что у нас имеются. И они позволяют исключить только две уникальные даты и не более того.
Если бы дата рождения была 15 мая, то первая фраза Альберта была той же самой, потому что есть всего два критерия: знаю и не знаю. Придумывать критерий — наверняка — что это какая-то степень разновидности не знаю — по меньшей мере — обманывать себя.T-D-K
04.05.2015 17:29+2Как же с вами тяжело.
Vatslavovich
04.05.2015 17:33Поменяйте ответ на 15 мая. Что измениться? Будет та же самая первая фраза Альберта. А вот дальше у вас будет затык.
T-D-K
04.05.2015 17:36Не будет такой же первой фразы. Т.к. в мае есть 19 число. К-е уникально. И потому Альберт не сможет сказать свою фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Потому что он не будет знать. Он может сказать " я предполагаю, что Бернард тоже не знает", но не «я знаю». Потому что в мае есть уникальное число, блин.Vatslavovich
04.05.2015 17:43Началось… И если Бернард при этом покачал головой и щелкнул два раза пальцами — мы поняли, что май нужно исключить. Чем по вашему отличается фраза " не знаю" от фразы «предполагаю, что не знаю»? Степенью вероятности события? Если вы так думаете, ( или хотя может так оно и есть), то тогда да, признаю, что я туп, и эта задача не для меня.
T-D-K
04.05.2015 17:45Именно что степенью вероятности события. Я понимаю, что аналогия — не аргумент, но чем отличаются два выражения: я знаю что вы из Москвы и я предполагаю что вы из Москвы. В первом случае я уверен и значит для меня вероятность того, что мы из Москвы = 1. Во втором случае вероятность для меня того, что вы из Москвы 0<p<1.
Спасибо что наконец признались в том, что эта задача не для вас.Vatslavovich
04.05.2015 18:00-1Ок. Тогда начнем с начала. Согласно вашей трактовке, фраза Альберта… Я не знаю, когда у Шерил день рождения,… должна звучать… Я предполагаю, что я не знаю. Это софистика чистой воды.
TimsTims
05.05.2015 23:21Но ведь Бернард услышав например 19-е число сразу бы сказал, что это май 19е. А раз промолчал и первая фраза за Альбертом, значит Альберт понял, что Бернард не знает и может С УВЕРЕННОСТЬЮ сказать, что ОН НЕ ЗНАЕТ.
И таким образом дата 15е мая вполне подходит под первую фразу и май действительно выкидывается зря.
Vatslavovich
04.05.2015 17:35Абсолютно с вами согласен. Из-за одного уникального числа отметают целый месяц.
Spiceman
27.04.2015 20:08+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))); } }
And32
29.04.2015 15:25+1Правильно ли я понимаю, что решение задачи о дне рождении возможно только для того кто задачу отгадывает на основе слов Альберта и Бернарда? Альберт ведь не мог прийти к однозначному выводу.
Поначалу вполне логично что остается всего два месяца — июлю, август. Затем Бернард заявляет что знает когда ДР, что вытекает из того что он получил два месяца и зная день рождения узнал месяц. Но на основе чего дальше делает свое заявление Альберт? Он может только сказать что день рождения не 14го числа, а точно назвать цифру сам он не может, ведь так? Зная 15 16 17 Бернард в любом случае узнал бы месяц, соответственно Альберт не может прийти к однозначному выводу.
akhmelev
01.05.2015 04:14Пара-решение в ограничениях условий задачи и последующего диалога всего одна. Вероятность такого развития событий 1/2843, т.е. загадай султан два любых других числа, и мудрецы неизбежно окажутся посрамлены. Везучие мудрецы.
Добавим к этой вероятности требование, что в одном месте в одно время должно быть два человека, обладающих способностью удерживать в голове матрицу в 10 млрд. элементов и запоминать вычеркнутые строки/столбцы.
Таких людей гарантированно нет даже одного, вероятность из 1/2843 превращается в ноль. Поэтому получаем классический парадокс, а поиск решения лишается смысла ;).
Но задача конечно шикарная.
QtRoS
Программирование в ограничениях очень подходит для этой задачи — формируется домен доступных решений, убираются (prune) недопустимые.