ABVGD ([info]abvgd) wrote,
@ 2008-10-04 14:50:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Current music:Judas Priest -- Victim Of Changes

а вот еще задачка
В тюрьме сидят 100 математиков. Одни сели за то, что всегда лгут, другие -- за то, что всегда говорят правду. Каждый из них знает, кто сидит за правду, а кто за ложь. В один прекрасный день начальника тюрьмы уволили за тупость. Чтобы проверить нового претендента, руководство ФСИН поручило ему как можно скорее определить, кто за что сидит. При этом ему сообщили, что за ложь сидят не все, и разрешили делать следующее: один раз в день собирать группу из любого количества зэков, раздавать им листки с вопросом "Сколько человек в этой группе сидят за ложь?" и собирать ответы.

Претендент управился в два дня и получил высокое назначение. Как он действовал?

UPD. в комментах появился правильный ответ, так что если кому интересно самому порешать, учитывайте это )


Advertisement

(Post a new comment)


[info]pavel_
2008-10-04 12:23 pm UTC (link)
Сначала собрал всех, раздал им листки. Затем выбрал самое повторяющееся число. Во второй раз собрал тех, кто написал этот ответ. И отсеял лгунов, которые написали то же самое число.

Правда, это сработает, только если лгуны не действуют согласованно. И не сработает, если правдивых математиков слишком мало.

(Reply to this)(Thread)

[info]abvgd
2008-10-04 12:33 pm UTC (link)
не, такая схема сработает только в отдельных случаях
представьте, 20 человек написали число 10, и оно самое повторяющееся
во второй день собираем этих 20 -- все они, очевидно, либо лжецы, либо правдецы
если правдецы, то все напишут во второй день 0, и задача действительно решена
а если лжецы, то все напишут не 0, и мы поймем, что это 20 лжецов -- но ничего не сможем сказать про остальных 80

однако вы на правильном пути

(Reply to this)(Parent)(Thread)

[info]pavel_
2008-10-04 12:59 pm UTC (link)
20 человек написали число 10,
Этого не может быть. Если только 20 человек говорит правду, то все они должны написать 80. Получается ещё одна проверка. (правда, ничто не мешает лгуну написать правдоподобное число).

(Reply to this)(Parent)(Thread)

[info]abvgd
2008-10-04 01:08 pm UTC (link)
вы правы, я погорячился, в случае если мы попали на 20 правдецов, они должны были в первый заход написать 80, а не 10
но случая со лжецами это не отменяет

(Reply to this)(Parent)(Thread)

[info]pavel_
2008-10-04 01:12 pm UTC (link)
Но с другой стороны ничто не мешает лжецам хором написать 0.

(Reply to this)(Parent)(Thread)

[info]abvgd
2008-10-04 01:32 pm UTC (link)
ну да
но это ничего не скажет про оставшихся 80

(Reply to this)(Parent)

[info]pavel_
2008-10-04 02:50 pm UTC (link)
Предположим, что 20 человек написали "80", 80 человек написали "20". Если во второй раз пригласить по 20 человек и из одной, и из другой группы, то ровно половина из них напишет "20", оставшаяся половина - всё, что угодно, только не 20 (они ведь лгут всегда). Так мы и найдём лжецов.

Правда, ситуация может быть сложнее.

(Reply to this)(Parent)(Thread)

[info]abvgd
2008-10-04 03:01 pm UTC (link)
ага
изначально вообще все числа могут быть разными

(Reply to this)(Parent)(Thread)

[info]pavel_
2008-10-04 03:53 pm UTC (link)
Если абсолютно все произнесли разные цифры, нашёлся один человек, который сказал "99". Именно он и сказал правду.

(Reply to this)(Parent)(Thread)

[info]abvgd
2008-10-04 03:58 pm UTC (link)
вы уже буквально в шаге от полного решения

(Reply to this)(Parent)

[info]pavel_
2008-10-04 01:01 pm UTC (link)
> лгунов, которые написали то же самое число.

Понял, что этого быть не может.

(Reply to this)(Parent)

[info]andenisov
2008-10-04 12:32 pm UTC (link)
Вопрос по существу - а что такое ложь математика?

(Reply to this)(Thread)

[info]abvgd
2008-10-04 12:38 pm UTC (link)
:))
ну в принципе же никто не мешает ему тайком правильно решать задачки, а на людях сплошь врать
правда есть вопрос, на который он не сможет ответить: "ты лжец?"

(Reply to this)(Parent)

(Reply from suspended user)

