100 человек оставили свои шляпы в прихожей, которые были уложены по одной в пронумерованные 100 коробок случайным образом. В конце новогоднего вечера люди стали выходить по одному, имея (каждый) 50 попыток для нахождения своей шляпы. Нашедший шляпу, получает конфетку (шляпа остаётся в коробке) и в любом случае покидает вечер. Как людям сговориться, чтоб собрать в среднем по-больше конфет?

Шуточный вариант: каждый выбирает не именно свою шляпу, а любую подошедшую по размеру ! :)

Если у людей, уже прошедших испытание, есть возможность оставить какое-либо сообщение следующему, то задача становится очень лёгкой. Если нет - невыполнимой. Как я понял коробки все одинаковые и без разницы найдена ли шляпа - точно такими же предстают глазами второму человеку. Так как тогда первый может помочь в выборе второму?

Определённая информация может косвенно передаваться. Возьмём упрощённый вариант: 4 шляпы, 2 попытки, 4 человека. Они договорились проверять по схеме: 12, 23, 34, 41. Т.е. первый человек проверяет первую и вторую коробки, второй человек проверяет вторую и третю коробки итд. Пусть первый человек нашёл свою шляпу во 2-ой коробке, тогда второй человек, открыв 2-ую коробку и, найдя там 1-ую шляпу, понимает, что первый человек нашёл свою шляпу и, теперь он (второй) может попытаться изменить своё решение и не открывать 3-ю коробку. Также необходимо заметить, что не все расположения шляп в коробках одинаковы для людей играющих по схеме. Иными словами, люди в процессе получения информации могут изменять свой маршрут, чтобы встать на рельсы в среднем более выгодного пути.

Нахождение 1ой шляпы во второй коробке не несёт второму абсолютно никакой информации, кроме той, что первый человек стал счастливым обладателем конфетки. Даже примитивный 1 бит информации передать этим нельзя, ведь коробку нельзя оставить закрытой/приоткрытой и т.д.

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

Ясно.Шляпы распределены равномерно и проверять надо равномерно.
1. 1-50
2. 2-51
.
51. 51-100
52. 52-1
.
100. 100-49.

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

Уточняющий вопрос к условиям задачи: очередь людей видит или знает о счастливых обладателях конфет? Если да, то можно попытаться разработать удобную двоичную, скользящую или иную схему извлечения информации.

Например, исходя из своего порядкового номера участник имеет четкую инструкцию по порядку извлечения шляп, т.е. набор номеров коробок. Очередь знает также результат такого испытания, а значит точно знает набор номеров коробок, среди которых находится коробка текущего участника (есть конфета - см. 50 номеров из набора, нет конфеты - см. 50 остальных номеров). Отсюда вопрос: можно ли превысить результат в 50 конфет?

P.S. Трюк: использовать время поиска шляпы как способ передачи информации.
Вот только стоит овчинка выделки. ))

Это сообщение отредактировал zenker - 2/02/2009, 16:34