theJam.ru

Логические задачиТысяча туземцев

28 мая 2008 | Добавил: aleg940

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

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки

Комментариев: 27

  1. noxwelle пишет:

    Если он вызовет одного человека, а тот был лжецом, то туземец скажет правду, что он лжец?

  2. SusAnna пишет:

    лжец не может сказать правду!
    Если путешественник вызовет одного туземца и спросит "сколько среди вас лжецов?", то лжец ответит "0", так как правильный ответ "1", а он должен солгать.

  3. Shurick пишет:

    Правдивец как минимум один. Т.е. их количество [1, 999].
    А лжец может хоть число хоть (-4+3i) назвать (наверное :) ). При этом все лжецы в вызванной группе могут называть одно и то же число, не являющееся правдой.
    А правда, если вызван один лжец, на вопрос "Сколько среди вас лжецов?" он может ответить "3"?

  4. SusAnna пишет:

    А правда, если вызван один лжец, на вопрос “Сколько среди вас лжецов?” он может ответить “3″?

    может.
    Задача состоит в том, чтобы рассмотреть наихудший вариант ответов туземцев (то есть, когда совсем ничего не понятно) и посчитать за сколько часов можно определить кто есть кто.
    А так, можно ответить, что за 1 час, ибо все лжецы ответят допустим числа больше 1000, а правдивцы скажут правильный ответ.
    то есть нужно найти минимум часов, за которое можно определить всех лжецов и правдивцев вне зависимости от ответов.

  5. Shurick пишет:

    Когда путешественник опрашивает группу, отвечают все вызванные туземцы поочереди?

  6. SusAnna пишет:

    Когда путешественник опрашивает группу, отвечают все вызванные туземцы поочереди?

    это не имеет значения. Путешественник обладает абсолютной памятью, он запоминает всех кого вызывал и что каждый из них ответил. Вызывать можно одних и тех же туземцев несколько раз.

  7. Shurick пишет:

    Я про другое. Если путешественник вызвал двоих, отвечают оба?
    И еще хочу оточнить: "вопрос о численности среди них либо правдивцев либо лжецов."
    "Они" - это вызванная группа или все племя?

  8. SusAnna пишет:

    Если путешественник вызвал двоих, отвечают оба?

    отвечают все в группе

    “Они” - это вызванная группа или все племя?

    о численности лжецов или правдивцев среди группы

  9. liveD3 пишет:

    раз путешественник обладает абсолютной памятью и легко запоминает кто что сказал то впринципе достаточно одного часа и задать вопрос сразу всему племени "вы все здесь правдивцы ?" лжецы естественно начнут врать "да" и только правдивцы ответят "нет" ...

  10. Ms пишет:

    liveD3, неверно

  11. Shurick пишет:

    Ms,
    А почему у liveD3 неверно? Вроде все по условию?

  12. Ms пишет:

    Требуется спрашивать о кол-ве: "Сколько среди вас лжецов(правдивцев)?"
    Задачка несколько сложнее, все же... :)

  13. tolstys пишет:

    хм...тогда пусть вызовет всех и спросит: сколько среди Вас правдивцев? того, кто крикнет "один", можно забирать))

  14. SusAnna пишет:

    tolstys, а если правдивцев двое?
    подсказка:
    допустим, что среди N выбранных туземцев правдивцев Х, какое число они назовут?

  15. XANT пишет:

    Все правдивцы назовут одно и тоже число лгунов, а лгуны никогда не назовут это число.

  16. SusAnna пишет:

    XANT, неверно

  17. XANT пишет:

    Этот предпосыл верен, иначе, что же получиться, если лгуны назовут тоже количество льгунов, что и правдивцы.
    Например: путешественник задает всем 1000 туземцам один и тот же вопрос "Сколько среди Вас льжецов?" и получит разные ответы, но только один из них будет истинным, остальные ложные.

  18. SusAnna пишет:

    хорошо, а если 2-е скажут что лжецов 998, а остальные 998 скажут, что лжецов двое? сколько лжецов среди тысячи туземцев?

  19. XANT пишет:

    Извеняюсь, что сразу не ответил на поставленный вопрос.
    Итак после первого вопроса заданного всем 1000 туземцам, мы имеем две группы туземцев, двое утверждают, что врунов 998, а 998 туземцев утверждают, что врунов 2(в сумме и там и там 1000). Путешественник поступает следующим образом: вызывает двух туземцев которые назвали число-998 и любых двух туземцев которые промурлыкали цифру- 2(при этом путешественник точно знает, что из двух групп по 2 туземца в каждой, в одной только правдивцы, в другой группе только лжецы).
    Задает им вопрос "Сколько среди Вас лжецов"?
    Правдивце ответят 2.
    Лжецы не могут ответят два, иначе они скажут правду, значит в любом случае они назовут любое число отличное от 2.
    Вывод: тот кто на поставленный вопрос назовет цифру два тот и будет правдивец.
    Следовательно затем нетрудно определить сколько всего лжецов и правдивцев имеется на острове.

  20. SusAnna пишет:

    вот теперь все верно. Только аппроксимируйте ответ в общем случае, не привязываясь к моему примеру с 998 и 2.

  21. XANT пишет:

    Обобщенное решение:
    В первый раз Путешественник может пригласить 1000 туземцев и задать вопрос "Сколько среди Вас лжецов?", при этом:
    -все правдивцы назовут одно и тоже количество лжецов-L, а разность между 1000-L=P даст нам количество правдивцев, в тоже время ни один из лжецов никогда не озвучит число лжецов названных правдивцами (число будет или меньше или больше числа названного правдивцами);
    -может оказать, что среди озвученного количества лжецами несколько ответов тоже будут составлять в сумме 1000, но разности будут отличаться от P, тогда обозначим эти разности Р1,Р2,Р3…Рn.
    А вот потом Путешественник может сортировать как угодно группы(ведь ситуаций может возникнуть множество) и задавать вопросы(или, или).
    В этой задаче интересен вопрос о времени, который к решению задачи по большому счету ни какого отношения не имеет, зато нечаянно можно зациклиться на определении этого времени.

  22. SusAnna пишет:

    XANT, ай-яй-яй. Так хорошо начали а к должному выводу так и не пришли. Есть точный ответ за сколько часов он определит сколько среди туземцев лжецов. Вообще-то задача напрямую зависит от времени, так как в условии сказано что он может вызывать по одной группе в час. То есть, если в первый час он вызвал всю тысячу, то следующую группу по своему усмотрению он может вызвать только через час. Фактически Вам нужно определить сколько групп и по какому правилу нужно вызывать.

  23. XANT пишет:

    Точно не хорошо, но ведь задача не плохая, поэтому если участники допишут решения это будет просто здорово.

  24. Pantheon пишет:

    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, а честных людей трое (мы этого, конечно, не знаем пока).
    Хех... Кого и как Вы будете опрашивать дальше? :)

  25. SusAnna пишет:

    Pantheon, до решения осталось совсем чуть-чуть... Действительно за 2 часа можно определелить кто есть кто.

  26. tib пишет:

    пожалуй первым вопросом будет опросить всех туземцев, сколько среди них правдивцев
    группа - это те туземцы, которые назвали одно и то же число при ответе на первый вопрос.
    вызываем по одному из каждой группы, численность которой равняется сказанному числу, и опять спрашиваем, сколько среди них правдивцев. Кто скажет "1", тот и правдивец, а вместе с ним и вся его группа :)

  27. SusAnna пишет:

    tib, браво! Наконец-то дошли до финала :)

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать