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

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



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

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

Всем привет,
предлагаю решить такую задачку:

В комнате стоят 100 одинаковых коробок, выстроенных в ряд. В каждой из них находится имя одного из 100 узников — причём имя каждого из них находится в одной из этих коробок. Узников по очереди запускают в комнату. Каждый из них имеет право открыть 50 коробок из ста. Если хотя бы один из них не найдёт своего имени, все они будут казнены; если же каждому удастся найти своё имя — всех выпустят на свободу. Узники не имеют права — и возможности — общаться друг с другом после выхода из комнаты; никаких пометок в комнате делать нельзя; перекладывать имена в коробках нельзя (впрочем, надзиратели этого делать тоже не будут). Короче говоря, каждый узник находит комнату в точно том же состоянии, что и предыдущий. Единственная возможность пообщаться — ДО испытания.

Как им следует действовать, чтобы вероятность выжить для них оказалась выше 30%?

Кто решит сам, тот молодец!
Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


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

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

Предлагаю для продления интереса к загадке писать найденные ответы цветом фона. Например, так (попробуйте выделить строку ниже):

*Этот текст виден только после выделения строки*
*Этот текст виден только после выделения строки*

Делается это следующим образом:


Последний раз редактировалось: Konstantin A. Timofeev (Пн Фев 19, 2007 13:00), всего редактировалось 1 раз
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


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

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

*[color=#EFEFEF]Этот текст виден только после выделения строки[/color]*
*[color=#DEE3E7]Этот текст виден только после выделения строки[/color]*

К сожалению, придется угадывать, какой цвет фона используется для вашего сообщения (их бывает два).
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


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

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

Шуточный вариант ответа:
*Первый узник открывает 50 коробок и не закрывает, затем второй открывает 50 оставшихся и не закрывает. Следующим узникам уже ничего открывать не надо --- нужно только смотреть Wink. Вероятность успеха 0.5.*

Менее "нахальный" вариант, приводящий к тому же результату, следующий (смущает фраза "каждый узник находит комнату в точно том же состоянии, что и предыдущий", ну да будем считать, что комната в том же состоянии, а коробки нет):
*Решил, что разработчикам не стоит публиковать свое решение Wink*

P.S. надеюсь, я правильно истолковал условие.


Последний раз редактировалось: Konstantin A. Timofeev (Чт Фев 22, 2007 17:41), всего редактировалось 1 раз
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Victoria K.



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

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

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

П.с. и еще узники могут общаться между собой до испытания.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Alexandr Vassilliev



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

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

А коробки то переставлять можно?Они ведь одинаковые, следовательно комната не будет изменяться.
И еще, узники знают друг друга, то есть знают кто и каким зайдет в комнату?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

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

Нет, комната не изменяется - коробки как были на своих местах, так и остаются, закрытыми. А узники, конечно, знают друг друга и могут каким-то образом договориться.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Alexandr Vassilliev



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

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

Ну это врядли..Нет, ну если переставить коробки местами, то комната останется в начальном виде, ничего не измениться.
Ну вот есть 2 буквы А,А, то есть разница между АА и АА(а на самом деле я их переставил местамиSmile)?
ИМХО, единственный способ как-то дать знать, как другим - это переставить местами коробки..
Короче, я так решил задачу. Ответ получился *99/200*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


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

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

А почему тогда не *1/2? Ведь можно всегда переставить коробки так, чтобы в первых 50-ти коробках было имя следующего заключенного.*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Victoria K.



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

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

Нельзя переставлять коробки!
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


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

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

Еще один вариант: узники не должны выбирать ничего - первый заходит и остается в комнате жить - ему повезло! (он не обязан открывать коробки, а только "имеет право"). При этом узников, конечно же, не выпустят, и им придется вернуться в свои камеры, но зато они останутся в живых. Smile Ведь так ставилось условие задачи? А 30% --- это вероятность хорошего настроениея, охранников, которым такой "фокус" не понравится.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Konstantin A. Timofeev
Site Admin


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

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

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



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

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

Конечно возможно я не прав, но вот мое доказательство того, что это невозможно:*Рассмотрим возможные действия первого, он не обладает абсолютно никакой информацией, а следовательно может открыть не более 50 произвольных коробок. Очевидно, что открывать меньше 50 смысла не имеет. Коробки идентичны друг другу, следовательно не важно, какие 50 коробок он откроет, будем считать, что он открыл левые 50 коробок. Он находит свое имя в этих 50 коробках с вероятностью 1\2. Подумаем, о чем могут договориться узники : рассмотрим условия вида if A then B else C, которое надо понимать следующим образом : если на К-м шаге процесса выполнится условие А, то К+1-й узник должен сделать действие B, а в противном случае - C. Очевидно, что условия такого вида невозможны, поскольку информация о выполнении или не выполнении условия А появится только после входы К-го узника в комнату, а тогда К+1-й узник, который не умеет возможности общаться с К-м после его входи в комнату, не узнает, выполнено или нет условие А, а следовательно не сможет принять решение об условном переходе. Таким образом договоренность узников может иметь вид А1,...,А100, где Аi - набор строго определенных действий. Так как единственное действие, которое может совершать узник в комнате - открывание не более 50 коробок, то единственно возможный вид договоренности - это фактически номера коробок, которые будет открывать К-й узник. В этих терминах А1 - набор чисел 1-50. Рассмотрим всевозможные значения А2. Очевидно, это опять таки набо не более чем 50 номеров коробок, которые откроет 2-й узник. Понятно, что открывать менее 50 коробок нецелесообразно. Допустим, что действие А2к состоит в том, что 2-й узник открывает к коробок из интервала 51-100 и 50-к коробок из интервала 1-50. Какого оптимальное значение к? Предположим, что в интервале 1-50 наверняка имеется имя первого узника(иначе мы проиграли и процесс закончен). Очевидно, что оптимальное к=50, так как если к<50, то вероятность второго узника найти свое имя будет меньше из-за того, что существует шанс вытащить имя первого. Для этого оптимального случая вероятность успеха равна 50\99. А следовательно независимо от последующих действий вероятность выживания всех узников уже не может быть выше чем 1\2*50\99=25\99<30%.*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

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

Цитата:
Еще один вариант: узники не должны выбирать ничего - первый заходит и остается в комнате жить - ему повезло! (он не обязан открывать коробки, а только "имеет право"). При этом узников, конечно же, не выпустят, и им придется вернуться в свои камеры, но зато они останутся в живых. Ведь так ставилось условие задачи? А 30% --- это вероятность хорошего настроениея, охранников, которым такой "фокус" не понравится.


"Если хотя бы один из них не найдёт своего имени, все они будут казнены." Так что если они в итоге вернутся в свои камеры, то имена свои, естественно, не найдут. Так что их казнят.
Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

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

Цитата:
Кстати, Вика, а такой способ общения возможен?


А это идея! Бедные заключенные, сколько же им придется в памяти хранить, чтобы запомнить все комбинации и соответствующее им время.
P.S. А есть еще и азбука Морзе. Тогда вообще красота получается. Smile

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

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


Powered by phpBB © 2001, 2005 phpBB Group