Сайт студентов и выпускников кафедры Статистического Моделирования statmod.ru
Кафедра Статистического Моделирования
 
ФотоальбомФотоальбом  FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 

Задачки
На страницу Пред.  1, 2, 3, 4  След.
 
Начать новую тему   Ответить на тему    Список форумов statmod.ru -> Беседка
Предыдущая тема :: Следующая тема  
Автор Сообщение
Victoria K.



Зарегистрирован: 11.09.2006
Сообщения: 42
Год выпуска, специализация, статус: 2007, САПР

СообщениеДобавлено: Пт Фев 23, 2007 17:26    Заголовок сообщения:   Ответить с цитатой

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


Почему не имеет? Он будет открывать по очереди коробки, пока не найдет свое имя: 1...k. (k<=50). Так что ему не обязательно открывать ВСЕ 50 коробок. Т.е. У него может быть что-то вроде "пути", который он совершит до своей коробки. (Можно посмотреть с такой точки зрения?)

Цитата:
Подумаем, о чем могут договориться узники : рассмотрим условия вида if A then B else C...


Честно говоря, у меня мозг перенапрягся. Зачем так усложнять? Smile

Цитата:
Так как единственное действие, которое может совершать узник в комнате - открывание не более 50 коробок, то единственно возможный вид договоренности - это фактически номера коробок, которые будет открывать К-й узник.


О, хорошо!

Цитата:
Допустим, что действие А2к состоит в том, что 2-й узник открывает к коробок из интервала 51-100 и 50-к коробок из интервала 1-50.

Какого оптимальное значение к?

Предположим, что в интервале 1-50 наверняка имеется имя первого узника(иначе мы проиграли и процесс закончен). Очевидно, что оптимальное к=50, так как если к<50, то вероятность второго узника найти свое имя будет меньше из-за того, что существует шанс вытащить имя первого.
Для этого оптимального случая вероятность успеха равна 50\99.

Т.е. имеется ввиду то, что это есть вероятность того, что второй найдет свое имя.

Цитата:
А следовательно независимо от последующих действий вероятность выживания всех узников уже не может быть выше чем 1\2*50\99=25\99<30%.


Предположим так. А если не знать ничего про ответ, то каким образом им дальше следует поступать, если продолжить процесс для остальных узников?
Если рассмотреть для числа коробок/узников = 4, например (всего 4! перестановок).

P.S. На самом деле можно добиться, чтобы для n=4 Р(гибели) = 7/12 => Р(выживания) = 5/12.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



Зарегистрирован: 11.09.2006
Сообщения: 42
Год выпуска, специализация, статус: 2007, САПР

СообщениеДобавлено: Пт Фев 23, 2007 17:38    Заголовок сообщения:   Ответить с цитатой

И еще одна задачка про монеты:
Имеется 101 монета. С виду они все одинаковые, но одна из них отличается весом. Вопрос: как, имея лишь чашечные весы, за 2 взвешивания определить, тяжелее она или легче других монет?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 642
Год выпуска, специализация, статус: 2005, аспирант СМ

СообщениеДобавлено: Пт Фев 23, 2007 21:54    Заголовок сообщения:   Ответить с цитатой

Да нет же, что-то вы все усложняете. Можно поступить следующим образом:*Первый узник открывает 1-50 коробки. Обмен информацией производится следующим образом. До начала мероприятия известен порядок узников в очереди. Если после захода очередного узника прошло больше 15 минут до запуска очередного заключенного, значит следующему узнику нужно искать свое имя в коробках с номерами 51-100, иначе в коробках с номерами 1-50. Вот и все.*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Nina E. Golyandina
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 934
Год выпуска, специализация, статус: давно, статмод

СообщениеДобавлено: Пт Фев 23, 2007 23:47    Заголовок сообщения:   Ответить с цитатой

