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

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


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

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

Стратегия - это договор между узниками "до начала мероприятия" о том, каким образом каждый из них будет принимать решение о том, какие коробки открывать, зайдя в комнату.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Yuri S. Gubernatorov



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

СообщениеДобавлено: Вт Фев 27, 2007 0:36    Заголовок сообщения:  узники Ответить с цитатой

Спасибо, Нина Эдуардовна!
Придумал с Вашими подсказками некое решение, которое оказалось не менее удивительным, чем задачка.
На самом деле, о решении (ну, о самом красивом варианте) я подумал сразу, как прочитал условие, но тут же отбросил его как совершенно невозможное.
Действительно 10 плюсиков при n = 2. И еще 1285920 плюсиков при n = 5. Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


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

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

Похоже, я понял в чем дело (по крайней мере, для 4-х ящиков, выводить теорию что-то не хочется). Ну и задачка!

Кстати, видел для phpbb плагин, позволяющий отображать скрытый текст, появляющийся при нажатии на него мышкой. Если эта тема будет развиваться - поставлю.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Victoria K.



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

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

Цитата:
Узник 1 открывает коробки с номерами 1-50. Если он не находит там своего имени, то операция прекращается. Если кроме своего имени он находит также имя узника "2", то он остается в комнате еще некоторое время (скажем, до достижения 15 минут с момента входа), иначе выходит сразу.


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

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



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

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

[code]Действительно 10 плюсиков при n = 2. И еще 1285920 плюсиков при n = 5
[/quote]

Это что за плюсики такие?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

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

У меня какие-то проблемы со связью, поэтому прошу прощения, если сообщения будут удваиваться.

И если все поняли, напишите ответ задачи (с обоснованием), кто-нибудь!

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

И решение задачи про монеты. Все-таки. А это не решение Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Konstantin A. Timofeev
Site Admin


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

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

Цитата:
А теперь отберем у узников часы, чтобы они не могли засекать время, и сделаем выход из комнаты с другой стороны, т.е. так, чтобы узники не видели выходящего. И пусть эта комната будет звукоизолирована, чтобы они не могли переговариваться или использовать азбуку Морзе.

Хороший способ запретить вариант решения "с засеканием времени" --- потребовать, чтобы узники запускались через равные интервалы. Хочу отметить, что даже в англоязычной формулировке этого требования нет.

Коробки:
*Для четырех коробок: пусть изники имеют имена "1", "2", "3", "4". Очередной узник, заходя в комнату, открывает коробку с номером, равным своему имени. Если там его имени нет, то открывает коробку с номером, равным имени, которое он нашел. Обоснование --- прямая проверка Smile.*
Монеты:
*Например, можно так:

1. Сравнить два набора по 33 монеты в каждом. (35 монет не участвует в сравнении)

2а. Если они равны, то выбрать из совокупности этих наборов любые 35 монет (они все одинаковые и "правильные") и сравнить с 35 другими, которые не участвовали в первом эксперименте (среди них фальшивая).

2б. Ели в результате эксперимента 1 один из наборов оказался тяжелее другого, то нужно сравнить более тяжелый набор с любым набором из 33 монет, не участвовавших в эксперименте 1 (в этом наборе все монеты "правильные").
*
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Yuri S. Gubernatorov



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

СообщениеДобавлено: Ср Фев 28, 2007 0:58    Заголовок сообщения:  узники Ответить с цитатой

Плюсиками отмечаю те перестановки на которых стратегия выигрывает. По-видимому можно было бы найти выражении для количества таких перестановок, но я смог придумать только процедуру подсчета. Для n=50, меньше, чем за час, насчитал 29101710375112308408737714312419\
50549065075890971849496149551460\
13502183139184118875280368074817\
37201298059943427610601204444672\
389283840000000000000000000000 плюсиков, это больше, чем 0.312 * 100!.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

СообщениеДобавлено: Чт Мар 01, 2007 16:22    Заголовок сообщения:   Ответить с цитатой

Про узников:
Цитата:
Обоснование --- прямая проверка

Хех. Ну хорошо Smile
Только там есть некоторые рассуждения, кроме простой проверки.

Про монеты тоже хорошо Smile
Зачет. Smile
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

СообщениеДобавлено: Чт Мар 01, 2007 16:40    Заголовок сообщения:   Ответить с цитатой

