IPB
 

Здравствуйте, гость ( Вход | Регистрация )

Поддержать форум
7 страниц V   1 2 3 > »   
Ответить в данную темуНачать новую тему
> снова гномоед и 100 гномов, не про шапочки
svetlana
Отправлено: 20.11.2009, 17:02
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



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


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

я вас заведу по одному в комнату, где находится 100 ящиков, в каждом ящике имя одного из гномов. Каждому гному разрешается открыть любые 50 ящиков. После этого ящики закрываются и я завожу следующего гнома. Если каждый из гномов найдет свое имя, то я, так и быть, отпущу вас. А если хотя бы один не найдет - всех в суп. Ночь вам на размышление в этой комнате, завтра с утра развожу всех по индивидуальным камерам и начинаем игру.

Ящики различаются между собой, скажем, пронумерованы. Ясно, что если гномы будут открывать наугад, то вероятность спастись 1/2^100, что ничтожно мало. Задача придумать хорошую стратегию, которая обеспечит значимую вероятность спастись.


P. S. Моргоюзверям, которые знают решение задачи от меня или из других источников, просьба не портить другим удовольствие от решения задачки.
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 20.11.2009, 17:25
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3966
Регистрация: 09.04.2007
Пользователь №: 45663



Гномы могут как-то повлиять на исходное расположение имен в ящиках?
Имена гномов фиксированы?
Гномам разрешается переговариваться между заходами?
 
Перейти в начало страницы
svetlana
Отправлено: 20.11.2009, 17:47
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



Цитата(Eyeless Watcher @ 20.11.2009, 18:25) *
Гномы могут как-то повлиять на исходное расположение имен в ящиках?
Имена гномов фиксированы?
Гномам разрешается переговариваться между заходами?

нет
да, фиксированы и все различны
не разрешается, конечно, а то первый бы всем все рассказал smile.gif
 
Перейти в начало страницы
Либерал
Отправлено: 20.11.2009, 17:53
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9082
Регистрация: 27.07.2007
Из: Ранчо
Пользователь №: 52146



А гном должен сказать свое имя перед тем, как будет открывать ящики?


--------------------
Отчалил из Рашки в лучшие края.
 
Перейти в начало страницы
svetlana
Отправлено: 20.11.2009, 17:55
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



Цитата(Либерал @ 20.11.2009, 18:53) *
А гном должен сказать свое имя перед тем, как будет открывать ящики?

Гномоед выучил имена гномов заранее.
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 20.11.2009, 18:04
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3966
Регистрация: 09.04.2007
Пользователь №: 45663



Порядок следования гномов известен?

Кстати, итоговая вероятность не может быть больше 50% - первому-то точно отталкиваться не о чего.

Охохо. Нашел решение в гугле. Красиво smile.gif
 
Перейти в начало страницы
svetlana
Отправлено: 20.11.2009, 18:39
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



Цитата(Eyeless Watcher @ 20.11.2009, 19:04) *
Порядок следования гномов известен?

Кстати, итоговая вероятность не может быть больше 50% - первому-то точно отталкиваться не о чего.

Охохо. Нашел решение в гугле. Красиво smile.gif

Порядок неизвестен.

Верно. Но она может быть гораздо больше 1/2^100.

А сколько удовольствия потеряли, оттого что полезли в гугл, вместо того чтобы самостоятельно порешать smile.gif
 
Перейти в начало страницы
жора
Отправлено: 20.11.2009, 18:39
+Цитировать сообщение


Veteran
*****

Группа: Участник
Сообщений: 1126
Регистрация: 28.10.2005
Пользователь №: 15877



Цитата
я вас заведу по одному в комнату, где находится 100 ящиков, в каждом ящике имя одного из гномов. Каждому гному разрешается открыть любые 50 ящиков. После этого ящики закрываются и я завожу следующего гнома. Если каждый из гномов найдет свое имя, то я, так и быть, отпущу вас. А если хотя бы один не найдет - всех в суп. Ночь вам на размышление в этой комнате, завтра с утра развожу всех по индивидуальным камерам и начинаем игру.


