Сто мудрецов

Что мы все о программировании да о программировании. Давайте в этот раз просто подумаем и поможем ста мудрецам спастить от неминуемой гибели от рук палача.

Итак, все сто мудрецов выстроены в одну колонну (каждый видит тех и только тех, кто стоит перед ним), и на головы им будут надеты шляпы одного из k > 0 цветов, выбранных независимо и случайным образом. Каждый из мудрецов в колонне, начиная с последнего, должен будет либо назвать цвет своей шляпы, либо сказать «пас».

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

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

Для случая k = 1 всё достаточно просто: если известно, что шляпы бывают только одного цвета, то именно его надо называть. С вероятностью 100% ответ будет правильным, поэтому мудрецы пройдут тест.

Чем хороша эта задача? А тем, что кажется, что она не имеет разумного решения. Судите сами: первый отвечающий, который видит перед собой 99 шляп, ничего не знает о цвете своей шляпы. Поэтому он, не имея права назвать какой-то цвет (если назовёт, то с вероятностью 1-1/k все проиграют), вынужден сказать «пас». Но у второго совершенно такая же ситуация: он видит перед собой 98 шляп, он заранее знал, что первый скажет «пас», поэтому он тоже вынужден говорить «пас». И так далее. Возникает иллюзия, что выиграть невозможно. И тем интереснее догадаться, как же действовать мудрецам.

UPD: спойлеры в каментах!