Цитата:
Плюсиками отмечаю те перестановки на которых стратегия выигрывает. По-видимому можно было бы найти выражении для количества таких перестановок, но я смог придумать только процедуру подсчета. Для n=50, меньше, чем за час, насчитал 29101710375112308408737714312419\
...

389283840000000000000000000000 плюсиков, это больше, чем 0.312 * 100!.


Shocked
А если число узников/коробок = 1000?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Yuri S. Gubernatorov



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

СообщениеДобавлено: Чт Мар 01, 2007 18:28    Заголовок сообщения:   Ответить с цитатой

Victoria K. писал(а):
А если число узников/коробок = 1000?

Зато проверка очень прямая %)
По-настоящему это, конечно, не решение. Не спорю. Потом может быть и формулу придумаем. На досуге.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Yuri S. Gubernatorov



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

СообщениеДобавлено: Сб Мар 03, 2007 16:31    Заголовок сообщения:   Ответить с цитатой

Я случайно придумал формулу для задачи узников. Не знаю, может уже, конечно, все ее придумали, но давайте уж поставим точку в этой задаче.
При количестве узников 2n, стратегия выигрывает если в перестановке 2n чисел все циклы не длиннее n. Посчитать такие перестановки, как я продемонстрировал выше, можно, но сложно в вычислительном плане. Намного проще оказывается сосчитать перестановки в которых имеются циклы длиннее n. (Кстати, Вика на это намекала выше.)
Таких перестановок существует \sum_{i=1}^n {C_{2n}^{n+i}(n+i-1)!(n-i)!}, отсюда найдем вероятность проигрыша:
Pn = \sum_{i=1}^n {1\over n+i}
Попутно заметим, что Pn представляет собой разность частичных сумм гармонического ряда:
Pn = H_{2n} - H_n
поэтому, предел Pn по n, стремящемся к бесконечности, равен ln(2), а ln(2) меньше чем 0.7.

UPD:
1) Чтобы на самом деле поставить точку надо, наверное, подчеркнуть, что, поскольку Pn возрастает при возрастании n, вероятность победы заключенных больше 1-ln(2) при любом n.
2) Мне вот интересно: как можно доказывать, что не существует более эффективных стратегий? Или как их искать, если они вдруг могут существовать?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Victoria K.



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

СообщениеДобавлено: Вт Мар 06, 2007 15:14    Заголовок сообщения:   Ответить с цитатой

Цитата:
Я случайно придумал формулу для задачи узников.

Хорошо звучит "случайно"! С каким распределением? Smile

Решение засчитано!

P.S. Честно говоря, немного заумное...
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Yuri S. Gubernatorov



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

СообщениеДобавлено: Вт Мар 13, 2007 23:28    Заголовок сообщения:  узники - 2 Ответить с цитатой

Детская задачка.

Узники прочитали форум на statmod.ru, удача им улыбнулась, их отпустили. Они ограбили банк и чтобы честно поделить между собой добычу решили устроить голосование. Бывшие узники по очереди предлагают вариант дележа. После каждого предложения голосуют (голосовать можно только «за» или «против»). Если большинство голосует «против», то предложившего тут же убивают, после чего начинается слушанье предложения следующего. Если не меньше половины проголосовало за принятие предложения, то оно принимается и процедура заканчивается. Каждый бывший узник старается 1) выжить, 2) максимизировать свою долю не подвергая себя опасности и 3) сохранить побольше товарищей, если это не уменьшает его долю и не приводит к его гибели.
Вопрос: как они поделят добычу?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
kokorins



Зарегистрирован: 14.08.2006
Сообщения: 67
Год выпуска, специализация, статус: 2008, SS

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

Ура, ура задача про коробки решилась за 24 часа! Правда кроме как реализовать алгоритм, в голову ничего не пришло. Как оказалось, ответ совпал с ответом Кости!

Задача про монеты очень старая(уже знаю ответ).
Буду думать над детской задачкой.

Может кто-нибудь знает как решать задачу про хрустальные шары:
Есть два шара и 100 этажное здание нужно узнать, начиная с какого этажа шары разбиваются за минимальное число попыток!(шары одинаковые) разбитый шар кидать заново нельзя?(уже не один месяц думаю, пока ничего толкового не придумал)

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

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


Powered by phpBB © 2001, 2005 phpBB Group