НГУ

Форумы НГУ
Текущее время: Чт фев 22, 2018 11:56 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Жизнь по барабану
СообщениеДобавлено: Ср ноя 16, 2005 11:32 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
В одной восточной стране правитель был большим оригиналом. Вот уж в который раз решил он свои тюрьмы почистить - что-то много там дармоедов сидит. Думал-думал и придумал барабан.

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

Устройство барабана изнутри. Слева от каждой дыры на одинаковых расстояниях на гвоздик прибито по 1 селёдке. Селёдки идентичны и гвоздик располагается в её центре тяжести. Каждая из селёдок может занимать два положения, закрепляемые специальными фиксаторами - головой вверх или головой вниз. Барабан изнутри разбит на 4 одинаковых отсека так, что в каждом отсеке 1 дыра и 1 селёдка. Исходное расположение каждой из селёдок перед процедурой устанавливается с помощью датчика случайных чисел. Узник это расположение не знает, так как снаружи селёдок не видно.

Процедура. Узнику предоставляется максимум 5 попыток. За одну попытку узник может засунуть руки в любые две из четырёх дыр, путём ощупывания узнать расположение селёдок и, если возникнет желание, изменить положение одной или обеих на противоположное. После этого руки вынимает, барабан вращают, и после остановки он готов к новой попытке. Вращение барабана не меняет закреплённое фиксаторами положение селёдок.
Если после одной из попыток все селёдки расположатся одинаково, узника отпускают. Таким образом, некоторым, особо везучим, предоставят свободу без всяких попыток, другим потребуется побороться за свою жизнь. Тем, кому не удастся сонаправить все четыре селёдки даже после пятой попытки, отрубят голову.

Оценить шансы узников.

_________________
Наука умеет много гитик.


Последний раз редактировалось bolbot Чт ноя 17, 2005 3:15 pm, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2005 12:30 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Чтобы поднять шансы оценить шансы узников, необходимо уточнить условие. Сказано, что через каждую дыру достижима только одна селедка, а из дальнейшего понятно, что достижимы по крайней мере 2 селедки из четырех. Но из условия вовсе не следует, что достижымы все 4 селедки. То есть не получится ли, что через разные дыры узник будет хватать одну и ту же селедку? Надо ли понимать так, что через каждую из 4 дыр достижима своя персональная для дыры селедка? И еще. Когда говорится, что узник может придать селедке одно из двух положений, не говорится, что узник будет знать, в какое именно положение он ее поставил. Так будет или не будет?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2005 2:18 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
ОК, отредактировал.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2005 8:07 pm 
Не в сети
Частый гость

Зарегистрирован: Сб сен 11, 2004 3:48 pm
Сообщения: 72
Откуда: Николай
bolbot, эту задачу (с почти дословной точностью) предлагали в компании Майкрософт лет 5 назад при приёме на работу программеров. Интересное совпадение... А Вы, Александр Дмитриевич, её сами придумали? Если да, то когда?

_________________
If we knew what it was we were doing, it would not be called research, would it? © A. Einstein


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 6:29 am 
Не в сети
Частый гость

Зарегистрирован: Пн ноя 07, 2005 8:11 pm
Сообщения: 29
Пусть у нас два положения:положение 1 ,положение 2.Мне так удобней.
1ая ПОПЫТКА:в какую-нибудь дырку засунули руку,сделали положение 1,засунули руку в дырку противоположную предыдущей(т.е через одну)тоже сделали положени 1.Итак в одной диагонали у нас две рыбки с положением 1.
2ая ПОПЫТКА:засунули руку в любую дырку сделали положение 1,и в какой-нибудь соседней дырке тоже сделали положение 1.
Итак мы можем утверждать,что после двух попыток у нас как минимум в трёх дырка положение 1.
Если дело дошло до 3ей попытки,значит в одной дырке у нас ещё положение 2,тогда
3я ПОПЫТКА:засунули руку в любую дырку.если положение 2, то меняем на 1 и мы спасены! Если положение 1, то если в соседней 2 меняем на 1(мы спасены),если 1 меняем на 2.Если получилось последнее,то у нас противоположные дырки имеют положения в одном случае 1 и 1,а вдругой 2 и 2.
4ая ПОПЫТКА:засунули руку в любую дырку,поменяли положение,и через одну дырку предыдущей(т.е противоположной )поменяли тоже положение.Получим везде одно положение.


