День рождения Алины

[fregimus]

В этих ваших интернетах сегодня ходит задачка, заданная сингапурским школьникам на каком-то экзамене. Она вызвала ожесточенные споры, так что сингапурскому ОНО - или как у них там ОНО называется - даже пришлось давать целое длинное разъяснение того решения, которое они посчитали правильным. Так вот, решение их неправильное. [см. доб

Comments

[_winnie]

Попробую.

Условие задачи таблицей:

-------------------------------
май: 15 16 19
июнь: 17 18
июль: 14 16
август: 14 15 17
-------------------------------

Фраза "я знаю что, что он знает", это значит что у кого-то множество вариантов проецируется на чужую ось без наложений, по одному варианту в каждую точку проекции (инъективно).

Чтобы Денис знал о дне рождения сразу - для этого день рождения должен приходится на число с единственным месяцем, т.е. 18 или 19.

Из фразы: 'Митя: Но я знаю, что и Денис не знает!' я (и Денис) делаю ввывод, что Алина шепнула Мите про июль или август, в противном случае Митя не был бы уверен что Алина не шепнула Денису про 18-е или 19-е число.

-----------------------
июль: 14 16
август: 14 15 17
-----------------------

Из фразы: "Денис: а я теперь знаю, когда твой день рождения!" следует, что д.р. 15, 16, или 17 (14 не подходит, так как для него подходит два оставшихся месяца, и тогда бы Денис не знал месяц).

июль: 16

[zeit_raffer]

"Денис знает, что Митя знает, что Денис знает Q" прекрасно записывается в модальной логике: KDKMKDQ. Но я не знаю, как там записываются ДО и ПОСЛЕ в утверждении, что Денис не знал день ДО первого ответа Мити, и стал знать ПОСЛЕ. Возможно, импликацией: из того, что Денис знает, что Митя знает, что Денис не знает, следует, что Денис знает. Надо звать проф.логиков.

Попробуем сами, без логиков

[zeit_raffer]

Будем пользоваться языком логики предикатов (and - &, or - |, not - ~). Кванторы (которые я буду писать не перевернутыми: A,E) по переменным m будут пробегать месяцы, по переменным d - дни. Введем базовые предикаты М(m), D(d), так чтобы M(август)&D(17) означало, что загадано 17 августа.

Используем известную семантику возможных миров, в соответствии с которой добавим нашим предикатам пару переменных (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

Попробуем сами, без логиков - 2

[zeit_raffer]

Теперь запишем условия задачи. Список возможных дней зададим формулой (я не пишу все дни):

Ф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.

[zeit_raffer]

Теперь можно подставить все определения вида ":=", получив формулы, использующие только кванторы по конечной области и равенства переменных. И засунуть в свой любимый солвер.