В условии не говорится, что ящики будут перетасованы перед испытанием. Поэтому они подготавливаясь в ЭТОЙ комнате тупо выучивают где лежит их имя.
Задача решена.

Кроме того, из условия однозначно следует что гномам всё равно пипец.
Цитата
Поймал гномоед 100 гномов, но решил не сразу суп из них сварить, а сначала поглумиться.


Т.е. даже в случае решения задачи гномами - их съедят.


--------------------
Там всем любовно и прельстиво.
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 20.11.2009, 18:42
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3966
Регистрация: 09.04.2007
Пользователь №: 45663



Цитата(svetlana @ 20.11.2009, 18:39) *
А сколько удовольствия потеряли, оттого что полезли в гугл, вместо того чтобы самостоятельно порешать smile.gif

Я бы до такого, честно признаюсь, не додумался бы. Хорошо, даже если додуматься до процедуры - обосновать мне образования не хватит. Дискретку мы учили немного в другом направлении... Хотя перестановки даже проходили... но на алгебре на первом курсе smile.gif
 
Перейти в начало страницы
p4w3l
Отправлено: 20.11.2009, 20:41
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 21.03.2009
Из: где то тут :)
Пользователь №: 102476



А они могут на ящиках царапать?) Если да, то задача весьма проста.
 
Перейти в начало страницы
svetlana
Отправлено: 20.11.2009, 20:51
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



2 p4w3l, жора: задачка честная, никаких царапаний, словесных ловушек и пр, решение чисто математическое.
 
Перейти в начало страницы
Eyeless Watcher
Отправлено: 20.11.2009, 20:57
+Цитировать сообщение


Guru
******

Группа: Опытный
Сообщений: 3966
Регистрация: 09.04.2007
Пользователь №: 45663



Я вот только не увидел в этом решении обоснования его оптимальности smile.gif
 
Перейти в начало страницы
p4w3l
Отправлено: 21.11.2009, 19:11
+Цитировать сообщение


Activist
***

Группа: Участник
Сообщений: 257
Регистрация: 21.03.2009
Из: где то тут :)
Пользователь №: 102476



Цитата(svetlana @ 20.11.2009, 20:51) *
2 p4w3l, жора: задачка честная, никаких царапаний, словесных ловушек и пр, решение чисто математическое.

переставлять ящики можно? Достаточно ли большое помещение, чтобы их в ряд ставить?
 
Перейти в начало страницы
Analyt
Отправлено: 21.11.2009, 19:23
+Цитировать сообщение


Ведущий
**********

Группа: Модератор
Сообщений: 6025
Регистрация: 25.10.2003
Пользователь №: 864



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

И значимая вероятность -- это сколько?


--------------------
In der Beschrankung zeigt sich erst der Meister
 
Перейти в начало страницы
svetlana
Отправлено: 21.11.2009, 19:36
+Цитировать сообщение


Patriarch
**********

Группа: Участник
Сообщений: 9957
Регистрация: 13.02.2005
Пользователь №: 7272



Цитата(Eyeless Watcher @ 20.11.2009, 21:57) *
Я вот только не увидел в этом решении обоснования его оптимальности smile.gif

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

Цитата(p4w3l @ 21.11.2009, 20:11) *
переставлять ящики можно? Достаточно ли большое помещение, чтобы их в ряд ставить?

Давайте считать, что ящики расставлены в ряд и прибиты к полу.

Цитата(Analyt @ 21.11.2009, 20:23) *
Если какой-нибудь гном не нашёл имени, их сразу в суп ведут или продолжают глумиться?
Другими словами, гномы как-то могут понять нашёл вышедший своё имя или нет?
И значимая вероятность -- это сколько?

Гномов сразу всех в суп.

Значимая - это не очень хорошая формулировка, но я не знаю, как сформулировать лучше, чтобы не подсказать или не дать ответ, подсказывать вроде еще рано. Реальная вероятность спастись, а не 2^{-100}.
 
Перейти в начало страницы

7 страниц V   1 2 3 > » 
Ответить в данную темуНачать новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



Удалить установленные форумом cookies · Отметить все сообщения прочитанными
RSS Текстовая версия