Вызга монос

Есть несколько классических задачек на рекурсивную логику.

Загадано число N (N >= 2). Одному человеку сообщается N + 1, другому N - 1. Между ними происходит следующий диалог:

- Я не знаю, что это за число.
- Я не знаю, что это за число.
...
- Я не знаю, что это за число.
- Я знаю, что это за число.

В зависимости от вариации задачи, люди (не)?знают, что им сообщили (N + 1 или N - 1).
Длина диалога внезапно равна N (+-1). Надо моделировать на малых числах и курить. А то, если N велико, трудно понять, что же нам дает не знание собеседника.

Следующая задача примерно такая же. Загадано два числа, одному сообщается сумма чисел, другому - произведение. Такой же диалог. Тут надо еще побольше шевелить мозгом, удары об стену идут вне зачета.

Эта задача была на полуфинале где-то в 2003/2004. На тренировке мы до нее не дошли, другой халявы было предостаточно.

А есть еще класс задач с шапочками, где какой-либо злодей надел на (пусть) гномов шапочки двух цветов, причем известно что есть оба цвета. Все гномы видят цвет всех, кроме себя. Им нужно к 22:37 определить, какой же у них цвет шапочки. Иначе смерть, ипотека, жена_трое_детей.

"Помоги веселым гномикам сделать это..." Там обычно, одетые, например, в красные шапки, должны сделать шаг вперед. Пусть у нас будут красные и черные.

Тут если два гнома, то тривиально. Три - одноходовка. На четырех уже надо подумать. Но здесь и далее меня выносит: если первые две задачки были дискретными, то здесь же есть какой-то скрытый элемент динамики. Даже для трех: пусть гном (я) видит у соседей два других цвета. Тогда из того, что одетый в черное стоит на месте, следует я тоже в черном. Если бы другой гном в черном видел бы на мне красный, и на другом красный, то он бы догадался, что на нем черный (ибо по условию обязательно есть оба цвета). И вот оба черных дошли до правильной мысли и должны сделать шаг.

Здесь заложена какая-то скрытая дискретность, раз он не пошел на предыдущей секунде (или другая отсечка), значит у него не хватает информации. Это, кстати, довольно круто, что недостаток информации дает какую новую для меня. Но как человеку немного более близкому к информатике, тут сильно глючит: успеют ли они за единицу времени провести логический вывод для следующего шага? Там как-то страшно (в смысле сильно не понятно как) растет дерево разбора... Непонятно, как синхронизироваться. Чистая математика и логика как-то вообще не рассматривают вопросы об эффективности и производительности, что печалит.

ЗЫ. Бывают какие-то моменты времени, что мне кажется, что я эти задачки понимаю. Как любят говорить математики, множество меры 0 (про время). В остальные моменты времени я думаю так: "блин, тут же все просто должно быть, я ж это понимал." Сидишь и гошешь челову, при условии что весь вызг монесен.