Гномики...

[Larkin]

Может уже было здесь, не знаю, мне понравилась задачка:

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

[ArtemiZagagulin]

...либо синего.

Знаю я таких гномиков, без буквы"н". Если можно сказать только цвет, пусть говорят "голубой", так как это будет правдой во всех случаях и выживут все!

А еще можно спросить окружающих про цвет своей шляпы. Кстати ели это шляпа, то должны быть поля, которые можно видеть самому. А если полей нет, то это уже не шляпа, а ямака какая-то.

Можно еще подойти очень близко к другим гномикам и посмотреть на свое отражение в их глазах.

[Larkin]

...либо синего.

Знаю я таких гномиков, без буквы"н". Если можно сказать только цвет, пусть говорят "голубой", так как это будет правдой во всех случаях и выживут все!

А еще можно спросить окружающих про цвет своей шляпы. Кстати ели это шляпа, то должны быть поля, которые можно видеть самому. А если полей нет, то это уже не шляпа, а ямака какая-то.

Можно еще подойти очень близко к другим гномикам и посмотреть на свое отражение в их глазах.

Задача решается строго математически, а это - не решение, это лирика...
PS Гномики между собой не общаются после перемены шляп.

[Ion Tichy]

Если каждый гномик (1) не дальтоник, (2) умеет считать и (3) будет знать кол-во красных, кол-во зеленых и кол-во синих шляп, то...

[Larkin]

Если каждый гномик (1) не дальтоник, (2) умеет считать и (3) будет знать кол-во красных, кол-во зеленых и кол-во синих шляп, то...

Гномики (1) не дальтоник, (2) умеют считать, но (3) не знают начальное кол-во красных, кол-во зеленых и кол-во синих шляп. Скажем сначала у вас 100 гномиков, потом им перемешивают шляпы и отбирают 80 для геноцида. Эти 80 видят друг друга, но не видят 20. Общаться между собой не могут, кучковаться по цвету они не могут, единственная информация, которую они могут сообщить - цвет, когда их спрашивает злой волшебник...

[IvanGrozniy]

Стартегия должна быть такая: выбрать предводителя среди гномиков, который будет руководить операцией захвата злого волшебника. При удачном раскладе и слаженности работы всего коллектива враг будет повержен без потерь.

[Ion Tichy]

...но (3) не знают начальное кол-во красных, кол-во зеленых и кол-во синих шляп...

Пардон, а как же

...До того, как шляпы перемешаны, у гномиков есть шанс выработать стратегию по минимизации смертности гномиков...

???
Я, собссно, и имел ввиду возможность проведения инвентаризации до прихода ЗВ. Стратегия, значица, такая вот.

[Larkin]

Стартегия должна быть такая: выбрать предводителя среди гномиков, который будет руководить операцией захвата злого волшебника. При удачном раскладе и слаженности работы всего коллектива враг будет повержен без потерь.

Похоже тут сказочники сидят в головоломках, а не математики...
Нужно было видимо сухо и математично сформулировать задачу, а то народ развлекается, а думать не хочет!

[Larkin]

...но (3) не знают начальное кол-во красных, кол-во зеленых и кол-во синих шляп...

Пардон, а как же

...До того, как шляпы перемешаны, у гномиков есть шанс выработать стратегию по минимизации смертности гномиков...

???
Я, собссно, и имел ввиду возможность проведения инвентаризации до прихода ЗВ. Стратегия, значица, такая вот.

Ну, порправила немножко, sorry, поскольку только над 80 издеваются, изначальное количество шляп не поможет...

[venco]

Сложение по модулю 3 поможет математически подкованным гномикам.
Первым придётся пожертвовать с вероятностью 2/3...

[Larkin]

Сложение по модулю 3 поможет математически подкованным гномикам.
Первым придётся пожертвовать с вероятностью 2/3...

Вот - математик пришел!

[Ljolja]

Вопрос: какая стратегия и каково минимальное число убиенных гномиков...

В подобных ?? нельзя полагаться исключительно на математические способности, человеческий фактор играет ключевую роль Если среди гномиков будет venco, то "пожертвуют" 2/3 гномика. А если IvanGrozniy - 2/3 от всего коллектива

[Ljolja]

venco, а Вы задачу решили или Вы знали решение (может быть подобной задачи). Если 1-е - сколько времени ушло на решение?

[venco]

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

[Ljolja]

venco, спасибо за ответ
И как по Вашему, задача стандартная, если знаешь правило?
[Что такое сложение по модулю, мне уже обьяснили]

[sladim]

Сложение по модулю 3 поможет математически подкованным гномикам.
Первым придётся пожертвовать с вероятностью 2/3...

а можно разъяснить? пожалуйста. по модулю - это вроде неравнозначно?

[Drom]

а "неравнозначно" - это как?

То, что писал venco, в развернутом виде выглядит примерно так:
- цвета кодируются числами 0, 1 и 2
- первый гномик-камикадзе называет цвет, соответсвующий сумме шляп остальных гномиков по модулю 3 (и с вероятностью 2/3 несовпадающий с его шляпой, что приводит к летальному исходу)
- остальные гномики, видя все остальные шляпы, подбирают цвет своей так, чтобы сумма давала нужный остаток по модулю 3.

Disclaimer: выражение "вычитание по модулю" не использовалось сознательно.

[sladim]

сорри за видимый оффтоп, я реально что-то забыл сильно. Я думал по модулю это что-то из булевой алгебры, а под "неравнозначный" я имел в виду что-то типа "исключающего или"?
кароче я запутался =)

[Drom]

кароче я запутался =)

Эт бывает. Если интересно, то можно сходить
сюда: http://www.answers.com/topic/modular-arithmetic (более подробно)
или сюда: http://mathworld.wolfram.com/ModularArithmetic.html (более академично)

[sladim]

спасибо =)