?

Log in

No account? Create an account
hina_chleck
December 16th, 2008
01:48 pm

[Link]

Previous Entry Share Flag Next Entry
Про две задачки и мои недодумывания
(Интересно не всем будет).
Первая из разряда – три ящика с разной логикой (на один вход: "да", "нет", "да/нет"). Выбрать ящик с жесткой логикой за один вопрос одному из них вслепую с незнанием языка (то есть, произнесено в ответ "да" или "нет" - неизвестно)
Исходный аналог: задача про двух братьев и две дороги.

Моя ошибка ==Неа, все равно, как ни строй многоэтажную конструкцию вопроса, выходит неполнота. Ну, сделаю я: "Если бы вы были лгун, то на вопрос, ведет ли эта дорога в город, произнесете ли вы "пиц-поц", при условии, что это значит "нет"? Уф.==
Но наличие многих неизвестных, оказывается, необязательно означает невозможность построения логической однозначной конструкции:

Ответ мне:
==Ключ ко всему, фундамент -- задача с братанами. Если помните, там решение -- спросить "что скажет твой братан на вопрос". Почему-то именно в таком виде все знают, хотя понятно, что точно так же будет работать и "что скажешь ты на вопрос". С братанами логика основана на (-1)*1 = 1*(-1) = -1, а с одним -- на (-1)*(-1) = 1*1 = 1. Потом Вы замечаете, что Вам, собственно, все равно, спрашивать про "нет", или про "да" -- всегда совпадение инпута и аутпута есть подтверждение, а несовпадение -- опровержение. А раз так -- то Вам, очевидно, и "да"-"нет" знать не надо -- это может быть просто пара "ага"-"угу", что из них "да", а что "нет" -- Вас не волнует.
Итого, значит, спросив "ответишь ли ты КУКУ на вопрос, верно ли Т", Вы всегда знаете, что Т верно, если в ответ прозвучало "КУКУ", и ложно, если "КУКАРЕКУ". Еще раз, простите за занудство -- независимо от того, честный перед Вами, или лжец, и независимо от того, что из КУКУ-КУКАРЕКУ есть "да", а что "нет".
Теперь с нашей тройкой. У них, значит, для ответов есть КУКУ-КУКАРЕКУ, или красная-зеленая лампочка, не суть. Главное -- Вы уже умеете с их помощью ориентироваться в окружающем мире. Проблема только с этим, который по случайному механизму(испорченный).
Давайте, один из трех будет для вопроса. А выбирать мы будем из оставшихся двух(Вася и Петя). Тогда мы спросим у него: "ответишь ли ты КУКУ на вопрос, испорчен ли Вася?". При условии, что спрашиваемый исправен, мы по ответу всегда поймем, испорчен ли Вася. Если да -- берем Петю, если нет -- берем Васю.
Это -- если спрашиваемый исправен. Но если он вдруг неисправен -- то мы ничем не рискуем, если применим к его ответам ту же логику. Потому что в итоге, руководствуюсь его ответом, мы выберем между Васей и Петей, а они-то оба исправны, так что нам бояться нечего.==
Вторая задачка: ==Есть сто бедолаг, их собирают, и объявляют о завтрашнем испытании. Завтра всем наденут колпачки, но вместо бубенчиков -- с номерами от единички до ста(ничего о единственности не сказано, номера могут повторяться -- может, все сто одинаковые будут). Каждый будет видеть 99 колпаков с номерами, и не видеть свой. Сигналы запрещены. Каждый пытается угадать номер на своем колпаке. Записывает догадку на бумажке(остальные не видят), и сдает контролеру. Если хоть один угадает свой номер -- всех отпустят целыми и невредимыми, если никто -- всех казнят. Сегодня они могут посовещаться между собой и придумать стратегию на завтра. Какую?==