Спасены,надеюсь!!!?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 8:59 am 
Не в сети
Частый гость

Зарегистрирован: Вт ноя 08, 2005 12:57 am
Сообщения: 34
Virt писал(а):
bolbot, эту задачу (с почти дословной точностью) предлагали в компании Майкрософт лет 5 назад при приёме на работу программеров. Интересное совпадение... А Вы, Александр Дмитриевич, её сами придумали? Если да, то когда?
Эту задачу, мы решали в ЛШ-98, а давал ее нам наш воспет, которому ее рассказывали еще раньше. Имхо Майкрософт к ее авторству никакого касательства не имеет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 9:22 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
MOM писал(а):
3я ПОПЫТКА:засунули руку в любую дырку.если положение 2, то меняем на 1 и мы спасены! Если положение 1, то если в соседней 2 меняем на 1(мы спасены),если 1 меняем на 2.Если получилось последнее,то у нас противоположные дырки имеют положения в одном случае 1 и 1,а вдругой 2 и 2.

В этом пункте ошибка.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 10:03 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Эту задачу мне дочь протелефонировала во вторник вечером, до этого её не слышал. Практически ничего в ней не менял, разве только попытался туману подпустить, изменив вопрос.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 12:47 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
bolbot писал(а):
Практически ничего в ней не менял, разве только попытался туману подпустить...

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 1:32 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Гост_Я писал(а):
Возможно, туман даже настолько густ, что никто и не заметит, если путем неподчинения требованию вынимать руки перед очередным вращением барабана хитрый узник освободится легко и досрочно.

Освободится от рук? :)
Впрочем, я это заметил, но дополнительно редактировать уже не стал, надеюсь на инстинкт самосохранения.
А вот ради этого пришлось-таки зайти и ещё раз отредактировать.
Цитата:
Чтобы путём ощупывания узнать расположение и особенно изменить положение одной или обеих дыр на противоположное

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 4:48 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Пт окт 21, 2005 12:34 pm
Сообщения: 180
Гост_Я писал(а):
MOM писал(а):
3я ПОПЫТКА:засунули руку в любую дырку.если положение 2, то меняем на 1 и мы спасены! Если положение 1, то если в соседней 2 меняем на 1(мы спасены),если 1 меняем на 2.Если получилось последнее,то у нас противоположные дырки имеют положения в одном случае 1 и 1,а вдругой 2 и 2.

В этом пункте ошибка.


Ошибка, потому что в последнем случае мы не можем сказать точно - либо противоположные, либо соседние. (У нас ситуация - 3 селедки в одном положении, четвертая селедка в другом (иначе уже спасены), а руку засунуть мы можем как в крайнее из трех положение - тогда МОМ прав, так и в среднее положение - тогда не получится...)
Найти стопроцентный способ спасения нельзя.... :( Можно только действительно оценить шансы. Если мы, допустим, сделали 2 попытки, в результате которых получили ситуацию - 3 селедки в одном положении, 1 в другом, то можно рискнуть - следующие три попытки делать одно и то же - допустим, засовывать руки в противоположные дырки и дальше смотреть по обстоятельствам. Вероятность того, что за три попытки он засунет одну из рук в среднее положение из трех - и есть ответ.

_________________
Никогда не знаешь, где тебе повезет...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт ноя 17, 2005 5:51 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
eva666 писал(а):
Найти стопроцентный способ спасения нельзя.... Можно только действительно оценить шансы... можно рискнуть ...
Рискнуть головой?

Итак, после двух попыток мы получили (1112). Тогда в третьей попытке мы засовываем руку в первую попавшуюся дыру (в барабане) и без колебаний и раздумий меняем положение селедки. Вторую руку при этом ... Далее следует текст скрытый настолько умело, что я не знаю, возможно ли его вообще прочитать. (Проверил, увидеть возможно, скопировав в Word, увеличив размер шрифта и сменив его цвет с белого на черный.)
Вторую руку при этом заносим в диаметрально противоположную дыру только для того, чтобы узнать, в каком положении теперь находятся все селедки. А именно, если ощупываемые разными руками селедки ориентированы одинаково, то имеем случай а) (1212), а если ориентированы различно, то случай б) (1122).
Далее можно не ощупывать и не задумываться. В случае а) (1212) вертим две любые не соседние селедки. В случае б) (1122) сначала вертим две любые соседние селедки, затем две любые не соседние селедки.
Как видно, во всей операции по освобождению только во второй попытке надо немного подумать, а в третьей - немного пощупать. Остальные попытки выполняются при полном умственном и физическом расслаблении.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 18, 2005 12:35 am 
Не в сети
Частый гость

