Да разделим честните от лъжливите

[ql^2/8]

Задачка:
Попадаме на остров с 1025 аборигени. Те, разбира се са честни и лъжовни.
Трябва бързо да научим кои са честните и кои лъжците чрез провеждане
на интервюта. За всяко интервю можем да изберем колкото си искаме местни жители
и да зададем на всички един и същ въпрос който може да е един от двата:
- Колко са лъжливите туземци на това интервю?
- Колко са честните туземци на това интервю?
Всеки човек и неговия отговор автоматично се запаметява.

Какъв е най-малкият брой интервюта, с които можем да определим всеки от
туземците дали е от страната на правдата или на лъжата?

[klingonoid]

Едно интервю е достатъчно:
1. Събираме всичките накуп за едно интервю. От тях N ва брой са честни. Задаваме въпроса "Колко са честните ?"
Честните N на брой ще ни отговорят, че "честните са N на брой". Значи отделяме ги тия N на брой щото са честните, а всички останали са лъжливите, а освен това те задължително са казали нещо друго.

[ql^2/8]

Добре е за начало! Поне никой не може да бие предположението.

Събираме всички 1025. Питаме колко са честните?
10 от тях отговарят 10; 12 отговарят 12; 15 отговарят 15; 33 отговарят 33, 51 отговарят 15...
и т.н. Коя група е честната?

[jair]

Добре е за начало! Поне никой не може да бие предположението.

Събираме всички 1025. Питаме колко са честните?
10 от тях отговарят 10; 12 отговарят 12; 15 отговарят 15; 33 отговарят 33, 51 отговарят 15...
и т.н. Коя група е честната?

Второ интервю, при което взимаме по един човек от всички такив групи. Питаме колко са честните, този който отговори 1 е бил от честната група?

[ql^2/8]

Бързо се справихте! Браво, jair !

Бонус задача:

Довеждат ви 10 туземци на интервю. Задавате само на един от тях
един единствен въпрос. Той ви отговаря "не" и вие вече можете да
определите за всеки от групата дали е честен или лъжец.
Какъв е въпросът?

[Yasen6275]

Второ интервю, при което взимаме по един човек от всички такив групи. Питаме колко са честните, този който отговори 1 е бил от честната група?

А какво пречи на някой от лъжовните да отговори с 1?

[klingonoid]

А какво пречи на някой от лъжовните да отговори с 1?

Ако отговори с 1, това означава, че казва нещо вярно. Което пък означава че не е лъжец.

[Yasen6275]

А къде е казано че лъжците винаги трябва да лъжат?

[Bibi]

На втората задача: ако въпросът е "Има ли лъжци в групата", а отговорът е "не", всичко е ясно

[klingonoid]

Не съм съгласен:

Нека лъжеца е само един в групата. А пък ние питаме някой от тези казващи истината.
Какво ще ни отговори той на "има ли лъжци ?" ?
Ще ни отговори "НЕ".

Ако променим въпроса на "има ли лъжец ?", пак не се получава при отговор "НЕ" - може всички да са честни, но може и всички да са лъжци.

[Bibi]

Но... Тук търсим обратното, нали? Търсим въпроса, а не стратегията.

Иначе го казах на шега.
Също ми стана интересно следното: взимаме един туземец. Питаме го "ти лъжец ли си". А той вземе, че ни отговори "да" И кво праим сега?

[klingonoid]

Но... Тук търсим обратното, нали? Търсим въпроса, а не стратегията....

Точно така !
Казвам само, че въпроса "Има ли лъжци в групата" (заедно с "НЕ") не става за да определим какви са 10-мата.

[Bibi]

Прав си. Втори опит: "Вярно ли е, че ти си честен и в групата ви има поне още един честен?"
При "не", значи сме нацелили единствения честен в извадката.

[klingonoid]

Ако всички са лъжци и зададем този въпрос на един от тях, ще получим такъв отговор:

отрицание на ((отрицание на НЕ) и (отрицание на НЕ)) =
= отрицание на (ДА и ДА) = отрицание на ДА =
= НЕ

И тоя въпрос не става, сори.

[ql^2/8]

@klingonoid: Всъщност, при сложни въпроси трябва да сме наясно с логиката на лъжеца.
Неговата логика е: Намирам верният отговор - и казвам обратното.
Ако започне да обръща отговорите на всеки елемент, после на всяка логическа конструкция
и накрая на получения резултат - току виж казал истината!

@Bibi - Браво! Приемам отговора за верен!