Пока знаю только, что 44 - неверно не оптимально, можно лучше.В городе живут правдецы, лжецы и шизики. Правдецы всегда говорят правду, лжецы всегда лгут, тут все понятно.
А вот шизики... те отвечают как им вздумается. Могут сказать правду, а могут и солгать, в зависимости от фазы луны, положения секундной стрелки на циферблате, результата подброса монетки или еще каких-то никому, кроме шизика, неизвестных факторов.
Все жители знакомы и каждый знает о любом другом кем тот является.
Вы видите группу из 23 жителей города. Про группу в целом вам известно, что в ней только правдецы и шизики (лжецов нет) и что шизиков точно меньше половины. Члены группы согласны отвечать на ваши вопросы, но только те, что допускают ответ "да" либо "нет".
Задача: какое минимальное число вопросов необходимо задать членам группы (одному или нескольким - как угодно), чтобы наверняка определить хотя бы одного правдивца? Нужно показать алгоритм, но доказательство его оптимальности не требуется.
Примечание: вопросы, на которые житель не может ответить точно и однозначно - недопустимы.
Хотя шизик фактически генерирует случайный ответ да/нет на любой вопрос, он все таки должен знать, какой ответ будет правильным и какой неправильным, т.е. правило точности и однозначности распространяется и на шизиков.
Есть смутное подозрение, что правильный ответ - 23.
11 и меньше - пожалуй, нет. Просто потому, что может оказаться, что спрашиваем только шизиков.
