Дано:
В классе 30 учеников, у каждого ровно по 2 друга.
Найти:
Можно ли организовать не менее 10 дежурств так, чтобы каждый раз дежурили двое друзей и при этом никто не дежурил дважды? Всегда ли можно организовать 11 дежурств?
Решение:
1. Условие задачи подразумевает, что ученики образуют граф, где каждая вершина (ученик) соединена с двумя другими вершинами (друзьями).
2. В этом графе 30 вершин и каждое ребро соединяет двоих друзей.
3. Общее количество рёбер в графе можно найти следующим образом:
- Каждый из 30 учеников имеет 2 друга.
- Это приводит к 30 * 2 = 60 "дружеским" связям.
- Однако каждое ребро учитывается дважды (дружба является симметричной), поэтому общее количество рёбер:
E = 60 / 2 = 30.
4. Дежурства можно организовать, выбирая пары друзей. Количество пар, которые можно выбрать из 30 учеников:
C(30, 2) = 30 * 29 / 2 = 435.
5. Теперь нужно проверить, сколько уникальных дежурств можно организовать. Каждый дежурный состав включает двух друзей, следовательно, если мы используем каждое ребро один раз, то можно провести 30 дежурств.
6. Для 10 дежурств это возможно, так как 10 ≤ 30.
7. Проверим возможность организации 11 дежурств. Учитывая, что у каждого ученика есть ровно 2 друга, при 11 дежурствах:
- Пары дежурных (учеников) могут пересекаться, и может возникнуть ситуация, когда один из друзей дежурил дважды.
8. На практике, с учётом структуры графа, в общем случае нельзя гарантировать, что 11 дежурств возможно без повторения, так как количество доступных рёбер (дружеских пар) ограничено.
Ответ:
Можно организовать не менее 10 дежурств, но не всегда возможно организовать 11 дежурств.