Question

В съезде юных писателей участвовали 22 школьника. После съезда каждый из них прочитал произведения трѐх юных писателей, побывавших на съезде. Докажите, что из делегатов съезда можно составить комиссию из четырѐх человек такую, в которой ни один из членов комиссии не читал произведения остальных еѐ членов.

Answer 1

Приведем алгоритм, позволяющий выбрать 4 подходящих школьников. Рассмотрим произвольного школьника A. По условию, ровно три других школьника читали его произведения. Удалим их из рассмотрения и выберем из 22-1-3=18 оставшихся школьников произвольного школьника B. Ясно, что A и B не читали произведения друг друга. Среди оставшихся 17 школьников у B есть не более трех его читателей (они могут совпадать с читателями A). Удалив их, выберем любого из 14 оставшихся школьников, назовем его C. Понятно, что A,B,C не читали работы друг друга. Среди 13 оставшихся школьников есть не более 3 читателей C, удалим их и выберем среди 10 оставшихся школьника D. Тогда из школьников A,B,C и D можно составить комиссию.