N гномиков стоят в колонне. На голове у каждого гномика шляпа черного или белого цвета. Гномик не видит цвета своей шляпы, но видит цвет шляпы всех стоящих перед ним. Каждый гномик, начиная с конца колонны называет цвет: черный или белый. Если он угадал цвет своей шляпы, он остается в живых, в противном случае гибнет.

Внимание : Альтруистов среди гномиков нет

Какое количество гномиков может спастись?


P.S. имхо это еще круче чем самолет, если я правильно понимаю...


Изменено 2-12-2004 автор Maverik

сообщение The Lord Aleksandr
Несколько вопросов по новым условиям задачи:

1. Зачем гномикам договариваться о стратегии ответов - они изначально не знают цветов шляп

2. Что дает перемена места для гномика - шляпа привязана к месту или голове гномика?

Тогда я чего-то не пойму: почему впереди стоящий гномик не может спросить сзади стоящего про цвет своей шляпы? Единственное, последнему спросить не у кого, следовательно выживет N-1, с вероятностью 50% (или если он угадает, то все N).

А-а-а,

начиная с конца колонны

Хитро: гномик альтруист и говорит слудующему не тот цвет, все слышат... как гномика убивают и перестают верить в подсказки, что тут начнется...
Тогда (по теории вероятности) (N-(a-1))/2+(a-1), где a-число гномиков до альтруиста, [-1] первый говорящий.

А чудно получилось вчера про WinAmp написал и уже больше 15 часов слушаю новую музыку.

сообщение The Lord Aleksandr
Хитро: гномик альтруист и говорит слудующему не тот цвет, все слышат... как гномика убивают и перестают

Тогда (по теории вероятности) (N-(a-1))/2+(a-1)

сообщение Maverik
N гномиков стоят в колонне. На голове у каждого гномика шляпа черного или белого цвета. Гномик не видит цвета своей шляпы, но видит цвет шляпы всех стоящих перед ним. Каждый гномик, начиная с конца колонны называет цвет: черный или белый. Если он угадал цвет своей шляпы, он остается в живых, в противном случае гибнет.

гномики могут договориться о наилучшей стратегии ответов, но только перед началом "опроса"

гномики не могут меняться местами

глухих и слабослышаших гномиков среди них нет

Вопрос : какое максимальное количество гномиков гарантированно может уцелеть при их наилучшей стратегии ?

PS : и еще - так все-таки чем будет отличаться оптимальная стратегия при условии когда альтруистов среди них нет - т.е. ни один из гномиков не готов пожертвовать собой ради других от оптимальной стратегии , когда хоть один альтруист есть ?

Maverik, а где же ответ на вопрос задачи, выраженный в N?
Приведите решение, мне оно не кажется очевидным.

сообщение butch
Maverik, а где же ответ на вопрос задачи, выраженный в N?
Приведите решение, мне оно не кажется очевидным.

Значит, отсутствие альтруистов отвергает решение типа:
Последний гном рассказывает всем, у кого какая шляпа, а сам выживает с вероятностью 50/50.

сообщение butch
Значит, отсутствие альтруистов отвергает решение типа:
Последний гном рассказывает всем, у кого какая шляпа, а сам выживает с вероятностью 50/50.

Договорились, выбрали стратегию, встали в ряд, открыли глаза, увидели цвета шляп у впереди стоящих. И какова же стратегия, позволившая N-1 (т.е. всем кроме первого ответившего) гарантированно узнать цвет своей шляпы?
Или ответ таков: ТЕОРЕТИЧЕСКИ существует такая стратегия......... Вот пример опровергающий это. Чтобы второй гном гарантированно назвал цвет своей шляпы, этот цвет должен подсказать первый, рискуя 50/50. Но тогда уже третий опять рискует. Ну если только слово белый произнести по буквам, каждая буква в своем музыкальном регистре, перерывы между буквами тоже информативны....... Ну тогда задача не интересна с точки зрения математики.

сообщение Олег Нечаев
Договорились, выбрали стратегию, встали в ряд, открыли глаза, увидели цвета шляп у впереди стоящих. И какова же стратегия, позволившая N-1 (т.е. всем кроме первого ответившего) гарантированно узнать цвет своей шляпы?
Или ответ таков: ТЕОРЕТИЧЕСКИ существует такая стратегия......... Вот пример опровергающий это. Чтобы второй гном гарантированно назвал цвет своей шляпы, этот цвет должен подсказать первый, рискуя 50/50. Но тогда уже третий опять рискует. Ну если только слово белый произнести по буквам, каждая буква в своем музыкальном регистре, перерывы между буквами тоже информативны....... Ну тогда задача не интересна с точки зрения математики.

Maverik,
а чем Вам не нравится мое решение?
Решение, приведенное Вами, отличается лишь своей красотой в силу лаконичности. Возникает вопрос: с какой стати первый гном будет договариваться со всеми, если ему в этой жизни выпало выжить с вероятностью 50% ? Прошу заметить, что он не альтруист! Почему бы ему всех не "кинуть". Не хочу ни кого обидеть, но все это похоже на демагогию...

К сожалению, только сейчас залез в эту ветку и прочёл последние сообщения о задаче. Я сообщил в привате Юрию решение почти один в один, как и приведенное Butch ещё три недели назад, просто мне оно показалось столь очевидным, что не хотелось раньше времени его писать в форум. До опроса они договариваются говорить правду и сообщают впереди стоящему цвет его шляпы. Они знают, что такая стратегия позволяет выжить N-1 гномикам наверняка. Лучшего добиться невозможно, поэтому это и есть решение этой задачи, друге дело что такая стратегия может быть неединственной, например, ещё и такой, как привёл Юрий, но это не значит, что я "угадал" ответ, а решение неверное. Теперь о последнем гномике. Он наугад может назвать цвет своей шляпы и вероятность выжить тогда будет 1/2. Однако, если, видя перед собой шляпы впереди стоящих, он уловит некую закономерность в распределении цветов, то может РИСКНУТЬ и называть цвет своей шляпы с учётом этого. При этом если цвета распределены не случайным образом и N достаточно велико, то вероятность выжить для него будет больше или равна 1/2. Как известно, вероятность и информация связаны между собой. Известно также, что если человеку предложить написать наугад длинный ряд нулей и единиц, то с вероятностью больше 1/2 можно угадывать следующую цифру, видя достаточно много предыдущих, т.е. у каждого свой "почерк". С этой точки зрения моё решение как минимум не хуже приведенного Юрием, где последнего ОБЯЗЫВАЮТ называть цвет в зависимости от чётности, т.е. наугад.

сообщение butch
Maverik,
а чем Вам не нравится мое решение?
Решение, приведенное Вами, отличается лишь своей