Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 56
Программирование в ограничениях очень подходит для этой задачи — формируется домен доступных решений, убираются (prune) недопустимые.
Вот формальное решение этой задачи на 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]
Для решения я использовал MATLAB. Да, я стреляю из пушки по воробьям, но с Матлабом я часто сталкиваюсь в работе
Я бы тоже выбрал Матлаб, если бы созрел для составления программы по этой задаче. Но не только потому, что сталкиваюсь по работе. Главная причина — развитые возможности отладки в Матлабе. Вы можете не только поставить в скрипте точку останова и посмотреть значения переменных, но и исполнить во время останова произвольные команды, хоть фрагменты своего скрипта, подкорректировать неверные промежуточные результаты и т.д.
Все сложные алгоритмы, которые реализую, я сначала отлаживаю в Матлабе и потом перевожу на C, C++ или ассемблер.
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]]
А можно для самых маленьких объяснить, почему Али назвал числа 4 и 13, а не 2 и 26 или 1 и 52?
1 и 52 не разрешено по условию.
А вот 2 и 26… если предположить, что загаданы эти числа, то их сумма 28.
Оно также раскладывается как 5+23.
5 и 23 — простые, то есть произведение 5*23 нельзя разложить иным способом
Следовательно, знай Вали это число 28, он бы не мог ответить «я знал» на первую фразу Али.
А вот 2 и 26… если предположить, что загаданы эти числа, то их сумма 28.
Оно также раскладывается как 5+23.
5 и 23 — простые, то есть произведение 5*23 нельзя разложить иным способом
Следовательно, знай Вали это число 28, он бы не мог ответить «я знал» на первую фразу Али.
Вот решение на 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
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
больше похоже на решение на SQL, чем на 1С.
В 1С так язык запросов выглядит, если использовать английский язык разработки. Практически это и есть SQL, точнее, его некоторое подмножество.
Кстати, одним из самых подходящих языков для решения этой задачи был бы Пролог.
А в Матлабе можно было бы попытаться комплексные числа для повышения компактности решения использовать.
Кстати, одним из самых подходящих языков для решения этой задачи был бы Пролог.
А в Матлабе можно было бы попытаться комплексные числа для повышения компактности решения использовать.
Решение на прологе:
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).
Я решительно не понимаю по чему Вы так легко убрали 5 и 6-ой месяц?
Потому что числу 18 и 19 соответствует только определенный месяц, и если бы Бернард знал что это число 18, то он сразу бы назвал нужный месяц, но он не знает.
Всё понял… Просто рассуждал вот так: если допустим 16 мая — то фраза «Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает» — тоже подходит: Я не знаю, когда у Шерил день рождения — (так как в мае три дня), но я знаю, что Бернард тоже не знает ( это тоже подходит так на 16 число подходит 2 месяца) — но в таком случаи он не может быть уверен, что Бернард не знает, так как 19 попадает на Май.
а можете мне тоже объяснить почему вычеркиваются столбцы? я так и не понял
18 и 19 числа вычеркиваем потому что Альберт знает, что Бернард не знает месяца
но это утверждение не исключает столбцы полностью, только 2 даты
18 и 19 числа вычеркиваем потому что Альберт знает, что Бернард не знает месяца
но это утверждение не исключает столбцы полностью, только 2 даты
Поясню, почему вычёркиваются столбцы.
Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: "Я знаю, что Бернард не знает", так как есть вероятность, что д.р. 19-го мая.
Поэтому май вычёркивается. Аналогично и с июнем.
Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: "Я знаю, что Бернард не знает", так как есть вероятность, что д.р. 19-го мая.
Поэтому май вычёркивается. Аналогично и с июнем.
Смотрите — они оба молчат, значит Бернард не знает. Значит можно сказать, что «я знаю, что Бернард не знает». Почему это не может быть 15 мая?
Допустим, это 15 мая. Значит, Альберту известен месяц «май».
Далее следует рассуждение из моего сообщения выше.
Ведь он не знает точно, что это именно 15-е. Он допускает, что это может быть 19-е. И не говорит "Я знаю, что Бернард не знает".
Далее следует рассуждение из моего сообщения выше.
Ведь он не знает точно, что это именно 15-е. Он допускает, что это может быть 19-е. И не говорит "Я знаю, что Бернард не знает".
Если бы было 19-е, Бернард сказал бы сразу — 19е мая. Но т.к. оба молчат, значит оба друг другу говорят, что это не 19е мая и 18е июня. Разве не так?
Как-раз из-за их молчания делается такой вывод, т.е. 19-е мая исключается изначально.
Дальше не понял про 15-е мая.
Как-раз из-за их молчания делается такой вывод, т.е. 19-е мая исключается изначально.
Дальше не понял про 15-е мая.
Конечно, 19 мая и 18 июня исключаются изначально. Но вместе с этими датами исключаются и месяцы целиком.
Вам не ясно, почему исключаются месяцы?
Вам не ясно, почему исключаются месяцы?
Да, поясните пожалуйста
Попытаюсь.
Альберту известен только месяц. Бернарду день.
Таблица возможных сочетаний месяцев и дней известна обоим. Мы (наблюдатели) знаем только таблицу.
Альберт смотрит, какие дни могут быть в месяце, который ему известен, и думает.
Допустим, он знает, что это июль. Тогда он видит, что ответ — либо 14 июля, либо 16 июля. То есть Бернарду известно либо 14, либо 16 число. И в том, и в другом случае, Альберт видит, что у Бернарда нет однозначного ответа. И тогда Альберт может сказать свою первую фразу.
Противоречия нет, мы делаем вывод, что июль — допустимый месяц.
Теперь допустим, что он знает, что это июнь. Для июня он видит варианты — 17 и 18 июня. То есть Бернарду известно либо 17, либо 18 число. В случае 17-го у Бернарда нет однозначного ответа. В случае 18-го Бернард будет знать ответ наверняка. Получается, что Альберт, зная июнь, не может точно сказать, знает Бернард ответ сразу или нет. И он не может сказать свою первую реплику.
Получаем противоречие и делаем вывод, что июнь — недопустимый месяц.
Таким образом, месяцы, в которых встречаются дни, которым соответствует лишь один месяц, недопустимы. Их мы вычёркиваем.
Надеюсь, я не запутал вас ещё больше.
Альберту известен только месяц. Бернарду день.
Таблица возможных сочетаний месяцев и дней известна обоим. Мы (наблюдатели) знаем только таблицу.
Альберт смотрит, какие дни могут быть в месяце, который ему известен, и думает.
Допустим, он знает, что это июль. Тогда он видит, что ответ — либо 14 июля, либо 16 июля. То есть Бернарду известно либо 14, либо 16 число. И в том, и в другом случае, Альберт видит, что у Бернарда нет однозначного ответа. И тогда Альберт может сказать свою первую фразу.
Противоречия нет, мы делаем вывод, что июль — допустимый месяц.
Теперь допустим, что он знает, что это июнь. Для июня он видит варианты — 17 и 18 июня. То есть Бернарду известно либо 17, либо 18 число. В случае 17-го у Бернарда нет однозначного ответа. В случае 18-го Бернард будет знать ответ наверняка. Получается, что Альберт, зная июнь, не может точно сказать, знает Бернард ответ сразу или нет. И он не может сказать свою первую реплику.
Получаем противоречие и делаем вывод, что июнь — недопустимый месяц.
Таким образом, месяцы, в которых встречаются дни, которым соответствует лишь один месяц, недопустимы. Их мы вычёркиваем.
Надеюсь, я не запутал вас ещё больше.
Пожалуйста, не поленитесь, распишите тоже самое, но если это 15 мая, в каком месте реально произойдет затык. Да поблагодарят вас все запутавшиется!
Допустим, было загадано 15 мая. Посмотрим, как в этой ситуации размышлял бы Альберт:
На этом месте происходит «затык». В случае мая он не может сказать первую фразу.
«Я знаю, что это май.
Это может быть 15, 16 или 19 — какой-то из этих трёх вариантов.
Значит, число, которое известно Бернарду — 15, 16 или 19.
Если у Бернарда 15, то тогда он сомневается между маем и августом.
Если у него 16, то он колеблется между маем и июлем.
Если у него 19, то он уже знает ответ.
Так что я не могу сказать, знает ли Бернард ответ, или не знает.»
На этом месте происходит «затык». В случае мая он не может сказать первую фразу.
Спасибо, разберем дальше:
-Если у него 19, то он уже знает ответ.
Значит Бернард первым скажет, что это 19е мая. А он молчит, поэтому вычеркиваем 19е мая(только этот день!)
Остаются две даты: 15е мая и 16е мая(их мы еще не вычеркнули!)
-Если у Бернарда 15, то тогда он сомневается между маем и августом.
-Если у него 16, то он колеблется между маем и июлем.
Ок, Бернард колеблется, это значит, что Бернард не знает.
Значит точно можно сказать «я знаю, что Бернард тоже не знает.»
Выходит, 15е мая и 16е мая не вычеркиваются.
-Если у него 19, то он уже знает ответ.
Значит Бернард первым скажет, что это 19е мая. А он молчит, поэтому вычеркиваем 19е мая(только этот день!)
Остаются две даты: 15е мая и 16е мая(их мы еще не вычеркнули!)
-Если у Бернарда 15, то тогда он сомневается между маем и августом.
-Если у него 16, то он колеблется между маем и июлем.
Ок, Бернард колеблется, это значит, что Бернард не знает.
Значит точно можно сказать «я знаю, что Бернард тоже не знает.»
Выходит, 15е мая и 16е мая не вычеркиваются.
Интересное рассуждение. Я не задумывался над этим, когда публиковал задачу. Как и многие, кто согласился с решением.
Получается, что сторонний наблюдатель может сделать вывод, что раз Альберт заговорил первым, то Бернард не знал ответа.
Чтобы исключить такой ход мыслей, нужно скорректировать условие задачи про день рождения, чтобы реплики были такими же, как в задаче про числа:
Получается, что сторонний наблюдатель может сделать вывод, что раз Альберт заговорил первым, то Бернард не знал ответа.
Чтобы исключить такой ход мыслей, нужно скорректировать условие задачи про день рождения, чтобы реплики были такими же, как в задаче про числа:
Бернард: Я не знаю.В этом случае решение будет корректным.
Альберт: Я знал, что ты не знаешь.
Из фразы Бернарда:
следует, что он уже на втором шаге знал правильный ответ. Хотя это произошло только на третьем. Вобщем текст задачи весьма туманный.
Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
следует, что он уже на втором шаге знал правильный ответ. Хотя это произошло только на третьем. Вобщем текст задачи весьма туманный.
На втором шаге ответ узнал Бернард. На третьем шаге узнал ответ Альберт.
Да как же он узнал… он только смог отсеять май и июнь. На самом деле вся задача построена на предположениях: один на пустом месте утверждает одно, второй, не опровергая это, продолжает сужать рамки и утверждает другое и т.д. хотя на любом шаге кто-то может предположить неверно… Вобщем интересная задача!
Хм, а у меня произведений получилось 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
(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
Стоп-стоп, поясните мне, давно мучаюсь:
почему на первом же шаге отметается весь май и июнь?
19е мая и 18июня отметаются — там всё понятно, но почему из первого выражения следует, что это не могут быть даты 15/05 16/05?
Представим, что это 15 мая, или 16 мая значит:
— Я не знаю этих чисел, — сказал он, опуская голову.
Вполне означает, что она ему сказала «май», ведь из-за молчания была отметена только дата 19.05. остальные две даты остались: 15.06 и 16.05.
— Я это знал, — подал голос Вали.
значит, что она ему сказала например 15-е или 16-е, что для первого означало бы май/июнь/август
— Тогда я знаю эти числа, — обрадовался Али.
ну всё, тут логика рушится. почему-то все объяснения(и на хабре и на ГТ) смело отметают весь май и весь июнь только потому, что в июне и мае есть 19.05 и 18.06, которые встречаются один раз, однако почему-то отметаются еще и другие даты — 15.05 и 16.05, про которых ни слова.
Спасибо за разъяснения
почему на первом же шаге отметается весь май и июнь?
19е мая и 18июня отметаются — там всё понятно, но почему из первого выражения следует, что это не могут быть даты 15/05 16/05?
Представим, что это 15 мая, или 16 мая значит:
— Я не знаю этих чисел, — сказал он, опуская голову.
Вполне означает, что она ему сказала «май», ведь из-за молчания была отметена только дата 19.05. остальные две даты остались: 15.06 и 16.05.
— Я это знал, — подал голос Вали.
значит, что она ему сказала например 15-е или 16-е, что для первого означало бы май/июнь/август
— Тогда я знаю эти числа, — обрадовался Али.
ну всё, тут логика рушится. почему-то все объяснения(и на хабре и на ГТ) смело отметают весь май и весь июнь только потому, что в июне и мае есть 19.05 и 18.06, которые встречаются один раз, однако почему-то отметаются еще и другие даты — 15.05 и 16.05, про которых ни слова.
Спасибо за разъяснения
Пояснил чуть выше, почему отметаются месяцы, а не дни.
Да нет, совершенно там не объяснили ничего.
Цитата:… Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: «Я знаю, что Бернард не знает», так как есть вероятность, что д.р. 19-го мая… В случае с 19 мая Бернард сказал бы сразу дату. В случае, если Альберту сказали май, а Бернарду — число 15, Альберт бы точно так же мог произнести фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает, потому что: а) первая часть фразы указывает на то, что по уникальности месяца задачу не решить, б) по уникальным числам Бернард решить ее тоже не смог. Фраза позволяет исключить лишь два уникальных числа, но не в коем случае не месяцы. На каком логическом рассуждении вы исключили май — не понятно.
Цитата:… Предположим, Альберту известно, что д.р. в мае.
То есть 15 мая, 16 мая или 19 мая.
В этом случае Альберт не может сказать свою первую фразу: «Я знаю, что Бернард не знает», так как есть вероятность, что д.р. 19-го мая… В случае с 19 мая Бернард сказал бы сразу дату. В случае, если Альберту сказали май, а Бернарду — число 15, Альберт бы точно так же мог произнести фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает, потому что: а) первая часть фразы указывает на то, что по уникальности месяца задачу не решить, б) по уникальным числам Бернард решить ее тоже не смог. Фраза позволяет исключить лишь два уникальных числа, но не в коем случае не месяцы. На каком логическом рассуждении вы исключили май — не понятно.
Может быть так будет понятнее?
В метод передаём дни для того месяца, к-й знает Альберт. Возвращает true, если Бернард тоже не знает наверняка день рождения при известном Альберту месяце.
Если текстом и ещё раз то, что писали выше:
Во время первой фразы «Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает. » Альберт знает только месяц. Он знает что у Бернарда есть какое-то число, но не знает какое это число.
Альбер перебирает все дни своего месяца и проверяет что каждый из не уникален. Только в таком случае он может сказать свою фразу.
Т.е. пускай P(m) — вероятность того, что для месяца m Бернард может сразу определить день рождения.
Тогда P(август) =(0+0+0)/3 = 0. Т.к. в августе все дни не уникальны, но, например для мая: P(май) = (0(15 мая)+0(16 мая)+1(19 мая))/3 = 1/3. Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения, а значит Бернард не может наверняка не знать, а значит Альберт не может сказать свою первую фразу, поэтому исключаем мая.
В метод передаём дни для того месяца, к-й знает Альберт. Возвращает 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 Бернард знает день рождения, а значит Бернард не может наверняка не знать, а значит Альберт не может сказать свою первую фразу, поэтому исключаем мая.
… Альбер перебирает все дни своего месяца и проверяет что каждый из не уникален. Только в таком случае он может сказать свою фразу… Он может сказать только первую часть первой фразы.
А вторая часть фразы говорит о том, что и Бернард не знает даты рождения, то есть у Бернарда нет уникального дня.
… Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения… Абсолютная глупость. Если что-либо известно Альберту, то это не говорит о том, что это знает и Бернард. Мы можем оперировать только теми данными и допущениями, что у нас имеются. И они позволяют исключить только две уникальные даты и не более того.
Если бы дата рождения была 15 мая, то первая фраза Альберта была той же самой, потому что есть всего два критерия: знаю и не знаю. Придумывать критерий — наверняка — что это какая-то степень разновидности не знаю — по меньшей мере — обманывать себя.
А вторая часть фразы говорит о том, что и Бернард не знает даты рождения, то есть у Бернарда нет уникального дня.
… Значит если Альберту известен май, то с вероятностью 1/3 Бернард знает день рождения… Абсолютная глупость. Если что-либо известно Альберту, то это не говорит о том, что это знает и Бернард. Мы можем оперировать только теми данными и допущениями, что у нас имеются. И они позволяют исключить только две уникальные даты и не более того.
Если бы дата рождения была 15 мая, то первая фраза Альберта была той же самой, потому что есть всего два критерия: знаю и не знаю. Придумывать критерий — наверняка — что это какая-то степень разновидности не знаю — по меньшей мере — обманывать себя.
Как же с вами тяжело.
Поменяйте ответ на 15 мая. Что измениться? Будет та же самая первая фраза Альберта. А вот дальше у вас будет затык.
Не будет такой же первой фразы. Т.к. в мае есть 19 число. К-е уникально. И потому Альберт не сможет сказать свою фразу: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Потому что он не будет знать. Он может сказать " я предполагаю, что Бернард тоже не знает", но не «я знаю». Потому что в мае есть уникальное число, блин.
Потому что он не будет знать. Он может сказать " я предполагаю, что Бернард тоже не знает", но не «я знаю». Потому что в мае есть уникальное число, блин.
Началось… И если Бернард при этом покачал головой и щелкнул два раза пальцами — мы поняли, что май нужно исключить. Чем по вашему отличается фраза " не знаю" от фразы «предполагаю, что не знаю»? Степенью вероятности события? Если вы так думаете, ( или хотя может так оно и есть), то тогда да, признаю, что я туп, и эта задача не для меня.
Именно что степенью вероятности события. Я понимаю, что аналогия — не аргумент, но чем отличаются два выражения: я знаю что вы из Москвы и я предполагаю что вы из Москвы. В первом случае я уверен и значит для меня вероятность того, что мы из Москвы = 1. Во втором случае вероятность для меня того, что вы из Москвы 0<p<1.
Спасибо что наконец признались в том, что эта задача не для вас.
Спасибо что наконец признались в том, что эта задача не для вас.
Но ведь Бернард услышав например 19-е число сразу бы сказал, что это май 19е. А раз промолчал и первая фраза за Альбертом, значит Альберт понял, что Бернард не знает и может С УВЕРЕННОСТЬЮ сказать, что ОН НЕ ЗНАЕТ.
И таким образом дата 15е мая вполне подходит под первую фразу и май действительно выкидывается зря.
И таким образом дата 15е мая вполне подходит под первую фразу и май действительно выкидывается зря.
Абсолютно с вами согласен. Из-за одного уникального числа отметают целый месяц.
Решение на 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)));
}
}
Правильно ли я понимаю, что решение задачи о дне рождении возможно только для того кто задачу отгадывает на основе слов Альберта и Бернарда? Альберт ведь не мог прийти к однозначному выводу.
Поначалу вполне логично что остается всего два месяца — июлю, август. Затем Бернард заявляет что знает когда ДР, что вытекает из того что он получил два месяца и зная день рождения узнал месяц. Но на основе чего дальше делает свое заявление Альберт? Он может только сказать что день рождения не 14го числа, а точно назвать цифру сам он не может, ведь так? Зная 15 16 17 Бернард в любом случае узнал бы месяц, соответственно Альберт не может прийти к однозначному выводу.
Поначалу вполне логично что остается всего два месяца — июлю, август. Затем Бернард заявляет что знает когда ДР, что вытекает из того что он получил два месяца и зная день рождения узнал месяц. Но на основе чего дальше делает свое заявление Альберт? Он может только сказать что день рождения не 14го числа, а точно назвать цифру сам он не может, ведь так? Зная 15 16 17 Бернард в любом случае узнал бы месяц, соответственно Альберт не может прийти к однозначному выводу.
Пара-решение в ограничениях условий задачи и последующего диалога всего одна. Вероятность такого развития событий 1/2843, т.е. загадай султан два любых других числа, и мудрецы неизбежно окажутся посрамлены. Везучие мудрецы.
Добавим к этой вероятности требование, что в одном месте в одно время должно быть два человека, обладающих способностью удерживать в голове матрицу в 10 млрд. элементов и запоминать вычеркнутые строки/столбцы.
Таких людей гарантированно нет даже одного, вероятность из 1/2843 превращается в ноль. Поэтому получаем классический парадокс, а поиск решения лишается смысла ;).
Но задача конечно шикарная.
Добавим к этой вероятности требование, что в одном месте в одно время должно быть два человека, обладающих способностью удерживать в голове матрицу в 10 млрд. элементов и запоминать вычеркнутые строки/столбцы.
Таких людей гарантированно нет даже одного, вероятность из 1/2843 превращается в ноль. Поэтому получаем классический парадокс, а поиск решения лишается смысла ;).
Но задача конечно шикарная.
т.е. загадай султан два любых других числа
Он знал! Он знал!
Говорят, Дейкстра решил за шесть часов вариант этой задачи в уме, без бумажки и ручки. Конечно, вероятность встречи двух Дейкстр в одном месте в одно время тоже не особо велика :)
Не та ссылка. Должна была быть эта
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задачи о двух мудрецах и числах от 1 до 100