Зарегистрирован: Сб сен 11, 2004 3:48 pm
Сообщения: 72
Откуда: Николай
Крендель писал(а):
Virt писал(а):
bolbot, эту задачу (с почти дословной точностью) предлагали в компании Майкрософт лет 5 назад при приёме на работу программеров. Интересное совпадение... А Вы, Александр Дмитриевич, её сами придумали? Если да, то когда?
Эту задачу, мы решали в ЛШ-98, а давал ее нам наш воспет, которому ее рассказывали еще раньше. Имхо Майкрософт к ее авторству никакого касательства не имеет.

Если честно, то я был почти уверен, что эту задачу придумали не в Майкрософте. Раз уж они порой умудрялись делать деньги (и не малые) на том, что придумали другие... :)

_________________
If we knew what it was we were doing, it would not be called research, would it? © A. Einstein


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 18, 2005 1:29 pm 
Не в сети
Частый гость

Зарегистрирован: Пн ноя 07, 2005 8:11 pm
Сообщения: 29
Извинияюсь за ошибку в решении.Попробую исправить:
Итак.Если дело дошло до 3ей попытки то у нас такое дело (2111).
3я ПОПЫТКА: Засунули руку в дырку. Если положение 2, меняем на 1(спасены).
если 1 ,то меняем на 2.Заглядываем в противоположную предыдущей(т.е через одну)дырку и ничего не меняем,только смотрим(ну или щупаем:)) и понимаем: a)если в ней значение 2,то у нас получилось хорошее положение:
противоположные дырки имеют положения в одном случае 1 и 1,а вдругой 2 и 2.
b)Если в ней положение 1,то у нас получилось (2211).
4ая ПОПЫТКА: если a)очевидно.засунули руку в любую дырку,поменяли положение,и через одну дырку предыдущей(противоположной )поменяли тоже положение.Получим везде одно положение. Спасены.
если b)засунули руку.Пусть например получили 2(не нарушая общности,всё-таки 2211)меняем на 1.Засунули руку в соседнюю, меняем на противоположную.И получаем:либо спасены т.е положение(1111).Либо,если дело дошло до пятой попытки,значит у нас положение(2121).
5ая ПОПЫТКА(если дело дошло до неё):
то есть у нас противоположные дырки имеют положения в одном случае 1 и 1,а вдругом 2 и 2.
очевидно.засунули руку в любую дырку,поменяли положение,и через одну дырку предыдущей(противоположной )поменяли тоже положение.Получим везде одно положение. Спасены.

А теперь спасены!!!?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт ноя 18, 2005 9:39 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Всё верно, хотя не сразу врубился в шаг 3-й.
Алгоритм можно описать чуть проще.
К примеру, в 3-й попытке суём сразу две руки в две противоположные дырки и если в одной из них 2 (кстати, почему 1 и 2, а не 0 и 1?), то ясно, что делать. В противном случае меняем одну из 1 на 2.

PS. Всё-таки затуманивание имело результат - многие понимают эту задачу как вероятностную :)
Туман в сторону - вопрос попроще: сколько попыток достаточно для случая трёхсекционного барабана?

Далее, как доказать без тупого перебора, что 4-х попыток недостаточно для гарантированного выхода на свободу?

И ещё вопрос (сам ещё не думал, но кажется он посложнее):
Специально для одного узника изготовили барабан с 8 секциями. Правила аналогичны - в одну попытку можно засунуть все руки. Существует ли гарантированное число попыток для выхода на свободу четверорукого создания?

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB