?

Log in

No account? Create an account
задачка - Наместник Карлсона На Земле
April 25th, 2003
07:53 am
[User Picture]

[Link]

Previous Entry Share Next Entry
задачка
Троим преступникам сообщают, что сейчас их разведут по одиночным камерам, не оставляя никаких средств сообщения друг с другом, кроме одного:
иногда то того, то этого будут отводить в некоторую комнату с выключателем (стандартный он\офф) и лампочкой, которую он включает.
Лампочку можно включить, можно выключить, можно ничего не делать.
Водить их так будут неограниченное число раз, пока кто-нибудь из них не скажет, что все трое уже побывали в этой комнате хотя бы по одному разу.
Если это верно - всех отпустят, если нет - всех казнят.
Сначала им предоставляется возможность разработать тактику, при которой они выйдут на свободу. Вам предлагается сделать это за них.

У задачи есть два варианта:
в одном они знают, включена изначально лампочка или выключена, в другом - не знают.
Никаких подколов, чиста канкретна математицкое решение.

Tags:

(40 comments | Leave a comment)

Comments
 
[User Picture]
From:amigofriend
Date:April 25th, 2003 05:04 am (UTC)

(Link)
Чёта я её слышал на днях, но выключателей было два, ничего не делать было нельзя, а вот преступников было
ДВАДЦАТЬ ТРИ.

Или мне это по пьяни послышалось?
[User Picture]
From:elcour
Date:April 25th, 2003 05:15 am (UTC)
(Link)
Даю подсказку: число преступников большой роли не играет. Главное, чтоб их было больше двух.
А если ничего не делать нельзя - то да, логично, одним выключателем не обойдёсся. Постой, а можно включить и выключить? :-)
[User Picture]
From:photon
Date:April 25th, 2003 08:16 am (UTC)
(Link)
Кажется есть решение которое работает только для трех преступников...
[User Picture]
From:elcour
Date:April 25th, 2003 08:40 am (UTC)
(Link)
Плохо. Мало.
Хотя, канешна, давай. ;-)
[User Picture]
From:photon
Date:April 25th, 2003 08:55 am (UTC)
(Link)
Один преступник всегда оставляет после себя включеную лампочку, другой выключеную. Третий собственно должен определить когда в камере побывали двое остальных. Для этого ему нужно минимум 3 посещения (при условии что первоначальное состояние неизвестно). Когда он видит что лампочка измеила свое состояние 2 раза - (вкл.-выкл.-вкл. или наоборот) - значит все.
[User Picture]
From:igorbor
Date:April 25th, 2003 07:05 am (UTC)
(Link)
В варианте, который я слышал, их водили в камеру каждый день. В смысле - каждый день строго по одгому из них (но, конечно, могли неделю подряд подить одного и того же). Мне почему-то кажется, что "иногда" - это сильно осложняет задачу. По-моему, если их водят нерегулярно - задача может решения не иметь.
[User Picture]
From:elcour
Date:April 25th, 2003 07:15 am (UTC)

(Link)
Какая разница?
[User Picture]
From:alexcohn
Date:April 25th, 2003 08:31 am (UTC)
(Link)
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf предлагает разнообразные варианты оптимизации в зависимости от начальных условий. То, что лампочка потушена сначала и то, что водят каждый день, сокращают ожидаемое время заключения.
[User Picture]
From:elcour
Date:April 25th, 2003 09:10 am (UTC)

для особо продвинутых - следуюшшая задачка:

(Link)
есть три компьютера:
русский - всегда врёт
американский - всегда говорит правду
и
китайский - непредсказуемый.
из них ты готов купить любой, лишь бы не китайский. ты можешь задать одному из них один вопрос на да-нет, вслед за чем выбрать какой-нибудь компьютер.

задачка имеет решение ;)
[User Picture]
From:mistysugar
Date:April 26th, 2003 11:52 am (UTC)

Re: для особо продвинутых - следуюшшая задачка:

(Link)
Отбираешь два компа и одного спрашиваешь: "Что бы ты ответил на вопрос, правда ли это, что только один из вас (отобранной пары) русский или американец?" Если ответ "да", тогда третий (кот. в стороне) точно не китаец. Если ответ "нет", то не-китаец - второй ("пассивный" комп из отобранной пары).
[User Picture]
From:elcour
Date:April 26th, 2003 06:16 pm (UTC)

Re: для особо продвинутых - следуюшшая задачка:

(Link)
Увы.
Представь себе, что ты спросила русского, а в паре с ним - американец. Он ответит утвердительно, а китаец как раз - третий.
К слову, тот же вопрос формулируется проще: "Есть ли в вашей паре китаец"?
Но это не оно. Думай дальше.
[User Picture]
From:alexcohn
Date:April 27th, 2003 01:15 am (UTC)

вариант на 50%

(Link)
Пожалуй, нужно задать такой вопрос, на который нет нельзя ни ответить правду, ни соврать. Тогда китайский компьютер ответит "да" или "нет", а любой другой - сгорит от перенапряжения. Правда, остается вопрос - зачем покупать сгоревший компьютер.

Пример такого вопроса: "Ты уже прекратил насиловать малолетних перед завтраком?"

Для того, чтобы не сломать ценный прибор, можно задать такой вопрос, на который и русский, и американский заведомо ответят "да". Например: "ты - американский?" Тогда ответ "нет" однозначно укажет на китайца. Проблема в том, что и китаец может ответить "да"...
[User Picture]
From:elcour
Date:April 27th, 2003 07:34 am (UTC)

Re: вариант на 50%

(Link)
Сломать прибор, по условиям задачи, невозможно.
А на вопрос: "Ты уже прекратил насиловать малолетних перед завтраком?" - компьютер ответит в соответствии с принципами своей работы (правду, ложь, либо случайно), ибо этого он, видимо, не прекращал ни разу за всю свою бытность компьютером.

mistysugar уже решила. Подтягиваемся, подтягиваемся.
[User Picture]
From:igorbor
Date:April 25th, 2003 06:39 pm (UTC)
(Link)
Прошу прощения, насчет регулярности я, конечно, стормозил. Вещь абсолютно ненужная.

Знание начального состояния лампочки может сократить время ожидания и делает алгоритм детерменистким.

Могу решение запостить сюда, могу выдать по требованию.
[User Picture]
From:solmyr
Date:June 15th, 2005 01:33 pm (UTC)
(Link)
Расскажите уже, интересно ведь :) Для случая, когда состояние лампочки заранее известно, я умею. А если неизвестно - нет.
Powered by LiveJournal.com