Мой тяжкий ход мыслей
==Мне непонятно: вот есть два чела и есть четыре комбинации из 0 и 1.
Допустим, они выберут какую-то стратегию (для первого, например) в зависимости от числа на колпаке другого. Но как определить, какая стратегия будет выбрана, если они не могут подавать сигналы?
...Значит... должен быть единственный вариант...
...Есть смутная идея, что должен быть кто-то ведущий. Лидер. Обама, короче. Вышло так для двоих: ведомый, всегда не думая, пишет то, что видит у ведущего.
Ведущий же должен подумать и написать то, что должно скомпенсировать неверный ответ ведомого (в сумме, чтобы была единица).
Ну, если одинаковые у обоих О/1 - то ясно и так, а если разные - ведомый напишет заведомо неверный ответ, Обама думает тогда: "Если он напишет неверно, то я остаюсь один, который может верно написать. Исходя из компенсации ошибки, лидер теперь пишет, глядя на цифру ведомого - пишу наоборот. Если у меня единица - угадаю я, если же ноль - угадает он.
Для трех - непонятно пока, как один скомпенсирует ошибки двоих...
Или тогда цепочка начинается: ведомый-ведущий со сдвигом по людям?==

Ответ мне:
==Вы же уже почти сами доехали, просто не сообразили, как по-другому назвать "разные" и "одинаковые". Как только это сообразится -- общий случай станет очевиден.
Так вот, "разные" -- это "сумма равна 1". "Одинаковые" -- "сумма равна 0". Все, естественно, по модулю 2, и пара 1-2 заменена на 0-1. Очевидно тогда, что в общем случае каждый должен предполагать разную сумму по модулю N. То бишь, попросту, чуваки должны рассчитаться по порядку номеров, и каждый свой номер запомнить. Потом, глядя на шапки товарищей, каждый в уме проговаривает: "я предполагаю, что полная сумма равна К(где К -- запомненный номер); коль скоро это так -- мой шапка равен К минус сумма товарищей"(естественно, все по модулю N). Поскольку общая сумма чему-то, да равна, а все ее возможные значения чуваки зацапали, то кто-то обязательно выйдет прав, а значит, и шапку свою вычислит правильно.

На самом деле интересная по-настоящему -- только задачка про пару, потому что пока не поймешь, что события "разные" и "одинаковые" образуют полное -- остается ощущение такого странного бреда, кролика из шляпы. Как так, мол -- я говорю, как вижу, а он наоборот, и вдруг оказывается, что один всегда попадет...==

Разъяснение на примере для 121
==Итак:
По порядку номеров они уже рассчитаны -- 1, 2, 3. Вычтем единичку у каждого, чтоб удобней было с числами по модулю работать.

Первый будет полагать сумму равной 0 по модулю 3.
Второй будет полагать сумму равной 1 по модулю 3.
Третий будет полагать сумму равной 2 по модулю 3.

Из всех шапочных номеров для удобства будем вычитать единичку, чтобы говорить не об 1, 2, 3, а об 0, 1, 2. Мы потом ее восстановим.
Впрочем, можно этого и не делать, поскольку сумма всех трех -- так и так три эти лишние единички занулит. Тогда в логике у каждого единичку обратно добавлять не надо, а если получился 0 -- заменять на тройку.

Смотрят на соседей.
Первый: я вижу 2 и 1, то бишь, 1 и 0. Их сумма по модулю 3 равна 1, я загадал 0, значит, мой номер 0-1 = -1 = 2(арифметика же -- по модулю 3), то бишь, добавив обратно единичку, 3.
Второй: я вижу 1 и 1, то бишь, 0 и 0. Их сумма по модулю 3 равна 0, я загадал 1, значит, мой номер 1-0 = 1, то бишь, добавив обратно единичку, 2.
Третий: я вижу 1 и 2, то бишь, 0 и 1. Их сумма по модулю 3 равна 1, я загадал 2, значит, мой номер 2-1 = 1, то бишь, добавив обратно единичку, 2.

Значит, догадки: 3, 2, 2. Второй угадал. Сумма шляп по модулю 3 есть(что вычитай единички, что не) (1+2+1)(mod 3)=1. То бишь, та самая, на которую и закладывался второй.==

Tags:

(8 comments | Leave a comment)

Comments
 
From:(Anonymous)
Date:December 18th, 2008 03:03 am (UTC)

Зфзф-Фш

