11 апреля 2015 он разместил на своей странице в Facebook задачу на логику для школьной олимпиады. SASMO (Singapore and Asean Schools Math Olympiads) уточнили позже, что задача предназначалась для детей 14 лет (уровень Sec 3).
Задача ставится следующим образом:
Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат: 15 мая, 16 мая, 19 мая, 17 июня, 18 июня, 14 июля, 16 июля, 14 августа, 15 августа и 17 августа. Затем Шерил сказала Альберту месяц своего рождения, а Бернарду — день. После этого состоялся диалог.
Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Бернард: Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
Альберт: Теперь я тоже знаю, когда у Шерил день рождения.
Когда у Шерил день рождения?
Резонанс в сети, который вызвала эта простая задача, поражает. На момент написания статьи оригинальный пост на Facebook собрал более 5000 репостов и огромное количество комментариев. О задаче также написали Mashable, tj и другие ресурсы.
Почему эта задача вызвала такие дискуссии?
Дат всего 10, а дни находятся в промежутке от 14 до 19. При этом только 18 и 19 числа встречаются по одному разу. Если день рождения Шерил 18-го или 19-го, то Бернард сразу бы мог сказать и месяц.
Но откуда Альберт знает, что Бернард не знает ответа? Если Шерил сказала Альберту, что родилась в мае или июне, значит, её день рождения может быть 19 мая или 18 июня. При таком раскладе Бернард может знать, когда у Шерил день рождения. Факт, что Альберт точно знает о том, что Бернард не знает ответа, говорит о том, что май и июнь можно исключить, а Шерил родилась либо в июле, либо в августе.
Изначально Бернард не знал, когда день рождения у Шерил. Каким образом он узнал ответ после реплики Альберта? Из оставшихся пяти дат в июле и августе, варьирующихся от 15 до 17, только 14 встречается дважды. Если Шерил сказала бы Бернарду, что день её рождения 14-го, значит Бернард после предположения Альберта всё ещё не мог бы дать точного ответа. Тот факт, что он сразу всё понял, говорит о том, что Шерил родилась не 14-го. Остаются три возможные даты: 16 июля, 15 августа и 17 августа.
После того, как Бернард заговорил, Альберт узнал, когда у Шерил день рождения. Если бы она сказала ему, что родилась в августе, Альберт не мог бы знать точного ответа, потому что из трёх оставшихся дат две приходятся на август. Значит, Шерил родилась 16 июля.
Комментарии (136)
Hyston
14.04.2015 17:05+16Интересная задача, но она действительно для школьной олимпиады, а не для аудитории гиков
qbertych
14.04.2015 19:14-3Как раз на нормальных школьных олимпиадах таких задач (на полный перебор) и не бывает.
putnik
14.04.2015 20:37+4Где вы тут увидели полный перебор?
ZlodeiBaal
15.04.2015 05:32Простейший вариант решения таких задач — проверить перебором все даты и то как они подходят под условие. По сути так как она и была решена. Такие задачи помню на кружке по математике в 6-7 классе. Хотя скорее они даже там сложнее были…
qbertych
15.04.2015 11:36Это упрощенная задача про мудреца или про возраст троих детей. Ниже в комментах вам даже код на C# написали, что это еще если не перебор.
Поверьте, составители олимпиадных задач знают гораздо более изящные способы занять школьников.
smiil
14.04.2015 17:20+11Надо просто нарисовать табличку месяц-день, и задачка решается за минуту.
Allen
17.04.2015 10:46+1Согласен, минута или меньше. А вообще достаточно представить как должна выглядеть эта таблица и как по ней искать ответ и желание решать задачу тут же отпадает. Я лично её бросил как неинтересную.
impwx
14.04.2015 17:35+13<irony>В это время Дэниэл сэкономил на ненужных вычислениях, посмотрев дату у Шерил в профиле на фейсбуке.</irony>
PyVolshebnyi
14.04.2015 17:41+21Задачка простая, да. Но она ведь основана на куда более интересной задаче, которую я вам и предлагаю решить. Очень ее люблю.
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.isden
14.04.2015 18:48А можете пояснить логическую последовательность решения этой задачи?
Тут в интернетах пишут разное, и с разными решениями.SKolotienko
14.04.2015 20:15+4Скрытый текстВали (тот, кто знает сумму), знает, что Али (тот, кто знает произведение) не знает ответа. Что это может означать:
Султан сказал Вали такую сумму, что для любых двух чисел, которые могут образовывать эту сумму, не может быть «единственного» произведения. Иначе бы Али тогда мог знать ответ.
Далее мы должны понять, какое есть возможное множество таких сумм, которые султан сказал Вали. Т.е. например для каждой суммы посчитать множество пар чисел, которые составляют эту сумму. Для каждой пары чисел из этих составляющих — посчитать возможное количество других пар, которые могут образовывать одинаковое произведение. Если хотя бы для одной пары есть другая пара с таким произведением, то рассматриваемая сумма не могла быть сказана Вали.
Далее, после того, как Вали сказал «Я это знал», у Али появляется дополнительная информация в виде того множества сумм, что мы получили в предыдущем абзаце. И он пересекает множество пар, которые образуют эти суммы с тем множеством пар, которые образуют его произведение. В данном случае, после пересечения остаётся ровно одна пара, после чего он кричит «Тогда я знаю эти числа».
Вали в свою очередь слышит, что после его информации о множестве возможных сумм получил ответ, и может ограничить количество возможных сумм только до тех сумм, для которых была только одна возможная пара чисел с возможными произведениями больше 1.
Скорее всего можно объяснить как-то проще :)isden
14.04.2015 20:24Скрытый текст> Султан сказал Вали такую сумму, что для любых двух чисел, которые могут образовывать эту сумму, не может быть «единственного» произведения. Иначе бы Али тогда мог знать ответ.
Все, теперь логика понятна, спасибо :) Не хватало именно этой стартовой точки.yosemity
14.04.2015 21:29+3Странно, я вроде бы написал то же самое, но чуть проще (как мне кажется). но меня минусуют, а вас наоборот. Хотя мы вместе ищем логику решения, вспоминается анекдот про Вовочку, когда его выгнали из класса и он рассуждал «где же логика?».
mark_ablov
14.04.2015 20:55+4upd: ох, а тут спойлеры нужны.
Скрытый текстЧисла a, b. p = a * b, s = a + b
1. «Я не знаю этих чисел» => если бы a и b были простыми, тогда можно было бы по p их узнать => как минимум одно из них составное.
2. «Я это знал» => s не разлагается на пару простых чисел. Если гипотеза, что любое чётное число можно разложить на пару простых (для a, b < 100 это очевидно). То есть s нечётно.
3. «Тогда я знаю эти числа» => при нечётном s, p однозначно раскладывается. Сразу понятно, что можно зафиксировать одно число как простое, иначе a1 * a2 * b1 * b2 даёт несколько комбинаций. Кроме того, второе число должно быть степенью простого числа (тоже исходя из однозначности разложения). Получаем a * (b ^ n), n > 1. Так как s нечётная, то возможный нечётный вариант a + b^n достигается только при b = 2 (если не очевидно, то простое доказательство: если b простое и не 2, то нечётное, произведение нечёт даёт нечёт, то есть b^n тоже нечёт, сумма 2х нечёт a + b^n даёт чёт, чего не может быть из предпоссылки).
4. «Тогда и я знаю!». Здесь уже только перебор. Но умный перебор, примерно 10-15 пар.elepner
15.04.2015 09:35Вот еще брутфорс на C#.
Ответ4 и 13omikad
15.04.2015 09:55+1Вот я пытался написать на LINQ посимпатичней: github.com/omikad/omikad-stuff/blob/master/ProblemSets/ProblemSets/Problems/AllyVally.cs
andy1618
17.04.2015 12:26Прикольно — чистенько и красиво!
А как работают Uncertain и Confident? В LINQ такого не припомню, хотя уже давно с C# не работал.omikad
17.04.2015 14:19Спасибо! Это мои хелперы, извиняюсь что забыл указать:
Confident это когда Count() == 1;
Uncertain это когда Count() > 1; (или иначе Skip(1).Any())
Для этой задачи они отражают фразы «я знаю ответ» и «я не знаю»
qbertych
15.04.2015 11:28Если гипотеза, что любое чётное число можно разложить на пару простых (для a, b < 100 это очевидно).
Не совсем понял почему это очевидно для a<100. В голову приходит только перебор (который упрощается если заметить, что 3,5,7 — три подряд идущих простых нечетных числа).
qbertych
15.04.2015 11:49И да, у вас ошибка. В начале 3 шага Али знает, что s — не сумма двух простых. В вашем же решении Али знает, что s — нечетно. Это более общее (слабое) утверждение. Скажем, 5 или 15 нечетны, но является суммой двух простых.
То есть на самом деле Али может быть недостаточно того, что s нечетно.mark_ablov
15.04.2015 12:12Ответ на оба комментария — проблема Гольдбаха. В которой утверждается, что «любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел». (s < 4 я думаю понятно почему не может быть?)
Соответственно из этого следует что можно исключить все чётные числа из рассмотрения s => принимаем что s — нечётное, что достаточно для дальнейшего анализа.
Из комментария не понял, где же ошибка.qbertych
15.04.2015 16:13Ну вы же понимаете что это недоказанная гипотеза.
Насчет ошибки: представьте, что p такое, что у Али есть три варианта разложить его на множители. Соответственно, он знает три возможных s. Пусть это будут четное x, нечетное y и нечетное z=15. Что происходит после реплики Вали:
По вашей логике, Али понимает, что четное x не подходит. Остаются два варианта и он пока не знает ответа.
На самом деле Али понимает, что не подходят x (оно четное) и z=15=2+13 (тогда реплика Вали неверна). Вуаля, остается y.mark_ablov
15.04.2015 16:24Это-то понятно, только применимости в дальнейшем я не увидел.
Более слабого ограничения достаточно.
KOLANICH
15.04.2015 22:21Моё решение без перебора (извините за отсутствие спойлера, карма не позволяет):
1 аналогично
2 нечётность суммы идёт из того, что все простые числа нечётны, сумма простых всегда чётна, и если бы сумма была чётной, Вали не мог бы знать, что число не является произведением простых. Тогда одно число чётно, другое — нечётно.
3 «Тогда я знаю эти числа». Число способов собрать сумму s в виде a+b растёт с ростом s, а значит с ростом s растёт и энтропия (напоминаю, H=\sum_i-p_i*log_2{p_i}). Чтобы узнать число, нужно чтобы предыдущий ответ снизил энтропию до нуля, что означает, что нам нужно минимальное s. Берём первые 2 простых числа: 2 и 3. Делаем минимальное непростое число: 2*2=4. 7=2*2+3 12=3*4.
mark_ablov
14.04.2015 18:56+1Ага, классика, помню еще в универе наткнулся на неё. Вместе с преподом матлогики решали :)
Так что задача из топика решилась довольно просто для меня.
yosemity
14.04.2015 19:45+1Я думаю, что логика такая. Вали услышал, что Али не знает и подсказал Али, что так и знал. Али понял подсказку и нашел те самые два числа, которые:
1) больше 1 и меньше 100.
2) результат их умножения может быть результатом умножения других чисел так же в диапазоне от 2 до 99, и при этом
3) результат их сложения так же может быть результатом сложения других чисел 2 до 99.
Вроде так, осталось найти два числа ))
x3gluk
15.04.2015 12:20+2А еще есть такая задачка:
Между двумя приятелями произошел такой диалог:
— Привет!
— Привет!
— Как дела?
— Хорошо. Растут два сына, дошкольника.
— А сколько им лет?
— Произведение их возрастов равно числу голубей около этой скамейки.
— Этой информации мне недостаточно!
— Старший похож на мать.
— Вот теперь я знаю ответ на свой вопрос!
Назовите возраст сыновей.mark_ablov
15.04.2015 13:29+3Скрытый текст1, 4?
1 <= a, b <= 7
Так как после получение информации о том что есть старший ребёнок, то есть a != b, был найден ответ, значит до этого была неоднозначность и рассматривались варианты с a = b, эти варианты 1, 4, 9, 16, 25, 36, 49. Очевидно что подходит только 4 (альтарнтивное разложение 1 * 4), ну и с натяжкой 16 (2 * 8), если расширить понятие дошкольник ;)
Solovej
15.04.2015 15:57Так а сколько голубей у скамейки? Где данные?
x3gluk
15.04.2015 16:09Данных хватает, главное понимать, что оба приятеля видят сколько голубей.
Solovej
15.04.2015 16:29Так может быть:
1 и 6
1 и 5
1 и 4
1 и 3
1 и 2
2 и 3
Gunnar
15.04.2015 16:38Если бы было 6 голубей: знания, что один из них старше не хватило бы, т.к. возможные разложения — 3*2 и 6*1
Если бы было 5 он бы сразу сказал, что им 5 и 1
4 — неоднозначность
3 — сразу понятно что 1 и 3
2 — сразу понятно что 1 и 2
1 — неодноначность
Далее второй говорит, что один из них старше. Значит 1*1 и 2*2 отпадают. Остается 4*1
Mrrl
15.04.2015 16:38+1Если голубей 6, то детям может быть либо 1 и 6 лет, либо 2 и 3. В обоих случаях информация «Старший похож на мать» ничего не даёт, вариантов остаётся два. Если голубей 5, то второй сразу скажет, что первому 5 лет, а второму 1 год.
viktorpanasiuk
14.04.2015 17:47+1Факт, что Альберт точно знает о том, что Бернард не знает ответа, говорит о том, что май и июнь можно исключить, а Шерил родилась либо в июле, либо в августе.
Странное умозаключение у tjournal. Не уловил никакой логики.
Мое решение следующее:
- Бернард не сказал сразу — значит не 18 мая и не 19 июня;
- Если бы Альберту сказали июнь, он бы однозначно дал ответ 17 июня, так как это последнее оставшееся в этом месяце. Раз не сказал — июнь можно исключить полностью;
- Из 17-х чисел остается только 17 августа;
- Теперь идем с другого конца, если бы Бернарду сказали 14, 15, 16, никто бы из них не смог дать окончательного ответа, так как в каждом случае варианта два;
- Раз Бренард с уверенностью сказал что знает дату, остается только 17 августа;
- Мысля также, и после слов Бернарда, Альберт также окончательно останавливается на этой дате;
Gunnar
14.04.2015 17:57+9Логика там абсолютно правильная — тот факт, что Альберт может с уверенностью утверждать, что Бернард не знает, значит что Май и Июнь отпадают. Иначе был бы шанс, что число 18 или 19.
В (6) у вас ошибка — Альберт не может мыслить так же как Бернард, т.к. он знает только месяц.
viktorpanasiuk
14.04.2015 18:10В мае, помимо 19-го еще два числа, в июне, помимо 18-го есть еще 17-е. Если у Бернарда 15-е, 16-е или 17-е, что мешает иметь их в мае или июне? В 6 никакой ошибки, мыслят они по шагам и приходят к одним и тем же умозаключениям.
Альберт не может утверждать что Бернард не знает овтета. Он взял его на понт, потому что Бернард сразу не выдал что это 18-е или 19-е. Но ключевым, в дальнейших рассуждениях Бернарда, является фраза что Альберт также не знает ответа (не 17 июня).yosemity
14.04.2015 19:11+6Альберт точно знает, что Бернард не знает дату, т.к. Альберт знает месяц. Тем самым подсказывая Бернарду, что это не май и июнь, т.к. Альберт точно знает месяц, а уникальные цифры только 18 июня и 19 мая и Бернард сразу бы дал однозначный ответ.в остальных месяцах есть еще варианты. После этого Бернард делает вывод, что остается только июль и август. Но бернард знает дату и говорит, что знает ответ, т.е. это не 14 число, т.к. он бы тогда не мог точно сказать дату ДР, не зная месяца. А Альберт знает месяц и говорит, что знает ДР, т.к. если бы это было не 16 июля, то Бернард не смогу бы однозначно выбрать между 15 и 17 августа.
В ответе
«Альберт не мог бы знать точного ответа, потому что из трёх оставшихся дат две приходятся на август
стоит заменить Альберт на Бернард. Это путает.Petrik
14.04.2015 20:05-1Если убрать догадки, что Альберт пытался подсказать своей первой фразой, то 17 августа выходит самым логичным ответом.
Как у автора выше.
pushist1y
15.04.2015 15:04Я понимаю всё до последнего шага.
Ок, май и июнь исключили, после этого Бернард, зная число, точно понимает дату. Значит, это не 14 число. Значит, это 15 или 17 августа или 16 июля. И Бернард точно знает, какой из этих трёх дней верный, о чём и заявляет. Как на основании это информации Альберт может сделать правильный вывод?viktorpanasiuk
15.04.2015 15:23+1Он же сказал что также знает ответ, значит его месяц — июнь, иначе от него мы бы такого ответа не услышали.
Gunnar
15.04.2015 16:28+1Альберт знает что месяц — июль, а со слов Бернарда от теперь знает что число не 14. Значит остается Июль 16
freeeeez
14.04.2015 22:44По этой логике из 3-его пункта следует, что до этих умозаключений могли додуматься оба, а значит 17 августа остается в одном экземпляре, а следовательно если бы Бернард знал 17, он бы сказал 17 августа, значит это число вырезаем. Т.е. оба до разговора уже знали что 17-е числа, 18 и 19 не учитываются… Или нет?
viktorpanasiuk
14.04.2015 23:05Альберт ждал, ведь если бы у Бернарда было 18 или 19 — он сказал бы что знает ответ. Но раз нет, теперь ждет Бернард, даже если у него 17 число, ведь вариантов 2: июнь или август. Если молчит Альбертушка, значит явно его месяц не июнь, ведь он бы выдал ответ. Это является поводом исключить июнь и оставить август. Вот если у Бернарда были бы иные числа, они бы еще долго сидели и думали и никто бы из них не сказал что знает ответ.
freeeeez
14.04.2015 23:15Вот именно, из этого умозаключения если бы Альберту сказали июнь — он бы сразу сказал ответ 17. А раз он не сказал, значит июнь исключаем. Но это и Бернард понимает, не так ли? Т.е. если бы да кабы, короче если Шерил сказала Бернарду 17 вначале, то он бы сразу дал ответ август, ведь путем этих умозаключений отсается только 17 августа, и это, заметьте, все до разговора! Так что 17 августа тоже нужно исключить и решение ваше не верное. Но я дальше не знаю как, помогите развить ход событий…
yosemity
14.04.2015 23:29Я тоже ушел не туда, исключив 17 августа и застрял в тупике. Но покурив, попив чайку вернулся к началу. смотрите мой каммент geektimes.ru/post/249014/#comment_8333188
freeeeez
14.04.2015 23:37+1почитал, "… Тем самым подсказывая Бернарду, что это не май..." откуда вы все это взяли?? в мае 3 дня! 19 исключаем (это да), но 15 и 16 остается… во всех ответах пишут «и май исключаем» но не пишут почему исключаем сразу два дня. с какого?? почему объясните исключается 15 и 16 число в мае, только это хочу знать, потому что никто не может объяснить. Типо если бы у Альберта был май, Бернард бы сразу знал день рождения… Но ведь даже если и так у него могло бы быть как 15 так и 16 или я тупой?
yosemity
14.04.2015 23:58Перечитал свой каммент, да сбивчиво. Щас поясню. Вот так верно:
1) если бы это был 19.05 или 18.06, то Бернард дал бы сразу ответ, но не дал и Альберт делает вывод, что это не 18 и 19 соответственно.
2) Альберт знает месяц, но утверждает, что Бернард не знает, т.к. если бы это был май или июнь, то Бернард мог бы знать это и подсказка.
3) Бернард все понял и говорит что знает, выбирая между июлем или августом. но 14 быть не может, т.к. Бернард бы не дал однозначного ответа.
4) остается 16.07, 15.08 и 17.08. Но Альберт знает месяц, а если бы это был Август, то не знал бы.
sielover
15.04.2015 00:06+1Типо если бы у Альберта был май, Бернард бы сразу знал день рождения…
«Так, у меня май. У Бернарда может быть 15, 16 или 19. Если у него 15, то он не знает месяц (может быть май или август). Если у него 16, то аналогично, май или июль. Но если у него 19, то он знает точную дату, т.к. 19-е только в мае. Значит, я не могу утверждать наверняка, что Бернард не знает точную дату. Возможно, он знает»freeeeez
15.04.2015 00:10… поэтому Альберт и утверждает наверняка, что Бернард не знает, потому что у него может быть как 15 так и 16, даже если у Альберта май?
sielover
15.04.2015 00:16+1Если бы у Альберта был май, он бы так не утверждал. Ибо не может быть уверен наверняка. А поскольку утверждает, то у него не май.
Для сравнения
«Так, у меня июль. У Бернарда может быть 14 или 16. Если у него 14, то он не знает месяц (может быть июль или август). Если у него 16, то аналогично, май или июль. Значит, я могу утверждать наверняка, что Бернард не знает точную дату.»
«Так, у меня август. У Бернарда может быть 14, 15 или 17. Если у него 14, то он не знает месяц (может быть июль или август). Если у него 15, то аналогично, май или август. И 17 — июнь или август. Значит, я могу утверждать наверняка, что Бернард не знает точную дату.»freeeeez
15.04.2015 00:21И из этих ваших двух ответов получается что все три случая равнозначны, ведь во всех их трех имеются даты 14, 15 и 16. и каждый раз по две даты. 17 августа исключается за счет того, что если бы Бернарду сказали в начале 17, то он бы сразу дал ответ — август. Потому что 18 и 19 в одном экземпляре, а если бы был июнь, то Альберт назвал бы.
Mrrl
15.04.2015 00:19Если у Альберта май, то он не может утверждать «Бернард не знает», потому что тогда у Шерил может оказаться 19 мая — и в этом случае Бернард будет знать день сразу.
freeeeez
15.04.2015 00:23Я понимаю вас всех, кто говорит «Альберт не стал бы утверждать, ведь май и все такое...» но согласитесь — это все притянуто за уши. Решение задачи сводится к «если бы да кабы», а это уже не четкий ответ.
yosemity
15.04.2015 00:24Перечитайте же это
geektimes.ru/post/249014/#comment_8333516
и это
geektimes.ru/post/249014/#comment_8333538freeeeez
15.04.2015 00:34Перечитал и понял, что решение задачи сводится к тому, как интерпретировать реплику Альберта, либо он берет на понт, либо утверждает, а утверждать наверняка с таким большим набором дат он не может. Мне кажется «берет на понт», ведь наверняка знать что это не 15 мая он не может? (до первой фразы), так же он не может знать что не 16 мая. (ну при условии что это май)
Короче, объясните наконец, почему не 15 и 16 мая? Почему май исключаем только потому, что 19 одно число, ведь в мае еще два? Почему тогда в официальном ответе в сети ответом является 16 июля???SkidanovAlex
15.04.2015 00:37Я вам объяснил ниже, но тут отвечу на ваш конкретный вопрос.
Пусть это 15-ое Мая.
Тогда Альберт знает, что месяц Май.
Тогда, с точки зрения Альберта, дата может быть 19-ое Мая (Альберт не знает день)
Тогда Бернард может знать ответ.
Тогда Альберт не может сказать, что Бернадр не знает ответ.
Но Альберт говорит, что он уверен, что Бернадр не знает ответ.
Значит это не Май.
В таких задачах всегда предполагается, что участники не врут. Конечно, если Альберт берет Бернарда на «понт», как вы говорите, то задача не имеет смысла. Тогда и Шерил могла дать изначально неправильный список дат: о)freeeeez
15.04.2015 00:39Пусть это 15-ое Мая.
Тогда Альберт знает, что месяц Май.
Тогда, с точки зрения Альберта, дата может быть 19-ое Мая (Альберт не знает день)
----Также с точки зрения Альберта дата может быть 16-ое мая? Или не может?
Тогда Бернард может знать ответ.
Тогда Альберт не может сказать, что Бернадр не знает ответ.
Но Альберт говорит, что он уверен, что Бернадр не знает ответ.
Значит это не Май.SkidanovAlex
15.04.2015 00:43Она может быть и 16-ое Мая (и 15-ым, которым она является) с точки зрения Альберта. Это не противоречит моим рассуждениям. Важно, что она может быть 19-ым, а значит Альберт не может утверждать, что Бернард не знает ответ.
freeeeez
15.04.2015 00:44Пусть это 15-ое Мая.
Тогда Альберт знает, что месяц Май.
Тогда, с точки зрения Альберта, дата может быть 19-ое Мая (Альберт не знает день)
----Также с точки зрения Альберта дата может быть 16-ое мая? Или не может?
Тогда Бернард может знать ответ.
Тогда Альберт не может сказать, что Бернадр не знает ответ.
— Может ведь у Бернарда может быть как 15 так и 16 и оба под май подходят)))
Но Альберт говорит, что он уверен, что Бернадр не знает ответ.
Значит это не Май.SkidanovAlex
15.04.2015 00:47Вы не правы. Да, у Бернадра может быть 15-ое или 16-ое, и тогда Бернадр не знает ответ. Но у него может быть 19-ое, тогда он знает ответ. Для того, чтобы ваши рассуждения работали, Альберт должен сказать:
— Я не знаю ответ, но возможно Бернадр тоже не знает (ведь у него может быть 15-ое или 16-ое)
Но он говорит
— Я не знаю ответ, и я уверен, что Бернадр не знает ответ.
Альберт не может быть уверен, потому что в Мае есть день, при котором Бернадр знал бы ответ.
yosemity
15.04.2015 00:44Вам жирный шрифт чтоль не отображается? Повторю, выделю.
Альберт _утверждает_, что Бернард не знает. Если бы это был май или июнь, то Бернард _мог_бы_знать_ и это подсказка.freeeeez
15.04.2015 00:51Мне все отображается как и всем, я пользуюсь обычным браузером, но вы повторяете одно и тоже во всех комментариях и не отвечаете на мои вопросы:(( Тогда ответьте почему ответ yaptro — 16 июля — не верный? Этот ответ на всех остальных сайтах, только у вас 17 августа
yosemity
15.04.2015 00:53Если вы мне, то верный ответ — 16 июля. Я не понял как вы решили, что мой верный ответ 17 августа? Я сказал, что я пошел по неверному пути и застрял на 17 августа. Оставаились еще 15,16 мая, 14,16 июля и 14,15 августа.
Mrrl
15.04.2015 00:5416 июля верный ответ. Но раз он на всех остальных сайтах, то его никто и не пишет, а просто говорят «я решил».
yaptro Автор
15.04.2015 00:44Реплики авторов следует принимать за истинные реплики (в сопутствующих системах отсчёта, так сказать). Это значит, что Альберт и Бернард не врут друг другу.
В первой реплике Альберта (Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает) очень важна последняя часть. Она как-бы предупреждает попытки Альберта соврать (сказав, что день 18 или 19), т.к. Бернард знает, что это не может быть 18 или 19 день, т.к. он знает месяц, и месяц этот не июнь или май.
Вообще, конечно, как и в случае с платьем, проблемы возникают с интерпретацией информации, пониманием её (в данном случае задачи). Тогда спор крутился вокруг того, как человек воспринимает цвета (не просто как компьютер, а с последующей обработкой в мозгу). Сейчас проблемы возникают на почве того, что не задана точно логическая база, т.е. непонятно, чем считать высказывания Альберта и Бернарда, и с какой точки зрения их рассматривать. Если вообразить это всё в реальности, то дата 16 июля, как никакая другая, «вписывается» в диалог как реальную жизненную ситуацию.
viktorpanasiuk
15.04.2015 09:32Ваши мысли очень забавны. Экстраполируя результат на второй случай, если бы Бернарду сказали число 16, он бы сразу ответил 16 июля еще до начала разговора. Как-то так… Бернард, имея число 17 смог бы дать ответ только после слов Альберта что я также не знаю ответ (не 17 июня), иначе варианта по-прежнему два.
SkidanovAlex
15.04.2015 00:15Вы не правы в опровержении логики tj. Логика у tj абсолютно верная.
Если дата Май, 18 или Июнь, 19, то Бернард знает ответ сразу, до первой реплики.
Однако, Альберт утверждает, что он уверен, что Бернард не знает ответ. Но Альберт знает только месяц. Из этого следует, что месяц не Май и не Июнь. Если бы это был Май или Июнь, то Альберт не мог бы быть уверен, что Бернард не знает текущую дату. Почему? Допустим, что месяц — Июнь. Это все, что знает Альберт, он не может знать, что дата — не 19-ое Июня, а потому не может знать, что Бердард не знает ответ.
Поэтому после первой реплики Бернард знает, что месяц — Июль или Август.
Верный ответ — 16-ое июня. Чтобы понять почему, давайте рассмотрим мысли Альберта после того, как он узнал, что Бернард знает ответ (то есть после второй реплики):
1. Пусть месяц — Август. Я знаю, что число не 14-ое. Но оно может быть 15 или 17. Я не знаю день рождения
2. Пусть месяц — Июль. Я знаю, что число не 14-ое. Оно может быть только 16. Я знаю ответ.
Если вы все еще не согласны, то уточните с чем, можно будет разобрать отдельно.
В вашем решении я вижу ошибку в первом же утверждении. Вы говорите, что утверждение Бернарда уничтожает только Май 18 и Июнь 19, но на самом деле еще до утверждения Бернарда Май и Июнь уже были полностью убраны из рассмотрения.yosemity
15.04.2015 00:19Да, да, вы правы. Ключевой момент, что Альберт утверждает, что Бернард не знает. Я попытался разжевать тут geektimes.ru/post/249014/#comment_8333516
Но сам решал задачу относительно долго, т.к. ушел не тем путем. Смотрите.
Альберт убрал 18 и 19, т.к. Бернард не сказал ответ сразу, но сам Альберт сказал, что не знает, а если бы это был июнь, то Альберт бы однозначно назвал дату, там осталось только 17 августа. Исходя из этого, если бы это было 17 августа, то Альберт бы не утверждал, что Бернард не знает.
viktorpanasiuk
15.04.2015 09:23На месте Альберта, спустя некоторое время, не услышав 18-е или 19-е, я могу с уверенностью утверждать что Бернард точно не знает овтета. Вот такие умозаключения возникли сразу в моей голове.
A1MaZ
14.04.2015 18:25+38Мне больше всего понравилось «мужское» решение с tj.
18+
freeeeez
14.04.2015 22:46-2там указано 16 июля, как в большинстве источников, но при решении все говорят «можно исключить май» хотя в мае 3 дня указано. июнь понятно почему исключаем, но в мае остается 15 и 16. если следовать методом исключения и то и то подходит и исключить эти числа невозможно
SkidanovAlex
15.04.2015 00:24+5Пусть это Май. Рассмотрим, что происходит до первой реплики. Альберт знает, что это Май. Альберт не знает число — то есть, число может быть и 19. А может не быть. Но если число 19-ое, то Бернард знает ответ. Если число не 19-ое, то он не знает. То есть если месяц Май — то Бернард, с точки зрения Альберта, может знать ответ, а может не знать. Но Альберт утверждает, что Бернард НЕ знает ответ. Если месяц — Май, то Альберт не мог бы этого утверждать.
janatem
15.04.2015 12:01+1Отсюда можно вывести несколько более серьезную задачу по криптографии. Пусть А и Б не доверяют друг другу в том смысле, что если кто-то первым сообщит свою часть информации, то второй может его «кинуть», не сообщив свою часть. Получится, что второй узнал всю информацию, а первый нет. Тогда задача состоит в том, чтобы придумать протокол, защищающий А и Б друг от друга. Разумеется, можно записать ответы на бумажке, но хочется получить криптографически чистое решение.
andy1618
17.04.2015 12:33Помнится, у Шнайера был описан криптографический протокол подбрасывания монеты по телефону.
dom1n1k
15.04.2015 01:08+1Сюжет баянный.
Видел аналогичную задачу давным-давно, только там были не даты, а два числа. И одному человеку сообщалась сумма, а другому произведение. И далее именно такой же диалог: «я не знаю и он не знает — теперь я знаю — теперь и я знаю».
Там комбинаций гораздо больше, и авторское решение было очень громоздко и при этом совершенно неинтересно — тупо перебор вариантов.
yosemity
15.04.2015 02:08+7Хорошо, для тех, кто любит в графике. Вроде ничего не упустил.
Mrrl
15.04.2015 02:15+1Проблема в первом же пункте: «Бернард не сказал сразу же дату ДР». Вообще-то, Бернарда никто не спрашивал, он не обязан был ничего говорить, и использовать то, что он промолчал, в решении никак нельзя.
yosemity
15.04.2015 02:17Это очевидно. Если бы Шерил сказала 18 или 19 Бернарду, то задача не имела бы смысла. Ведь парням для подката надо было знать, когда ей на ДР дарить ништяки. ;)
mrxak
15.04.2015 04:05Почему до начала разговора нельзя исключить 17 августа?
1. Бернард молчит, то есть не 18 июня,
2. Альберт молчит, то есть ему сказали не июнь
3. Если бы Бернарду сказали 17, то он бы сразу (ну, скажем, после первого акта молчания) сказал бы август.Mrrl
15.04.2015 04:16+2Мы не знаем, когда они прочитали почту. Поэтому из молчания делать выводы нельзя. Первым начал говорить Альберт — возможно, он раньше добрался до смартфона с сообщением.
AlexTest
17.04.2015 02:224) Бернард, зная число, выбирает единственно правильный ответ и говорит, что знает дату ДР
Ну вот как на вашем 4-м шаге Бернард может дать единственно правильный ответ, зная только число и исключив два первых месяца?
Он ведь еще не услышал последней фразы Альберта (что Альберт тоже знает дату ДР)?
Как мне кажется в такой постановке эта задача на 4-м шаге для Бернарда не имеет решения, и он никак не может на этом шаге заявлять, что он знает решение — ему просто не хватает информации (той, что скажет Альберт в будущем)!
Но все остальное рассуждение строится именно на том, что уже на 4-м шаге Бернард знает правильный ответ, причем не только у вас.
Возможно я не прав, но я думаю, что задача в такой постановке просто не имеет решения (если учитывать очередность событий ).AlexTest
17.04.2015 02:47Т.е. задача имела бы единственное решение, если бы в условии было так:
Выберите единственно возможную дату ДР, при которой заявления всех участников верны без учета их очередности во времени.
AlexTest
17.04.2015 03:14я не совсем правильно в первом своем посте написал про Бернарда, он то конечно может дать на этом шаге правильный ответ, если Шерил сказала ему любое из чисел 15,16,17, т.к. они однозначно указывают на конкретный месяц: 15 и 17 на Август, а 16 на Июль. Т.е. возможны все три варианта на 4м шаге, и только если Бернарду было сказано 16 число, последнее утверждение Альберта может быть верным, подчеркиваю — именно МОЖЕТ БЫТЬ ВЕРНЫМ! Т.е. как я и писал выше в задачу надо добавить условие:
Выберите единственно возможную дату ДР, при которой заявления всех участников МОГУТ БЫТЬ ВЕРНЫ без учета их очередности во времени.yosemity
17.04.2015 18:54Все верно. Я, вы и прочие читатели ищем решение, а не Бернард и Альберт. Мы уже знаем, все сразу. Мы знаем все шаги. И из этого строим логический вывод. Рассматривайте условия проще. Есть, а) б) в)… etc). Ищем ответ.
scottKey
15.04.2015 10:39+1Я не совсем понял почему вначале откидывается Май, т.е. 15 и 16 Мая?
viktorpanasiuk
15.04.2015 10:47+1Потому что Альберт со 100% уверенностью утвеждает что Бернард тоже не знает. Такое возможно только если Альберту сказали июль или август. В противном случае (май, июнь) он бы не мог со 100% вероятностью такое утверждать, так как там есть 18-е и 19-е (ответ Бернарду может быть известен).
kramolnik
15.04.2015 11:48Если перефразировать диалог, то будет понятнее:
— Я так понимаю, что у тебя неопределенность с цифрами дат, значит месяцы с уникальными датами можно исключить.
— Да, теперь когда мы исключили месяцы с уникальными датами неопределённость исчезла.
— Ну значит и я теперь вижу точную дату.
cybermerlin
15.04.2015 13:44позвольте подправить ход мыслей:
— А утверждает, что Б не знает = числа должны быть повторяющимися
— НО т.к. А знает месяц = он отметает май и июнь полностью, потому что 18 и 19 туда попадают
— допущение — Б сказали 16 — значить отметая май и июнь мы получаем 16 июля
(- НО если Б сказали 14 — то он не может знать)
— после озвучки А тоже понимает, что число оставшееся без повторений = 16
и еще ложку дёгтя во всю эту логику:
— Допустим А — умный человек и не станет пороть чуши подсказывая, что это не Май и Июнь опираясь только на уникальность чисел, Да он ДОГАДЫВАЕТСЯ, что Б МОЖЕТ и не знать ДР, опираясь, что числа 18 и 19 уникальны и Б уже прыгал бы от радости, ТОГДА остаются только парные числа.
— И допустим и Б не станет пороть горячки думая, что А исключил с числами 18 и 19 и эти месяцы!
— Тогда больше никто ни до чего не догадается
Исключать остальные месяцы и числа — сущая глупость или «пальцем в небо» пока не озвучит кто-то свои данные.
Так что это задача на «нелогичность»
правильный ответ:
у Шерил др красного цвета деревянный стул.
Solovej
15.04.2015 16:04-5Извините о какой логике можно рассуждать если нет исходных данных на которые можно опираться? Массив цифр это не исходные данные.
Смотреть кто сколько раз «мигнул» во время разговора и делать на основе этого выводы?
Такие логические задачи пишут логики со своей логикой, такую логику могут решить только такие же «себе подобные».
С таким успехом можно написать любую логическую задачу, «половина» планеты решит что автор чудила, а половина даст верный ответ. Почему? Да потому что логика у всех разная. Она не может быть одинаковой.
HeadFore
15.04.2015 16:35+1Бинарная логика тоже у всех своя?
Вот вам задачка попроще:
1 мая 2 мая 3 мая
2 июня 3 июня 4 июня
Альберту сказали месяц, Бернарду день.
Бернард сказал что знает полную дату.
После этого Альберт тоже сказал, что знает.
Что, тут тоже ваши «перемигивания»? Нет исходных данных?x3gluk
15.04.2015 16:43+1Ну это не правильный пример, правильный:
2 мая 3 мая
2 июня 3 июня 4 июня
Альберту сказали месяц, Бернарду день.
Бернард сказал что знает полную дату.
После этого Альберт тоже сказал, что знает.Mrrl
15.04.2015 16:46+1А здесь информации слишком много. Альберту даже не нужно знать месяц — после реплики Бернарда уже весь мир всё знает.
Mrrl
15.04.2015 16:50+1Так и случилось. Половина пыталась решить задачу, а остальные сказали, что друзья должны послать Шерил подальше и найти себе более адекватных девушек.
Quetz
15.04.2015 22:09+2Если кому-то понравилась задача, рекомендую книгу Принцесса или тигр. С удовольствием решала подобные логические задачки лет в 10. Правда, тогда не смогла осилить третью и четвертую части =)
Sna1L
16.04.2015 20:52А мне нравятся такие задачи. В них не нужно специальных знаний, нет никаких «ловушек».
Дан набор информации, а ты просто должен собрать ее в кучу и сделать вывод, который и станет ответом.
P.S. решил за 3 минуты, но есть ощущение, что что-то упустил, поэтому через несколько часов решил перешать, но более обоснованно, формулируя мысли чуть ли не вслух. Ушло минут 5.
P.P.S постскриптум был к тому, что такие задачи все-таки немного некорректно решать в быстром темпе на скорость, поскольку можно сделать не совсем обоснованный вывод, который совпадет с ответом, а ты будешь гордо ходить, так и не решив(по сути) задачу=)
Sna1L
16.04.2015 20:55Почему эта задача вызвала такие дискуссии?
Я тут вспомнил скриншот из «Одноклассников», где люди ожесточенно спорили, чему равно 1+1+1+1+1+1*0.
Так что я бы не удивлялся.andy1618
17.04.2015 12:40-2Скорее, это более типично для фейсбука, где много людей с «заграничным образованием» ;)
Sna1L
17.04.2015 16:57Простите, но Вы слишком предвзято относитесь к «буржуям». Всякого необразованного быдла везде хватает, в т.ч. и в нашей необъятной Родине. Люди есть люди. От того, что они находятся в Евразии, они умнее не становятся.
andy1618
17.04.2015 20:56Я не про географию, а про образование.
Для меня, к примеру, показательно, что в турнирах Google Code Jam процент попавших в финал из России на порядок(!) выше, чем, к примеру, из США, и это при том, что условия задач на английском.
Вот пример статистики по 2014-му году:
www.go-hero.net/jam/14/regionsSna1L
18.04.2015 12:18Это не показатель.
В отместку могу сказать, что в ИТ-сфере больше открытий сделано учеными с «заграничным образованием». Но и это не показатель…
ilrandir
17.04.2015 16:20Тоже нарисовал в виде таблички:
Кстати друзья из Америки рассказали что если day, то имеется ввиду число, а если day of the week, то день недели. Потому что я вначале немного не так понял условие задачи.
floppox
22.04.2015 13:31Занимательно выглядят дебаты. Одни люди видят единственно верное решение и называют его (единогласно, заметьте). Другие его не понимают, и утверждают что «нет логики». Вот так и всегда в жизни, у кого-то логика есть, а у кого-то нет.
Mrrl
22.04.2015 18:17Если посмотреть другие дискуссии, то видно два «единственно верных» решения — 16 июля и 17 августа. Основное различие в рассуждениях — можно ли по характеру первой реплики сказать, что ни А, ни Б не смогли вычислить день рождения ни по своим данным, ни по молчанию другого.
Хотя я их не понимаю: Б вычисляет 17 августа на третьем такте молчания, безо всякого диалога. А если не вычислил — остаётся 6 дней, которые уже никак не различишь.floppox
22.04.2015 18:28Если вы о решении viktorpanasiuk, то его ошибку давно указали.
Mrrl
22.04.2015 18:55Нет, я о рассуждениях на facebook и в прочих местах (давно смотрел, сейчас не помню).
И у задачи про торт два единственно верных решения… но корреляции между ответом на ту задачу и цветом платья так и не нашли.
isden
Извините, но как??
Несколько раз перечитал текст задачи и решение, но так и не понял логики. Я уже слишком стар для таких задач?
orcy
Тут задачка на логику, догадаться можно, так что не очень понятно почему такая популярность для задачи. Я думаю было бы круче если бы финальный вопрос был бы «Какого цвета платье у Шерил?». Тогда обсуждать задачку можно было бы долго.
dvserg
Темно-синего или золотого.
Error_403_Forbidden
Альберт и Бернард зашли в профиль фейсбука Шерил
isden
geektimes.ru/post/249014/#comment_8333112 :)
Shark
Просто у Бернарда интернет быстрее.
macik_spb
Вспомнилась задачка про трех мудрецов и колпаки.
Mithgol
Позвольте сообщить Вам решение задачи в тех выражениях, которыми я сам сформулировал его ещё до того, как поглядел в решение TJournal.
Первая часть первой реплики Альбера очевидна: каждый месяц содержит две или три возможные даты, так что Альбер, знающий только месяц, не в состоянии угадать дату.
Вторая часть первой реплики Альбера означает, во-первых, что Бернар получил такое число, по которому нельзя угадать дату (то есть среди десятка дат есть две возможные даты, приходящихся на это число в разные месяцы); следовательно, Бернар не мог узнать от Шерил число «19» (что сразу означало бы «19 мая») и число «18» (что сразу означало бы «18 июня»). Во-вторых, если Альбер способен догадаться об этом, то Шерил сообщила ему не «май» и не «июнь», а «июль» или «август».
Первая часть реплики Бернара является просто подтверждением верности догадки Альбера. Вторая часть его реплики означает, что Бернар знает такое число, одна из возможных дат которого приходится на май или июнь, а вторая на июль или август, так что сообщение Альбера позволяет ему не колебаться долее. Это значит, что Шерил сообщила Бернару не «14» (ведь тогда он продолжал бы колебаться между июлем и августом), а «15» (что с учётом сообщения Альбера означает «15 августа», но не «15 мая») или «16» (что с учётом сообщения Альбера означает «16 июля», но не «16 мая») или «17» (что с учётом сообщения Альбера означает «17 августа», а не «17 июня»).
Сообщение Бернара (о том, что число — не четырнадцатое) достаточно, однако, для Альбера, который после этого узнаёт дату. Это означает, что Шерил сообщила Альберу «июль» (что после исключения четырнадцатого числа означает «16 июля»), а не «август» (потому что тогда Альбер не мог бы выбрать между пятнадцатым и семнадцатым числом августа).
Дата дня рождения Шерил — 16 июля.