Гномы и сундуки

Инна · Сообщение **Инна** » 12 ноя 2007, 15:40

Belshina писал(а): Когда гномов помещают в 3 комнату то этим самым подразумевается что все они успешно открыли сундуки, т.е. нашли свое имя? или в не зависимости от исхода открытия сундуков каждого гнома сажают в 3 комнату?

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

Antananarivu

Да..это задача года (по крайней мере для меня) в области элементарной математики (ну почти элементарной!)

У нас никто из отдела решить снаскоку не смог

Инне спасибо!

Инна · Сообщение **Инна** » 12 ноя 2007, 15:43

http://velisantik.ru/ru/content/view/161/202/
Картинка в тему

Dendr · Сообщение **Dendr** » 12 ноя 2007, 15:52

Виталий Антипов писал(а):И еще... если тот кто хочет убить гномов математик, он ведь может подстраховаться и положить таблички так, что гномы (выбрав эту стратегию) точно погибнут! Поэтому в условии стоит указать, что таблички положили случайным образом!

Даже не зная авторского ответа, готов поспорить. Я уже это обсуждал тут. Гномы могут входить в любом порядке! И этот порядок заранее раскладчику табличек неизвестен.

Antananarivu

Dendr писал(а):
Виталий Антипов писал(а):И еще... если тот кто хочет убить гномов математик, он ведь может подстраховаться и положить таблички так, что гномы (выбрав эту стратегию) точно погибнут! Поэтому в условии стоит указать, что таблички положили случайным образом!
Даже не зная авторского ответа, готов поспорить. Я уже это обсуждал тут. Гномы могут входить в любом порядке! И этот порядок заранее раскладчику табличек неизвестен.

А там порядок и не важен

Инна · Сообщение **Инна** » 12 ноя 2007, 15:59

Виталий Антипов писал(а):
Dendr писал(а):
Виталий Антипов писал(а):И еще... если тот кто хочет убить гномов математик, он ведь может подстраховаться и положить таблички так, что гномы (выбрав эту стратегию) точно погибнут! Поэтому в условии стоит указать, что таблички положили случайным образом!
Даже не зная авторского ответа, готов поспорить. Я уже это обсуждал тут. Гномы могут входить в любом порядке! И этот порядок заранее раскладчику табличек неизвестен.
А там порядок и не важен

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

Antananarivu

Да, согласен... ох уж эти стереотипы мышления. Инна права!
P.S. Вообще удивительно как вероятность из, например, 1/2^1000 незаметно превращается в 30 с хвостиком процента...

Геля · Сообщение **Геля** » 12 ноя 2007, 16:03

Надо было упоминание о том, что эксперимент прекращается в случае первой ошибки вынести в условие, это существенная часть условия все-таки. И вид ответа тоже наводит на размышления, ln2 - похоже сумма ряда.
И зачем сообщать всем, что нашел решение в инете, еще и с точным указанием параметров поиска, прям настроение пропало решать(((

Antananarivu

Геля писал(а):Надо было упоминание о том, что эксперимент прекращается в случае первой ошибки вынести в условие, это существенная часть условия все-таки. И вид ответа тоже наводит на размышления, ln2 - похоже сумма ряда.
И зачем сообщать всем, что нашел решение в инете, еще и с точным указанием параметров поиска, прям настроение пропало решать(((

Да не важно это! Прекращается, не прекращается!
Если кому-то интересно самому решить он и не полезет смотреть ответ! И потом в интернете можно все найти, я ж не тайное место какое выдал.

Плавающая Точка

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

Первый гном пришел - окрывает сундуки подряд, допустим, справа налево. Нашел свое имя - ура! открывает дальше в том же порядке.
Второй гном опять открывает справа налево. Тут два варианта - либо его имя встретится раньше имени первого гнома, тогда ему все равно, что открывать дальше. Либо он встретить имя первого гнома. Тогда он может продолжить открывать сундуки с другого конца - слева направо. Это, чтоб третий гном в случае успеха второго гнома (а если будет неуспех, так и пофик уже), лишний раз не нарывался на чужое имя.
Третий гном опять открывает ящики справа налево. Уже три варианта: ему попадется имя первого гнома - тогда надо продолжать в том же направлении, так как с другого конца лежит имя второго гнома и там вероятность успеха уже заведомо на один сундук меньше.
Или ему попадается имя второго гнома, значит, хватит тут рыть, там дальше опять минус один сундук с именем первого гнома. Роем с другой стороны. Ну, а если имя третьего попадается первым, дальше уже все равно, что открывать.

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

Antananarivu

Если бы я был гномом я бы видимо погиб ))

AndrNiko · Сообщение **AndrNiko** » 12 ноя 2007, 17:44

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

Моя ошибка была в неявном предположении, что перед входом в комнату каждый гном уже знает, какие сундуки будет открывать. Нет - ни один гном, включая первого, не знает заранее весь список! Он знает только первый сундук, который откроет. Дальнейшее зависит от того, что он там увидит.

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

Надеюсь, что эта подсказка не испортит удовольствие от задачи тем, кто в состоянии её решить. К сожалению, таких тут немного.

Dendr · Сообщение **Dendr** » 12 ноя 2007, 18:00

Похоже, многие не выдержывают...

Хотя б в личку намекните - ход мыслей-то верный у меня?
здесь

Atson · Сообщение **Atson** » 12 ноя 2007, 18:12

Подсказки таки прозвучали.

В связи с вышесказанным можно проверить такую стратегию. Пронумеруем гномов, скажем по алфавитному принципу. Гном номер i открывает первым ящик i. Находит там имя гнома j. Открывает дальше ящик i + j (если i + j больше n, то i + j - n). Там имя номера x. Открываем i + x и т.д. Что-то не знаю, как посчитать вероятность попроще.

Инна · Сообщение **Инна** » 12 ноя 2007, 18:24

Dendr писал(а):Похоже, многие не выдержывают...

Хотя б в личку намекните - ход мыслей-то верный у меня?
здесь

Личка не там, но основная мысль верна: номера сундуков могут зависеть от того, что было увидено в предыдущих.