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

[fregimus]

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

Comments

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

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

Использование модели возможных миров означает, что мы сразу же выразим наши модальные операторы через кванторы и спокойно забудем про модальную логику. Введем

(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))

(см. продолжение...)