На самом деле, задача о узниках и коробках очень красивая в своей первоначальной формулировке, без шутливых дополнений. И действительно имеет решение, хотя в это трудно поверить.
(Идею решения знала, поэтому похвастаться, что сама решила, не могу.)
Задача непростая. Вот пара "легких" подсказок
1.*Имеет смысл искать идею для 4-х человек/коробок*
2.*Понятно, что такого эффекта можно достигнуть только если результаты людей очень сильно коррелированы*
3.*Память у узников должна быть хорошо развита, линейно по числу узников Smile*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 642
Год выпуска, специализация, статус: 2005, аспирант СМ

СообщениеДобавлено: Сб Фев 24, 2007 16:05    Заголовок сообщения:   Ответить с цитатой

Тогда еще один вопрос к Вике: *Узники обязаны с первого раза открывать все 50 коробок, или они могут открыть несколько, затем выйти из комнаты и встать в конец очереди?*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Alexandr Vassilliev



Зарегистрирован: 21.02.2007
Сообщения: 5
Год выпуска, специализация, статус: 2009, САПР, студент)

СообщениеДобавлено: Сб Фев 24, 2007 22:41    Заголовок сообщения:   Ответить с цитатой

ну с монетами задача совсем легкая)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Nina E. Golyandina
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 934
Год выпуска, специализация, статус: давно, статмод

СообщениеДобавлено: Вс Фев 25, 2007 1:38    Заголовок сообщения:   Ответить с цитатой

Цитата:
Тогда еще один вопрос к Вике:
Отвечаю за Вику. Каждый узник обязан за один раз открыть все 50 коробок.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Victoria K.



Зарегистрирован: 11.09.2006
Сообщения: 42
Год выпуска, специализация, статус: 2007, САПР

СообщениеДобавлено: Вс Фев 25, 2007 17:44    Заголовок сообщения:   Ответить с цитатой

Цитата:
ну с монетами задача совсем легкая)

Кому как Smile

Цитата:
Первый узник открывает 1-50 коробки. Обмен информацией производится следующим образом. До начала мероприятия известен порядок узников в очереди. Если после захода очередного узника прошло больше 15 минут до запуска очередного заключенного, значит следующему узнику нужно искать свое имя в коробках с номерами 51-100, иначе в коробках с номерами 1-50. Вот и все.


Даже если и так. То дальнейшая стратегия у них какая?
А вообще говоря, не так. Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 642
Год выпуска, специализация, статус: 2005, аспирант СМ

СообщениеДобавлено: Пн Фев 26, 2007 10:58    Заголовок сообщения:   Ответить с цитатой

Цитата:
Даже если и так. То дальнейшая стратегия у них какая?
В смысле? По-моему, я все подробно описал. Ну да ладно, повторю подробнее:
  1. Пусть узники имеют "имена" 1,2,...,100 и в очереди узник с "именем" n+1 стоит за узником с "именем" n, т.е. первым в комнату заходит узник с "именем" 1
  2. Узник 1 открывает коробки с номерами 1-50. Если он не находит там своего имени, то операция прекращается. Если кроме своего имени он находит также имя узника "2", то он остается в комнате еще некоторое время (скажем, до достижения 15 минут с момента входа), иначе выходит сразу.
  3. Пусть в комнату заходит узник с "именем" n, n>1. Если предыдущий узник (с номером n-1) прождал в комнате более 15 минут, тогда он открывает коробки с номерами 1-50. Иначе, он открывает коробки с номерами 51-100. Для n=2 ясно, что свое имя он найдет с вероятностью 1. Для n>2 это также будет очевидным, так как формат передаваемой информации сохранится. Ясно также, что просмотрев 50 коробок (с начала или с конца - не важно) из 100 узник n будет знать, в какой части коробок (1-50 или 51-100) находится "имя" n+1. Теперь он поступает как первый узник. Если он знает, что "имя" n+1 находится в коробках 1-50, то он ждет достижения 15 минут с момента входа, иначе выходит сразу.

Это точно сработает, даже задача достижения вероятности выживания 1/3 существенно перевыполнена Smile.

А задача с монетами (IMHO) действительно простая.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Nina E. Golyandina
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 934
Год выпуска, специализация, статус: давно, статмод

СообщениеДобавлено: Пн Фев 26, 2007 12:23    Заголовок сообщения:   Ответить с цитатой

