Заполните пропуски так, чтобы получилось правильное решение. Задача. В классе 14 человек. В каждый из 62 учебных осенних дней какие-то четверо из них назначались дежурными.…
Заполните пропуски так, чтобы получилось правильное решение. Задача. В классе 14 человек. В каждый из 62 учебных осенних дней какие-то четверо из них назначались дежурными. Докажите, что какие-то двое ребят дежурили вместе хотя бы 5 раз. Решение. Предположим, утверждение задачи неверно. Посчитаем двумя способами, сколько всего на протяжении осени было пар ребят, дежурящих вместе (каждые двое ребят могли дежурить вместе несколько раз). Каждый день дежурили четверо, и пар дежурств в этот день было ровно 6 . Значит, за 62 дня пар дежурящих вместе ребят было ровно 62⋅ 6 = 372 . С другой стороны, всего различных пар ребят в компании из 14 человек ровно 91 . Если никакая пара не дежурила вместе хотя бы 5 раз, то каждая пара ребят дежурила вместе не более 4 раз. Тогда суммарно пар дежурящих вместе ребят было не более 4⋅ 3 = . Но ранее мы выяснили, что их ровно , противоречие. Значит, какие-то двое ребят дежурили вместе хотя бы 5 раз.
Задача решается методом двойной подсчёта (счёт одной величины двумя способами).
Цель: доказать, что найдётся пара учащихся, которые дежурили вместе как минимум 5 раз.
- Подсчёт общих пар за весь осенний период
- Каждый день дежурят 4 человека. Среди них есть C(4,2) = 6 пар.
- Всего дней 62, значит всего пар-дружбы, посчитанных по дням, будет 62 · 6 = 372.
- Количество возможных пар учащихся
- В классе 14 человек, число различных неупорядоченных пар: C(14,2) = 91.
- Противоречие предположению “никакая пара не дежурила вместе не менее 5 раз”
- Пусть никакая пара не дежурила вместе хотя бы 5 раз, значит каждая пара встречалась вместе не более чем 4 раза.
- Тогда на все 91 пары приходилось бы не более 91 · 4 = 364 пар-дружбы.
- Придуманный вывод
- Мы получили 372 пар-дружбы, но по предположению максимум могло быть только 364.
- 372 > 364, значит противоречие. Следовательно, существует пара учащихся, которая дежурила вместе хотя бы 5 раз.
Дополнительная заметка (более общая форма):
- Общее правило: если D дней по m дежурных в день, то суммарное число «позиций пары» равно D · C(m,2).
- Всего пар среди n человек: C(n,2).
- Тогда по принципу средних значений или по неравенству, если D·C(m,2) > C(n,2)·(t−1), то найдётся пара, которая дежурила вместе не менее t раз.
- В данной задаче D=62, m=4, n=14, t=5: 62·C(4,2)=62·6=372, C(14,2)=91, и 372 > 91·4=364, значит существует пара с количеством совместных дежурств не менее 5.
