Question

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

Answer 1

Так как всего 27 учеников , а отличников больше половины, значит максимальное количество хулиганов может быть 13 (27=26+1=13*2+1). то есть , чтоб точно найти хоть одного отличника нужно спросить минимум 14 учеников.

Answer 2

Для того чтобы гарантированно вычислить хотя бы одного отличника, можно задать следующие вопросы:

1. Выберем произвольного ученика A и спросим его: "Ты отличник?"

   • Если он ответит "Да", то мы уже нашли хотя бы одного отличника.
   • Если он ответит "Нет", то переходим к следующему вопросу.

2. Выберем произвольного ученика B, который известно, что он отличник, и спросим его: "Ты хулиган?"

   • Если он ответит "Да", то он лжет (потому что все отличники всегда говорят правду), и значит, он является хулиганом. Тогда у нас уже есть один хулиган, и все остальные, кого мы расспрашивали до этого, являются отличниками.
   • Если он ответит "Нет", то он говорит правду (потому что все отличники всегда говорят правду), и значит, он действительно отличник. Тогда у нас уже есть хотя бы один отличник, и все остальные, кого мы расспрашивали до этого, также являются отличниками.

Таким образом, нам понадобятся максимум два вопроса, чтобы гарантированно вычислить хотя бы одного отличника.