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

Предмет вопроса: Принцип Дирихле и Инъективное отображение

Разъяснение: Чтобы решить данную задачу, мы можем использовать принцип Дирихле. Принцип Дирихле утверждает следующее: если на $n + 1$ объектов приходится $n$ мест, то хотя бы на двух объектах приходится одно место.

Предположим, что взвод состоит из 101 человека, у каждого из которых есть свой дежурный день. Количество дежурных дней равно 100. Рассмотрим множество дежурных дней от 1 до 100. Если разделить количество дней на количество людей взвода (100 дней / 101 человек), получим дробное число, что означает, что как минимум один из дежурных дней должен быть общим для двух человек.

Другими словами, существуют два человека во взводе, которые были на дежурстве одновременно в течение не менее 100 дней.

Например:

Условие: Взвод состоит из 101 человека, каждый из которых был на дежурстве в течение 100 дней. Докажите, что в какие-то два дня хотя бы два человека из взвода были на дежурстве одновременно.

Доказательство: По принципу Дирихле, если количество объектов (дежурных дней) больше количества мест (людей взвода), то хотя бы на двух объектах (дней) приходится одно место (двум людям). В данном случае, количество дней (100) больше количества людей взвода (101), поэтому существуют как минимум два человека, которые были на дежурстве одновременно в течение не менее 100 дней.

Совет: Для лучшего понимания данной задачи, можно представить взвод как студентов в классе, каждый из которых назначен на дежурство в течение 100 дней. Мы ищем момент, когда хотя бы два студента были на дежурстве одновременно. Принцип Дирихле полезно применить в таких задачах, где нужно найти "повторение" или "совпадение" среди объектов, таких как дни в нашем примере.

Практика: В классе 30 студентов. Каждый из них получил разные оценки от 1 до 100. Докажите, что как минимум два студента получили одинаковую оценку.