Да разделим честните от лъжливите
Задачка:
Попадаме на остров с 1025 аборигени. Те, разбира се са честни и лъжовни.
Трябва бързо да научим кои са честните и кои лъжците чрез провеждане
на интервюта. За всяко интервю можем да изберем колкото си искаме местни жители
и да зададем на всички един и същ въпрос който може да е един от двата:
- Колко са лъжливите туземци на това интервю?
- Колко са честните туземци на това интервю?
Всеки човек и неговия отговор автоматично се запаметява.
Какъв е най-малкият брой интервюта, с които можем да определим всеки от
туземците дали е от страната на правдата или на лъжата?
Отговор: Да разделим честните от лъжливите
Едно интервю е достатъчно:
1. Събираме всичките накуп за едно интервю. От тях N ва брой са честни. Задаваме въпроса "Колко са честните ?"
Честните N на брой ще ни отговорят, че "честните са N на брой". Значи отделяме ги тия N на брой щото са честните, а всички останали са лъжливите, а освен това те задължително са казали нещо друго.
Отговор: Да разделим честните от лъжливите
Добре е за начало! Поне никой не може да бие предположението.
Събираме всички 1025. Питаме колко са честните?
10 от тях отговарят 10; 12 отговарят 12; 15 отговарят 15; 33 отговарят 33, 51 отговарят 15...
и т.н. Коя група е честната?
Отговор: Да разделим честните от лъжливите
Цитат:
Първоначално публикувано от
ql^2/8 Добре е за начало! Поне никой не може да бие предположението.
Събираме всички 1025. Питаме колко са честните?
10 от тях отговарят 10; 12 отговарят 12; 15 отговарят 15; 33 отговарят 33, 51 отговарят 15...
и т.н. Коя група е честната?
Второ интервю, при което взимаме по един човек от всички такив групи. Питаме колко са честните, този който отговори 1 е бил от честната група?
Отговор: Да разделим честните от лъжливите
Бързо се справихте! Браво, jair !
Бонус задача:
Довеждат ви 10 туземци на интервю. Задавате само на един от тях
един единствен въпрос. Той ви отговаря "не" и вие вече можете да
определите за всеки от групата дали е честен или лъжец.
Какъв е въпросът?
Отговор: Да разделим честните от лъжливите
Цитат:
Първоначално публикувано от
jair Второ интервю, при което взимаме по един човек от всички такив групи. Питаме колко са честните, този който отговори 1 е бил от честната група?
А какво пречи на някой от лъжовните да отговори с 1?
Отговор: Да разделим честните от лъжливите
Цитат:
Първоначално публикувано от
Yasen6275 А какво пречи на някой от лъжовните да отговори с 1?
Ако отговори с 1, това означава, че казва нещо вярно. Което пък означава че не е лъжец.
Отговор: Да разделим честните от лъжливите
А къде е казано че лъжците винаги трябва да лъжат?
Отговор: Да разделим честните от лъжливите
На втората задача: ако въпросът е "Има ли лъжци в групата", а отговорът е "не", всичко е ясно :BigGrin
Отговор: Да разделим честните от лъжливите
Не съм съгласен:
Нека лъжеца е само един в групата. А пък ние питаме някой от тези казващи истината.
Какво ще ни отговори той на "има ли лъжци ?" ?
Ще ни отговори "НЕ".
Ако променим въпроса на "има ли лъжец ?", пак не се получава при отговор "НЕ" - може всички да са честни, но може и всички да са лъжци.
Отговор: Да разделим честните от лъжливите
Но... Тук търсим обратното, нали? Търсим въпроса, а не стратегията.
Иначе го казах на шега.
Също ми стана интересно следното: взимаме един туземец. Питаме го "ти лъжец ли си". А той вземе, че ни отговори "да" :) И кво праим сега?
Отговор: Да разделим честните от лъжливите
Цитат:
Първоначално публикувано от
Bibi Но... Тук търсим обратното, нали? Търсим въпроса, а не стратегията....
Точно така !
Казвам само, че въпроса "Има ли лъжци в групата" (заедно с "НЕ") не става за да определим какви са 10-мата.
Отговор: Да разделим честните от лъжливите
Прав си. Втори опит: "Вярно ли е, че ти си честен и в групата ви има поне още един честен?"
При "не", значи сме нацелили единствения честен в извадката.
Отговор: Да разделим честните от лъжливите
Ако всички са лъжци и зададем този въпрос на един от тях, ще получим такъв отговор:
отрицание на ((отрицание на НЕ) и (отрицание на НЕ)) =
= отрицание на (ДА и ДА) = отрицание на ДА =
= НЕ
И тоя въпрос не става, сори.
Отговор: Да разделим честните от лъжливите
@klingonoid: Всъщност, при сложни въпроси трябва да сме наясно с логиката на лъжеца.
Неговата логика е: Намирам верният отговор - и казвам обратното.
Ако започне да обръща отговорите на всеки елемент, после на всяка логическа конструкция
и накрая на получения резултат - току виж казал истината!
@Bibi - Браво! Приемам отговора за верен!