Question

У короля 10 министров. Однажды он получил шифрованную записку от своего шпиона с известием: «Ваше величество! Мне удалось установить, что: Среди Ваших министров не менее одного честного. Среди любой пары наугад выбранных министров не более одного честного». Король надолго задумался. Сколько честных министров у короля?

Answer 1

1 честный,если бы было больше, то в паре могло бы оказаться двое честных

Answer 2

Все министры честные потому, что если взять любую пару министров, то любой из министров может оказаться в этой паре. Значит, честных министров 10.

Answer 3

Предположим, что среди министров нет ни одного честного. Тогда любые два министра будут недоброжелательно настроены друг к другу, и шпион бы не мог установить, что среди любой пары министров не более одного честного. Следовательно, среди министров должен быть хотя бы один честный.

Предположим, что среди министров ровно один честный. Тогда все остальные девять министров недоброжелательно настроены к честному министру, и каждый из них будет недоброжелательно настроен к любому другому недоброжелательно настроенному министру. Но тогда шпион не мог бы установить, что среди любой пары наугад выбранных министров не более одного честного. Следовательно, среди министров должно быть не менее двух честных.

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

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

Таким образом, среди министров должно быть ровно два честных министра.