Физтех 2026, отборочный этап, 9 класс, второй тур, задача 10
Двести школьников собирают наклейки, среди которых есть наклейки редких видов. Оказалось, что у каждого школьника есть наклейки ровно двух редких видов, и для каждого редкого вида наклеек найдётся школьник, у которого есть наклейка такого вида. Также известно, что каких бы школьников ни взять, найдётся редкий вид наклеек такой, что его нет ни у кого из этих школьников. При каком наименьшем количестве редких видов наклеек такая ситуация возможна?
Ответ
Ответ. .
Решение. Пусть редких видов не более . Выберем любого школьника. Пусть у него есть наклейки и редких видов. Теперь можно выбрать школьника, у которого есть наклейки вида, затем школьника, у которого есть наклейки вида и т. д. Всего мы выберем не более школьников (некоторые из выбранных школьников могли совпасть). Дополнив их, если нужно, до группы из человек, получим, что для этой группы нет редкого вида, которого нет ни у кого из этих школьников. Противоречие.
Покажем, что для редких типов такая ситуация возможна. Пусть у каждого школьника есть наклейка -го типа и наклейка какого-то из первых типов (при этом наклейка каждого из первых типов есть у какого-то школьника). Тогда у любой группы из школьников есть наклейки не более из первых редких типов, поэтому у них какой-то редкий тип точно отсутствует.