theJam.ru
|
Разделы:
Lifehack12
Данетки95
Игры139
Игры на бумаге17
Книги14
Конкурсы8
Логические задачи346
Люди3
Новости6
Познавательно33
Почемучки14
Притчи4
Работа сайта10
Разное10
Сделай сам10
С праздником16
Страшно жить10
Творчество41
Тесты14
Фото4
Хобби2
Юмор105
 Логические задачи → Тысяча туземцев
28 мая 2008 | Добавил: SusAnna
Путешественник попал в плен на острове, где живут туземцы (правдивцы и лжецы), всего 1000 аборигенов, причем среди них есть как минимум один правдивец и путешественник об этом знает. Ему пообщещали жизнь, если он точно укажет, кто из туземцев является лжецом, а кто правдивцем. Каждый час путешественник может позвать любое количество туземцев и задать им один и тот же вопрос о численности среди них либо правдивцев либо лжецов. За какое минимальное количество часов путешественник справится с этой задачей и даст туземцам ответ? Примечание: каждой вызванной группе нужно задавать один и тот же вопрос.
Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки → логические
|
Случайное:
Обсуждения:
Ogra → Инспектор Варнике
Carcass → Тест советского восьмиклассника
Руслан → Слова, оканчивающиеся на “зо”.
ололошин → Незадачливый рыбак
lisicanasta → Инквизиция в наши дни
Ogra → И все же, они вертятся?
SM → Последовательность
Nastya → Бесконечная игра
SpAwN# → Самая трудная игра в мире
Полезное:
Карта сайта:
|
29 мая 2008 в 09:12
Если он вызовет одного человека, а тот был лжецом, то туземец скажет правду, что он лжец?
29 мая 2008 в 12:00
лжец не может сказать правду!
Если путешественник вызовет одного туземца и спросит "сколько среди вас лжецов?", то лжец ответит "0", так как правильный ответ "1", а он должен солгать.
29 мая 2008 в 12:15
Правдивец как минимум один. Т.е. их количество [1, 999].
А лжец может хоть число хоть (-4+3i) назвать (наверное :) ). При этом все лжецы в вызванной группе могут называть одно и то же число, не являющееся правдой.
А правда, если вызван один лжец, на вопрос "Сколько среди вас лжецов?" он может ответить "3"?
29 мая 2008 в 12:58
может.
Задача состоит в том, чтобы рассмотреть наихудший вариант ответов туземцев (то есть, когда совсем ничего не понятно) и посчитать за сколько часов можно определить кто есть кто.
А так, можно ответить, что за 1 час, ибо все лжецы ответят допустим числа больше 1000, а правдивцы скажут правильный ответ.
то есть нужно найти минимум часов, за которое можно определить всех лжецов и правдивцев вне зависимости от ответов.
29 мая 2008 в 15:21
Когда путешественник опрашивает группу, отвечают все вызванные туземцы поочереди?
29 мая 2008 в 16:46
это не имеет значения. Путешественник обладает абсолютной памятью, он запоминает всех кого вызывал и что каждый из них ответил. Вызывать можно одних и тех же туземцев несколько раз.
29 мая 2008 в 16:51
Я про другое. Если путешественник вызвал двоих, отвечают оба?
И еще хочу оточнить: "вопрос о численности среди них либо правдивцев либо лжецов."
"Они" - это вызванная группа или все племя?
29 мая 2008 в 17:13
отвечают все в группе
о численности лжецов или правдивцев среди группы
8 июня 2008 в 15:39
раз путешественник обладает абсолютной памятью и легко запоминает кто что сказал то впринципе достаточно одного часа и задать вопрос сразу всему племени "вы все здесь правдивцы ?" лжецы естественно начнут врать "да" и только правдивцы ответят "нет" ...
3 июля 2008 в 20:50
liveD3, неверно
4 июля 2008 в 11:58
Ms,
А почему у liveD3 неверно? Вроде все по условию?
5 июля 2008 в 14:04
Требуется спрашивать о кол-ве: "Сколько среди вас лжецов(правдивцев)?"
Задачка несколько сложнее, все же... :)
12 августа 2008 в 19:11
хм...тогда пусть вызовет всех и спросит: сколько среди Вас правдивцев? того, кто крикнет "один", можно забирать))
13 августа 2008 в 20:04
tolstys, а если правдивцев двое?
подсказка:
допустим, что среди N выбранных туземцев правдивцев Х, какое число они назовут?
8 сентября 2008 в 16:36
Все правдивцы назовут одно и тоже число лгунов, а лгуны никогда не назовут это число.
8 сентября 2008 в 17:37
XANT, неверно
8 сентября 2008 в 18:08
Этот предпосыл верен, иначе, что же получиться, если лгуны назовут тоже количество льгунов, что и правдивцы.
Например: путешественник задает всем 1000 туземцам один и тот же вопрос "Сколько среди Вас льжецов?" и получит разные ответы, но только один из них будет истинным, остальные ложные.
8 сентября 2008 в 18:18
хорошо, а если 2-е скажут что лжецов 998, а остальные 998 скажут, что лжецов двое? сколько лжецов среди тысячи туземцев?
9 сентября 2008 в 09:47
Извеняюсь, что сразу не ответил на поставленный вопрос.
Итак после первого вопроса заданного всем 1000 туземцам, мы имеем две группы туземцев, двое утверждают, что врунов 998, а 998 туземцев утверждают, что врунов 2(в сумме и там и там 1000). Путешественник поступает следующим образом: вызывает двух туземцев которые назвали число-998 и любых двух туземцев которые промурлыкали цифру- 2(при этом путешественник точно знает, что из двух групп по 2 туземца в каждой, в одной только правдивцы, в другой группе только лжецы).
Задает им вопрос "Сколько среди Вас лжецов"?
Правдивце ответят 2.
Лжецы не могут ответят два, иначе они скажут правду, значит в любом случае они назовут любое число отличное от 2.
Вывод: тот кто на поставленный вопрос назовет цифру два тот и будет правдивец.
Следовательно затем нетрудно определить сколько всего лжецов и правдивцев имеется на острове.
9 сентября 2008 в 12:30
вот теперь все верно. Только аппроксимируйте ответ в общем случае, не привязываясь к моему примеру с 998 и 2.
9 сентября 2008 в 13:32
Обобщенное решение:
В первый раз Путешественник может пригласить 1000 туземцев и задать вопрос "Сколько среди Вас лжецов?", при этом:
-все правдивцы назовут одно и тоже количество лжецов-L, а разность между 1000-L=P даст нам количество правдивцев, в тоже время ни один из лжецов никогда не озвучит число лжецов названных правдивцами (число будет или меньше или больше числа названного правдивцами);
-может оказать, что среди озвученного количества лжецами несколько ответов тоже будут составлять в сумме 1000, но разности будут отличаться от P, тогда обозначим эти разности Р1,Р2,Р3…Рn.
А вот потом Путешественник может сортировать как угодно группы(ведь ситуаций может возникнуть множество) и задавать вопросы(или, или).
В этой задаче интересен вопрос о времени, который к решению задачи по большому счету ни какого отношения не имеет, зато нечаянно можно зациклиться на определении этого времени.
9 сентября 2008 в 14:56
XANT, ай-яй-яй. Так хорошо начали а к должному выводу так и не пришли. Есть точный ответ за сколько часов он определит сколько среди туземцев лжецов. Вообще-то задача напрямую зависит от времени, так как в условии сказано что он может вызывать по одной группе в час. То есть, если в первый час он вызвал всю тысячу, то следующую группу по своему усмотрению он может вызвать только через час. Фактически Вам нужно определить сколько групп и по какому правилу нужно вызывать.
9 сентября 2008 в 15:12
Точно не хорошо, но ведь задача не плохая, поэтому если участники допишут решения это будет просто здорово.
24 сентября 2008 в 14:01
XANT Хммм...
По поводу предлагаемого выше варианта. Как за два часа (т.е. за два опроса двуг групп) вы выясните верное количество, если предложить такой вариант ответа участниками опроса.
(для упрощения задачи я не буду брать 1000 участников, а возьму всего 10 ! )
Из 10-ти участников, положим, сочетание такое и ответы на первый вопрос членами группы следующие (вопрос "сколько среди вас лжецов"):
L L T L T L L T L L
1 6 7 8 7 8 6 7 6 6
то есть, реально лжецов 7, а честных людей трое (мы этого, конечно, не знаем пока).
Хех... Кого и как Вы будете опрашивать дальше? :)
24 сентября 2008 в 14:12
Pantheon, до решения осталось совсем чуть-чуть... Действительно за 2 часа можно определелить кто есть кто.
25 сентября 2008 в 01:36
пожалуй первым вопросом будет опросить всех туземцев, сколько среди них правдивцев
группа - это те туземцы, которые назвали одно и то же число при ответе на первый вопрос.
вызываем по одному из каждой группы, численность которой равняется сказанному числу, и опять спрашиваем, сколько среди них правдивцев. Кто скажет "1", тот и правдивец, а вместе с ним и вся его группа :)
25 сентября 2008 в 13:16
tib, браво! Наконец-то дошли до финала :)