День рождения Алины
В этих ваших интернетах сегодня ходит задачка, заданная сингапурским школьникам на каком-то экзамене. Она вызвала ожесточенные споры, так что сингапурскому ОНО - или как у них там ОНО называется - даже пришлось давать целое длинное разъяснение того решения, которое они посчитали правильным. Так вот, решение их неправильное. [см. доб
( Read more... )
Условие задачи таблицей:
-------------------------------
май: 15 16 19
июнь: 17 18
июль: 14 16
август: 14 15 17
-------------------------------
Фраза "я знаю что, что он знает", это значит что у кого-то множество вариантов проецируется на чужую ось без наложений, по одному варианту в каждую точку проекции (инъективно).
Чтобы Денис знал о дне рождения сразу - для этого день рождения должен приходится на число с единственным месяцем, т.е. 18 или 19.
Из фразы: 'Митя: Но я знаю, что и Денис не знает!' я (и Денис) делаю ввывод, что Алина шепнула Мите про июль или август, в противном случае Митя не был бы уверен что Алина не шепнула Денису про 18-е или 19-е число.
-----------------------
июль: 14 16
август: 14 15 17
-----------------------
Из фразы: "Денис: а я теперь знаю, когда твой день рождения!" следует, что д.р. 15, 16, или 17 (14 не подходит, так как для него подходит два оставшихся месяца, и тогда бы Денис не знал месяц).
----------------------
июль: 16
август: 15 17
----------------------
Из фразы "Митя: тогда и я знаю!" я заключаю, что др 16 числа. Так как множество из (август,15), (июль,16), (август,17) - проецируется на август дважды (и Митя тогда не сможет узнать число), а на июль - единственный раз, и процецируется из 16 числа).
Ответ: 16 июля.
Я не знаю, как писать такое понятным образом и более формально, чтобы можно было не потеряться в фразе "Денис знает, что Митя знает, что Денис знает". Т.е. выбор - или формально, и невозможно проверить потому что непонятно. Или неформально, но неформальное не проверишь. Можно попробовать деревья вариантов рисовать, "при таком варианте он думает, что я думаю, что он думает".
Можно программу написать, но того как программу оттестируют на третьей однотипной задаче - в ней весьма вероятно будут опечатки.
Reply
Reply
Используем известную семантику возможных миров, в соответствии с которой добавим нашим предикатам пару переменных (m0, d0) означающих мир, в котором загаданы именно эти значения. Тогда M, D выражаются через равенство простым образом:
M(m)(m0, d0) := m == m0
D(d)(m0, d0) := d == d0
Поскольку нам придется формализовать понятие "значет, что", мы используем модальные операторы KM, KD, так чтобы формулы KMP, KDP значили "Митя знает P" и "Денис знает P" соответственно. Точнее, поскольку у нас несколько стадий знания, мы используем семейство К(i)x, где i - натуральное, x - либо M, либо D, что будет означать знание после ответа номер i.
Использование модели возможных миров означает, что мы сразу же выразим наши модальные операторы через кванторы и спокойно забудем про модальную логику. Введем
(KMP)(m0, d0) := A d. P(m0, d)
(KDP)(m0, d0) := A m. P(m, d0)
Для таких операторов верно "Митя знает месяц", "Денис знает день":
E m. KMM(m)
E d. KDD(d)
Что означает "x знает день рождения"? Что он знает M(m)&D(d) для некоторых m, d. Обозначим это утверждение буквой Z, учитывая зависимость знания от номера шага:
Z(i)x := (E m. KxM(m))&(E d. KxD(d))
(см. продолжение...)
Reply
Ф0 := (M(май)&D(15))|...|(M(август)&D(17))
Нашим героям эти дни сообщены, поэтому добавим им это знание на шаге (0):
К(0)xP := Kx(Ф0 => P)
На шаге (1) Митя заявляет, что знает, что Денис не знает ДР.
Ф1 := К(0)x ~Z(0)D
Это сообщается всем:
К(1)xP := К(0)x(Ф1 => P)
На шаге (2) Денис заявляет, что знает теперь ДР.
Ф2 := Z(1)D
Это сообщается всем:
К(2)xP := К(1)x(Ф2 => P)
На шаге (3) Митя заявляет, что тоже знает ДР
Ф3 := Z(2)M
Условие задачи формализуется утверждением Ф0&Ф1&Ф2&Ф3.
Reply
Reply
Leave a comment