ФЕНИКС   На связи с единомышленниками           

 Поддержка проекта 

Авторизуйтесь с помощью соцсетей и служб

Перепись.

Автор
Опубликовано: 20 дней назад (17 ноября 2019)
+5
: 5
Перепись.


На острове живет 1001 человек - лжецы, которые всегда лгут и рыцари, которые всегда говорят правду. Прибывший на остров новый губернатор хочет выяснить, кто из островитян лжец, а кто рыцарь. Для этой цели он организует перепись населения острова. Перепись будет проводиться следующим образом. Раз в день губернатор может вызвать на переписной пункт любую группу островитян и предложить им заполнить анкету. В анкете содержится только один вопрос: «Сколько лжецов в данной группе островитян?» Каждый островитянин про каждого из остальных знает, является тот лжецом или нет. Какое наименьшее число дней продлится перепись, если губернатору известно, что не все островитяне лжецы?
177 просмотров
Комментарии (21)
ШИКО # 17 ноября 2019 в 20:14 +6
Если губернатор может вызвать на переписной пункт любую группу островитян, надо полагать, одного дня будет достаточно. smile
Александр Борисенко # 18 ноября 2019 в 02:24 +5
Дело в том, что будут разные ответы, тем более - из уст лжецов! И как среди ответов определить истинные? laugh
ШИКО # 18 ноября 2019 в 09:26 +4
Именно потому что разные ответы будут "размазаны", ответы рыцарей же составят некий пик на их фоне,можно делать какие-то выводы. joke
Nif # 18 ноября 2019 в 21:15 +5
А если рыцарь всего один? scratch
Александр Борисенко # 19 ноября 2019 в 01:29 +4
Хм! scratch Статистика - серьёзная наука! Правда, скептики утверждают, что есть три вида лжи - преднамеренная (обман), непреднамеренная (ошибка) и статистика! laugh
В нашем случае полагаться на статистику затруднительно - рыцарей может быть малое количество (кстати, Nif это уже отметил). Но если исходить из обычных реалий, в Вашем подходе, ШИКО, есть определённый резон! smile_16 smile
voliy # 18 ноября 2019 в 22:55 +5
Число одинаковых ответов+ ответ= 1001
Перепись можно провести за 1 день.
Если 1 рыцарь, то будет так: 1+1000=1001
50 рыцарей укажут число 951, 50+951=1001 и т.д.
Ответ рыцаря никогда не совпадёт с ответом лжеца. v
Александр Борисенко # 19 ноября 2019 в 01:34 +4
Верно то, voliy, что ответы группы рыцарей будут единообразны и при этом будут отличаться от разнообразных (или не разнообразных) ответов лжецов. Проблема в том, "как отделить овец от козлищ"! laugh
voliy # 19 ноября 2019 в 01:34 +5
Всё-таки неверно. 1 рыцарь может указать 1000, а 50 лжецов укажут 951. Тогда надо из каждой группы брать по 1 ещё раз. А если таких групп из лжецов будет несколько, то будет в новой группе 1 рыцарь и несколько лжецов. Их число и назовёт рыцарь. Допустим, вторая группа из 3-х человек. Рыцарь определяется, он укажет 2. Тогда по его первой группе определяется общее число лжецов. Итак, по моим подсчётам потребуется 2 дня. hoho
Александр Борисенко # 19 ноября 2019 в 01:40 +5
v Победа, voliy! Это и есть решение! Взять из каждой группы одинаково ответивших по одному представителю, среди них будет ровно один рыцарь. На тот же вопрос лжецы вынуждены фантазировать вопреки очевидности, а рыцарь скажет очевидное! smile_16 smile smile_20
Nif # 19 ноября 2019 в 05:07 +4
Что-то не вижу решение в два дня shock "Взять из каждой группы одинаково ответивших..." Сколько возьмём групп, столько потратим дней. И где гарантии, что в выбранных группах будут рыцари (тем более из 3-х человек)? 1001:3 = 334 группы.
Nif # 19 ноября 2019 в 05:15 +4
К тому же, рыцари в разных группах будут называть разные цифры, ведь вопрос «Сколько лжецов в данной группе островитян?» касается только данной группы.
voliy # 19 ноября 2019 в 10:37 +5
1. В первый день отвечают все, 1001.
2. Самый удачный случай, когда есть только одна группа, или 1 человек с суммой 1001. Тогда 1 день, ибо это рыцари отвечали, или рыцарь. А во всех остальных случаях сумма ответивших и ответа не равна 1001. Но это маловероятно.
3. Поэтому, рассмотрим возможные варианты, где есть несколько групп с суммой 1001. Одна из этих групп-рыцари, но мы не знаем какая. Тогда мы приглашаем на следующий день по 1 человеку из каждой группы и у нас образуется одна группа, где 1 рыцарь и несколько лжецов.
4. Лжец из новой группы не может назвать истинное число лжецов из присутствующих. А рыцарь назовёт число лжецов, их будет меньше на 1, чем число участников группы. Мы вычислили рыцаря)))
5.Смотрим на его первую анкету, там число лжецов. getImage 1
Nif # 19 ноября 2019 в 15:08 +4
пункт 3. "рассмотрим возможные варианты, где есть несколько групп с суммой 1001". И сколько таких групп? К тому же, по условию, только "Раз в день губернатор может вызвать на переписной пункт любую группу островитян и предложить им заполнить анкету". И сколько дней потратит губернатор? Явно больше двух дней.
Опять загадки условия: "Раз в день губернатор может вызвать на переписной пункт любую группу островитян и предложить им заполнить анкету." Может это надо понимать так, что "одну и ту же группу островитян" губернатор может вызвать только один раз в день. Но в течение дня может вызвать хоть тысячу отдельных групп? crazy
voliy # 19 ноября 2019 в 16:45 +5
Я не понимаю что смущает?)
Ну давайте так, чтобы ещё раз пояснить как образуются группы при первом анкетировании.
Пусть рыцарь 1. Он укажет, что лжецов -1000, т.е. 1+1000=1001 участник
Дальше лжецы. 1 лжец не может сказать что их 1000, т.к. это правда, он говорит что лжецов 999. Если 2 лжеца скажут 999, то будет- 2+999=1001 участник. А если 3 лжеца скажут 999, то будет 3+999=1002- из этой группы на второй день никого не возьмут. Ну и т.д.
Допустим, у нас есть
1+1000=1001
2+999=1001
3+999=1002
5+996=1001
20+700=720
ну и, чтобы покороче было-970+ 31=1001
Анкетируемых- 1+2+3+5+20+970=1001, закончились они)
Нам надо найти рыцаря, он ключ к разгадке. Поэтому на второй день отбираем по одному человеку из групп, где сумма 1001. Получаем 1+1+1+1=4 Среди них-1 рыцарь. Анкетируем, рыцарь называет число лжецов-3. По его анкете 1-го дня определяем число лжецов. И всёёёёёёё)))
Число групп не важно, важно что здесь только один говорит правду на второй день. crazy
Nif # 19 ноября 2019 в 19:44 +3
Как это "число групп не важно"? Если губернатор, согласно условию, только РАЗ В ДЕНЬ может вызвать на переписной пункт любую группу островитян и предложить им заполнить анкету? Не понимаю, если в первый день губернатор вызвал только ОДНУ группу, из каких "нескольких" групп он будет отбирать по одному человеку на второй день? shock
ШИКО # 19 ноября 2019 в 20:08 +4
Nif! В один день образовалось несколько групп. На второй день приглашается группа, в состав которой входят по одному представителю из образовавшихся в первый день групп. Не суть важно, сколько было групп, важно, что их представители в группу на следующий день вошли. По одному островитянину. 10 таких групп - значит 10 человек, 20 - значит 20. Из этих N человек единственный рыцарь легко находится. Вместе с ним находятся все рыцари, а методом исключения и все лжецы, как того требует условие.
Вроде у voliy всё просто. joke
Nif # 19 ноября 2019 в 21:28 +4
ШИКО! Это всё понятно. Но я упёрся в условие задачи: "Перепись будет проводиться следующим образом. Раз в день губернатор может вызвать на переписной пункт любую группу островитян и предложить им заполнить анкету". Что такое "Раз в день"? cry
ШИКО # 19 ноября 2019 в 22:01 +4
Я так, Nif, понимаю, что в любой день губернатор может пригласить любую группу. В другой день, чтоб не было наложений, - любую другую группу, часть, или полностью которая может состоять из уже вызванных ранее. Или вовсе новичков. И хоть весь рабочий день вызванной группе посвятить.
Честно если, ничего противоестественного не вижу в этой части вопроса. Не пойму, что здесь может вызывать вопросы. zst
Александр Борисенко # 20 ноября 2019 в 02:14 +3
Во второй день могут быть вызваны любые островитяне. Но губернатор вызывает только несколько человек, ориентируясь на полученные анкеты. Анкеты разложены на кучки, в каждой кучке одинаковые ответы. Вызывается один из каждой кучки, они-то и формируют группу для второго дня! laugh
Nif # 20 ноября 2019 в 06:13 +3
Понял. Разные понятия названы одним и тем же словом ГРУППА. Группа людей, вызванных губернатором, и группы виртуальных людей (по результатам анкетирования). sad
Александр Борисенко # 21 ноября 2019 в 02:49 +2


Это смотря как сгруппировать! laugh