(Link)
3-я задачка
Есть сто бедолаг, их собирают, и объявляют о завтрашнем испытании. Завтра всем наденут колпачки, но вместо бубенчиков -- с номерами от единички до ста(ничего о единственности не сказано, номера могут повторяться -- может, все сто одинаковые будут). Каждый будет видеть 99 колпаков с номерами, и не видеть свой. Сигналы запрещены. Каждый пытается угадать номер на своем колпаке. Записывает догадку на бумажке(остальные не видят), и сдает контролеру.
, если никто не отгадает свой номер -- всех казнят. Если хоть один угадает свой номер ,то на заключенных cнова одевают шапочки в соответствии с записанном номером на бумажке и процедура повторяется.
Если номера шпочек всех заключенных совпадут с первоначальными то их
всех отпустят целыми и невредимыми.
Заключенные нашли стратегию ,которая позволила им освободиться. Сколько раз им пришлось переодевать шапочки?
[User Picture]
From:hina_chleck
Date:December 18th, 2008 05:48 am (UTC)

Re: Зфзф-Фш

(Link)
УФ. Не мучьте дитю. Давайте тогда вынесем снова стервятникам?
[User Picture]
From:hina_chleck
Date:December 18th, 2008 05:50 am (UTC)

Re: Зфзф-Фш

(Link)
Стоп, не поняла - что значит - переоденут в соответствии с номером на бумажке?
Был 59, на бумажке написано 41, наденут ему 41?
From:(Anonymous)
Date:December 19th, 2008 01:24 am (UTC)

Зфзф-Аш

(Link)
> Был 59, на бумажке написано 41, наденут ему 41?
точно так
[User Picture]
From:hina_chleck
Date:December 19th, 2008 05:42 am (UTC)

Re: Зфзф-Аш

(Link)
Если у вас есть решение - давайте его сразу. Я вам медаль повешу. Шоколадную. На Новый год - вот самое то.
From:(Anonymous)
Date:December 20th, 2008 05:17 pm (UTC)

Зфзф-Аш

(Link)
Хорошо,даю подказку. Отгадывать шапочку всегда будет один и тот же преступник.
From:(Anonymous)
Date:December 20th, 2008 11:30 pm (UTC)

Зфзф-Аш

(Link)
Хм...подсказка оказалась неверной для случая 100 преступников.
А получилась еще одна задачка ==> продолжение последней. Итак,на самом деле номер шапочки отгадывали по очереди два преступника. Удивившейся надзиратель спросил, у одного отгадывавшего про стратегию,которую преступники выбрали. Стратегия совпала с ответом na вторую задачку.
Тогда надзиратель спросил у преступника загаданное число,и оно оказалось равным 3.
Ага сказал надзиратель,я знаю какой номер загадал второй угадывавший номер шапочки преступник.
Какой номер был загадан?
From:(Anonymous)
Date:December 21st, 2008 04:39 pm (UTC)

Зфзф-Аш

(Link)
Ответы на задачки пожалуиста:
1. 100 -раз
В общем случае Н - если число преступников нечетное или делится на 4. и
2*Н - если число преступников четное и не делится на 4.
2. Преступник загадавший номер 53. ================================================================ И комментарий к первой задачке про преступников. В условиях к задаче нигде не говорится о том какая стратегия должна быть. Поетому логически любой ответ является правильным.
Скажем, наихудщей стратегией будет загадать всем преступником определенный номер заранее.
"Случаиная стратегия " - если преступники не договариваются вообще дает вероятность 1/100.
Я понимаю,что подразумевается "наилучшая стратeгия". Но тогда интересно наити не решение,а первоначально определить что даст эта лучшая стратегия. И каким критериям она удовлетворяет.
Если вы знаете решение,то вопрос уже как бы теряет смысл.

Тем не менее. Рассмотрим для простоты случай 3-х преступников. У нас есть 27 возможных ответов. Ответ первого,например, 1 покрывает 1/3(или 9 возможных ответов). Как должны отвечать 2-оставшихся преступника? Каждый из них своим ответом тоже может покрыть только 9 -возможных ответов.
Легко видеть,что если один из преступников отгадывает номер,два оставшихся не должны отгадывать номера своих шапочек. Такая стратегия покроет все 27 возможных ответов. Если же стратегия приводит к тому ,что два преступника могут угадать свои номера одновременно,то она не является наилучшей, поскольку оставит хотя бы один случай,когда никто из преступников свой номер не отгадает. Сложно?
По-моему очевидно. Это и есть своиство,совпадения одного разряда. =================================================================
Powered by LiveJournal.com