Форум Привет

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

Вы видите группу из 23 жителей города. Про группу в целом вам известно, что в ней только правдецы и шизики (лжецов нет) и что шизиков точно меньше половины. Члены группы согласны отвечать на ваши вопросы, но только те, что допускают ответ "да" либо "нет".

Задача: какое минимальное число вопросов необходимо задать членам группы (одному или нескольким - как угодно), чтобы наверняка определить хотя бы одного правдивца? Нужно показать алгоритм, но доказательство его оптимальности не требуется.

Примечание: вопросы, на которые житель не может ответить точно и однозначно - недопустимы.
Хотя шизик фактически генерирует случайный ответ да/нет на любой вопрос, он все таки должен знать, какой ответ будет правильным и какой неправильным, т.е. правило точности и однозначности распространяется и на шизиков.

perkins писал(а): ↑Пт июл 24, 2026 6:18 pm зачем в условии задачи есть лжецы, если им вопросы задавать нельзя? Задающий вопрос знает правильность ответа или нет?

perkins писал(а): ↑Пт июл 24, 2026 6:52 pm интуитивно, не зная вероятности выдачи правильного ответа шизиком, задача не имеет решения, не понятно как отличать шизика от правдеца если формально шизик может выдавать правильный ответ всегда

assassello писал(а): ↑Пт июл 24, 2026 6:58 pm

perkins писал(а): ↑Пт июл 24, 2026 6:52 pm интуитивно, не зная вероятности выдачи правильного ответа шизиком, задача не имеет решения, не понятно как отличать шизика от правдеца если формально шизик может выдавать правильный ответ всегда

Задача точно решается за 44 вопроса, это очень простой алгоритм, не зависящий ни от каких вероятностей.

perkins писал(а): ↑Пт июл 24, 2026 7:02 pm вопрос как отличить шизика от правдеца если шизики отвечают на первые например 100 вопросов правильно?

assassello писал(а): ↑Пт июл 24, 2026 7:08 pm

perkins писал(а): ↑Пт июл 24, 2026 7:02 pm вопрос как отличить шизика от правдеца если шизики отвечают на первые например 100 вопросов правильно?

Упрости задачу. Представь, что их не 23, а только 3. И шизиков среди них не больше одного.

assassello писал(а): ↑Пт июл 24, 2026 7:08 pm

perkins писал(а): ↑Пт июл 24, 2026 7:02 pm вопрос как отличить шизика от правдеца если шизики отвечают на первые например 100 вопросов правильно?

Упрости задачу. Представь, что их не 23, а только 3. И шизиков среди них не больше одного.

Lisa писал(а): ↑Пт июл 24, 2026 7:32 pm

assassello писал(а): ↑Пт июл 24, 2026 7:08 pm
Упрости задачу. Представь, что их не 23, а только 3. И шизиков среди них не больше одного.

Из 3х решается за один вопрос по-моему.

Буратино писал(а): ↑Пт июл 24, 2026 7:55 pm

Lisa писал(а): ↑Пт июл 24, 2026 7:32 pm
Из 3х решается за один вопрос по-моему.

За два вопроса.

Lisa писал(а): ↑Пт июл 24, 2026 7:59 pm

Буратино писал(а): ↑Пт июл 24, 2026 7:55 pm

За два вопроса.

Я вижу за один. Второй вопрос нужен чтобы определить шизика, но это не требуется в условии.

Lisa писал(а): ↑Пт июл 24, 2026 8:04 pm Писать или тут пока интригу держат?