Интересные интересности и задачи/головоломки

[Аватар]

Sibedir, эту задачу сам не решал (скорее всего и не решил бы), но решение когда-то видел - там много (очень много) рассуждений для тривиального частного случая с выводом формулы и обобщения её на 100 зк Подсказка желающим решить - проанализировать случай 3зк и номера от 1 до 3.

[Abstraction]

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

Задачу можно рассмотреть под чуть другим углом:
Тюремщик подслушивает разговоры заключённых и пытается подобрать номера так, чтобы они проиграли. Каждый ответ - функция от значений на остальных шляпах. Имеем N неравенств вида Fk(a1, a2, ..., a(k-1), a(k+1), ..., an)-ak != 0 (1 <= ai <= N).
Требуется сделать так, чтобы эта система была неразрешима. И теперь мы понимаем, что это элементарно: достаточно взять Fk=((-a1-a2-...-a(k-1)-a(k+1)-...-an+k) mod N) + 1. Действительно, если (a1+a2+...+an) mod N + 1=s, то Fs=0.

[Аватар]

И теперь мы понимаем, что это элементарно

Вот это элементарно очень даже ни чего, понравилось

[Sibedir]

Да, как-то так.
Ну я не всё понял про ak !, но тоже понравилось.

[Abstraction]

Sibedir, это !=, символ "не равно" из C. Аналог <> в Pascal.

[Poma][a]

Sibedir, респект за задачу.. Я так ничего и не смог придумать..
А можно вопрос : что такое Fk ?

[Naive]

Шляпы же не меняются? Один зэк называет первое увиденное число, все остальные его повторяют... брутфорс...

[Poma][a]

не вслух, а только мне на ушко (никто больше не услышит)

(пришлось немножко пофлудить в скобочках, чтобы пройти по длине)

[Abstraction]

Сообщение от Poma][a

Sibedir, респект за задачу.. Я так ничего и не смог придумать..
А можно вопрос : что такое Fk ?

Функция выбора k-го заключённого. Её значение - называемое им число.

Если перевести обратно в термины задачи, то заключённые считаются по порядку, от 0 до 99, и каждый запоминает свой номер. После этого, когда им надевают шляпы (пусть числа на шляпах тоже от 0 до 99), каждый складывает числа на шляпах всех прочих, берёт минус получившуюся сумму, прибавляет свой номер и берёт результат по модулю 100.

Пусть сумма всех чисел на шляпах равна s. Тогда заключённый номер (s mod 100) назовёт своё число x правильно: при подсчёте чужих шляп он получит сумму s-x, с минусом это будет x-s, после прибавления своего номера и взятия результата по модулю 100 останется x, ура.

Остаётся только внести поправки на то, что номера не от 0 до 99, а от 1 до 100.

И, разумеется, приходится надеяться, что все 100 заключённых в состоянии правильно сложить в уме 99 двузначных чисел...

Шляпы же не меняются? Один зэк называет первое увиденное число, все остальные его повторяют... брутфорс...

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

[Naive]

Сообщение от Poma][a

(пришлось немножко пофлудить в скобочках, чтобы пройти по длине)

пардон муа... тогда может по порядку?)