Привожу решение задачи Олега Полубасова о числе домов в деревне туземца.
Ближе всех к решению подшел
luitzen
Может быть, нужно задать такой вопрос, чтобы у лжеца был единственный способ обеспечить ложность ответа на него: назвать число домов. И, соответственно, для туземца-правдолюба называние числа домов было бы единственным способом обеспечить истинность ответа.
Решение задачи основано на свойствах дизъюнкции. Как известно, она ложна лишь в том случае, когда ложны оба операнда.
Для наглядности отдельно укажу структуру вопроса, а затем уже сформулирую возможные его составляющие.
Вопрос, решающий задачу, может иметь вид: верно ли утверждение

?
Высказывание

должно быть таким, чтобы туземец не знал, истинно ли оно, и не имел возможности проверить его истинность.
Автор задачи, Олег Полубасов, предлагал в качестве

использовать какую-нибудь не доказанную, но и не опровергную математическую гипотезу. Именно поэтому он включил в условие информацию об обширных познаниях туземца.
Мне представляется, что можно взять в качестве

что-нибудь попроще. Например, "К началу 22-го столетия население Франции превысит 100 000 000 человек". Понятно, что на сегодняшний день никто не может гарантированно ответить истинно ли приведеное утверждение. Трудно даже сказать будет ли к этому времени существовть сама Франция (неважно, в рамках Евросоюза или еще как-то). А ждать долго. Велика вероятность не дождаться
Утверждение

может выглядеть примерно так: "Сейчас ты разборчиво напишешь на этом листке единственное число (в десятичной системе счисления), совпадающее с числом домов в твоей деревне, и при этом никоим образом не будешь препятствовать тому, чтобы я прочел и нонял написанное."
Если дополнительных условий, которыми я, на всякий случай, снабдил

недостаточно, добавьте еще.
Итак вопрос прозвучал. Что делать бедному туземцу? Если он не напишет нужное число, истинность дизъюнкции будет зависеть от истинности

, а определить ее не представляется возможным. Зато если он напишет требуемое число, вся дизъюнкция станет истинной. Поэтому туземец напишет нужное число. И только после этого честный облегченно произнесет "Да", а лжец радостно скажет "Нет".
Понятно, что приведенный способ позволяет выведать у туземца любые доступные ему сведения (например, кто Маша, а кто Даша). Единственным недостатком метода является его низкая эффективность при общении не с задачными туземцами, а с реальными людьми
