Re: Есть контакт


Автор сообщения: Roger
Дата и время сообщения: 22 October 2004 at 19:31:01:

В ответ на сообщение: Re: Есть контакт

Итак, стратегия для N цветов следующая. Все цвета нумеруются от 0 до N-1. Затем каждый считает сумму цветов колпаков перед ним и вычисляет остаток от деления на N. Первый называет сумму вслух и его казнят с вероятностью 1/N. Следующий вычитает из его суммы свою (естественно, если результат отрицательный, добавляет N). Это и есть его цвет, который он произносит вслух. Все остальные вычитают из общей суммы уже названные цвета, и, когда дело доходит до них (или до этого), тоже вычитают из общей суммы свою.

Для N=2 формулировка, естественно, может быть попроще, на уровне чёт-нечет, но смысл такой же.

Интересно также рассмотреть алгоритм "коррекции ошибок". Допустим, в цепи есть слепой и он не угадал:( Цвет его колпака вслух не оглашают. Для случая N=2 всё просто, не чёрный - так белый. Для N=3 ещё имеет смысл угадать правильный цвет. А вот для N=4 и далее выгоднее (для популяции мудрецов, а не для индивидуума, естественно) начать с нуля, т.е. следующий за казнённым заново называет свою контрольную сумму.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице