В классе есть 35 учеников. Каждый ученик пропускает не более 33 уроков математики в год из 100. В течение учебного года
В классе есть 35 учеников. Каждый ученик пропускает не более 33 уроков математики в год из 100. В течение учебного года можно выбрать 3 урока, на которых каждый из учеников присутствовал как минимум на одном из них. Как это можно доказать?
Murchik 55
Чтобы показать, что в течение учебного года можно выбрать 3 урока, на которых каждый из 35 учеников присутствовал как минимум на одном из них, воспользуемся принципом Дирихле.Допустим, каждый ученик пропустил по k уроков математики в год. Тогда общее количество пропущенных уроков равно 35 * k. В нашем случае, каждый ученик пропускает не более 33 уроков из 100, поэтому имеем: k <= 33.
Теперь представим собой 3 урока, на которые мы хотим, чтобы каждый ученик присутствовал как минимум на одном из них. Представим эти уроки в виде трех контейнеров.
Разделим 35 учеников на эти 3 контейнера следующим образом: $\lceil \frac{35}{3} \rceil = 12$ учеников в первом контейнере, $\lceil \frac{35}{3} \rceil = 12$ учеников во втором контейнере и $35 - 12 - 12 = 11$ учеников в третьем контейнере.
Согласно принципу Дирихле, если количество объектов (учеников) больше, чем количество контейнеров (уроков), то хотя бы один контейнер будет содержать больше одного объекта. В нашем случае, в каждом из контейнеров будет хотя бы 2 ученика.
Это означает, что выбирая 3 урока из года с 100 уроками, каждый из 35 учеников будет присутствовать на хотя бы одном из этих 3 уроков. Таким образом, задача доказана.