[info]r00kie
2008-10-05 08:38 am UTC (link)
что-то до сих пор ответа не было.
В первый день опросить всех. Если только одному числу будет соответствовать количество ответов с этим числом - то это есть количество правдорубов.
Если таких чисел два, на следующий день собрать по одному человеку из этих двух выборок. Правдоруб скажет 1, а лжец 1 сказать не сможет.

(Reply to this)(Thread)

[info]abvgd
2008-10-05 08:54 am UTC (link)
почти точно, но не совсем
ведь групп, написавших одинаковые числа, может быть и больше двух

(Reply to this)(Parent)

[info]russian_savage
2008-10-05 08:49 am UTC (link)
У Вас забанены анонимы, пришлось завести ЖЖ. :))

Итак, решение.
Допустим в тюрьме сидит х лжецов, тогда правдецов будет 100-х. Отсортируем все ответы по группам. Группа правдецов будет обладать следующим свойством: в ней будет 100-х человек ответивших х. Таких групп может быть произвольное число. На следующий день соберём из каждой группы по одному человеку (не забудем их пронумеровать) и зададим тот же вопрос. Мы знаем, что в комнате ТОЛЬКО ОДИН правдец. Соответственно по ответу мы его и вычислим. А по его ответу в прошлый раз определим количество лжецов.

ps Но самое красивое и быстрое решение было предложено неизвестным математиком из Лангедока в 12 веке. "Убивайте всех! Господь признает своих".

(Reply to this)(Thread)

[info]abvgd
2008-10-05 08:53 am UTC (link)
так точно

ps анонимов специально не банил, оно само :)

(Reply to this)(Parent)

[info]pavel_
2008-10-05 10:38 am UTC (link)
Хотел написать примерно то же самое.
но ведь вся схема рассыпается, если опрос - анонимный. В условиях следует оговорить обратное.

(Reply to this)(Parent)(Thread)

[info]abvgd
2008-10-05 11:03 am UTC (link)
может быть... но, с другой стороны, и запрета смотреть, кто какой ответ дал, в условиях нет

(Reply to this)(Parent)

[info]russian_savage
2008-10-05 01:33 pm UTC (link)
Всегда остаётся вариант лангедокского математика :))

(Reply to this)(Parent)

[info]revoltp
2008-10-07 01:19 pm UTC (link)
да, сообщество для второго вопроса можно формировать проще: взять по одному человеку из каждой группы. Где под группой имеются в виду люди, ответившие одинаково на первый вопрос. Т.к. все честные ответили одинаково, то они попали в ону группу и будут представлены лишь одним человеком.

(Reply to this)(Parent)

[info]itar_stass
2008-10-05 02:31 pm UTC (link)
В тюрьме сидят 100 математиков... кроваввый режим расправляется с научной элитой))

(Reply to this)(Thread)

[info]abvgd
2008-10-05 03:32 pm UTC (link)
ну а что с ними еще делать, если они все время правду говорят? :)

(Reply to this)(Parent)

[info]langov
2008-10-05 08:15 pm UTC (link)
1. кандидат собирает всю сотню и спрашивает их. Затем ищет среди ответов такие, чтобы Ni+Ai = 100, где Ni - количество одинаковых ответов Аi, i от 1 до некоего n. То есть если за правду сидят трое математиков, все трое напишут "97", а остальные напишут другие числа. Если количество таких "групп" n равно 1, поиски заканчиваются, сразу все понятно. Но может получиться несколько групп, т. к. 4 лжеца могут написать "96" и т. д.
2. Берет из каждой i-й группы по i человек и собирает их вместе, повторяя ту же процедуру.

Пример. Трое из ста написали "97", четверо - "96", десятеро - "90". Из первых троих берем одного, из четверых - двух, из десятерых - 3. Итого 6. Если "правдолюбы" были в первой группе, из котрых теперь один, он напишет "5". Двое из второй группы теперь не могут написать "4", т. к. это будет правдой. Трое из третьей тоже не могут написать "3", поэтому у них будут какие-то другие числа.

(Reply to this)(Thread)

[info]abvgd
2008-10-05 08:20 pm UTC (link)
> Берет из каждой i-й группы по i человек

все верно, только достаточно из каждой i-й группы по одному взять, а не по i

(Reply to this)(Parent)(Thread)

[info]langov
2008-10-05 08:24 pm UTC (link)
ну это я уж допетрил, когда комменты прочитал :)) разум постоянно пытается немножко усложнить :)

(Reply to this)(Parent)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…