Цитата:
Это точно сработает, даже задача достижения вероятности выживания 1/3 существенно перевыполнена

Как бы там ни было, а >0.3 получается без обратной связи. Т.е. никакой передачи информации после захода узника в комнату не происходит.
Удивительность результата еще и в том, что при числе узников 2n предел по n, стремящемся к бесконечности, тоже больше 0.3.
Чтобы поверить в результат, я честно выписала для n=2 все 24 перестановки коробок и приписала им +, если узники выживают при стратегии, которая является ответом. Действительно получилось 10 плюсов Smile.
P.S. Дополнение к условию задачи: узник не обязан, заходя в комнату, сразу назвать все номера коробок, которые он хочет открыть.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 642
Год выпуска, специализация, статус: 2005, аспирант СМ

СообщениеДобавлено: Пн Фев 26, 2007 13:57    Заголовок сообщения:   Ответить с цитатой

Цитата:
Дополнение к условию задачи: узник не обязан, заходя в комнату, сразу назвать все номера коробок, которые он хочет открыть.
Т.е. в комнату могут зайти сразу несколько узников?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Nina E. Golyandina
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 934
Год выпуска, специализация, статус: давно, статмод

СообщениеДобавлено: Пн Фев 26, 2007 15:05    Заголовок сообщения:   Ответить с цитатой

Цитата:
Т.е. в комнату могут зайти сразу несколько узников?

Нет, конечно. Не надо упрощать условие Smile
Я имею в виду, что ящики узник может открывать и так: Откроет один, посмотрит, что там. Затем откроет другой. И т.д.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 642
Год выпуска, специализация, статус: 2005, аспирант СМ

СообщениеДобавлено: Пн Фев 26, 2007 15:33    Заголовок сообщения:   Ответить с цитатой

Nina E. Golyandina писал(а):
Я имею в виду, что ящики узник может открывать и так: Откроет один, посмотрит, что там. Затем откроет другой. И т.д.
Да... забавно Smile, особенно наряду с
Victoria K. писал(а):
...комната не изменяется - коробки как были на своих местах, так и остаются, закрытыми.
Nina E. Golyandina писал(а):
Каждый узник обязан за один раз открыть все 50 коробок.
Nina E. Golyandina писал(а):
...без обратной связи.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Nina E. Golyandina
Site Admin


Зарегистрирован: 31.07.2006
Сообщения: 934
Год выпуска, специализация, статус: давно, статмод

СообщениеДобавлено: Пн Фев 26, 2007 15:50    Заголовок сообщения:   Ответить с цитатой

А в чем забавность-то?
Костя, вы, по-моему, между строк что-то там читаете. В принципе, в изначальной формулировке задачи все сказано. Все остальное - это ответ на шуточные расширения условия Smile
Вот точная формулировка на английском:

The names of 100 prisoners are placed in 100 wooden boxes, one name per box (assume the are all named differently). The boxes are lined up on a table in a room. Prisoners would be allowed in one by one. Each may look at the contents of 50 of the boxes, but they cannot rearrange the boxes, change the contents, i.e. they have the leave the room the way the found it. The entrance and exit of the room are separated, so prisoners who have looked cannot communicate with prisoners who haven't looked.

The king decrees the following: if all prisoners find the box with their own names, they would be free. Otherwise they'd be executed. They are given a chance to talk this through in advance before the first prisoner is led into the room.

There is one strategy that could lead to a chance of survival greater than 30%. How?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Yuri S. Gubernatorov



Зарегистрирован: 26.02.2007
Сообщения: 9
Год выпуска, специализация, статус: 2007, MM

СообщениеДобавлено: Пн Фев 26, 2007 17:49    Заголовок сообщения:  узники Ответить с цитатой

Удивительная задачка!
Правильно ли я понял, что стратегией считают соответствие между узниками и наборами открываемых коробок?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов statmod.ru -> Беседка Часовой пояс: UTC + 3
На страницу Пред.  1, 2, 3, 4  След.
Страница 2 из 4

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы можете вкладывать файлы
Вы можете скачивать файлы
RSS feed


Powered by phpBB © 2001, 2005 phpBB Group