Страница 56 номер 70, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
В чемпионате города по футболу участвует 12 команд. Чемпионат проводится в один круг. Докажите, что в любой момент проведения чемпионата всегда найдутся хотя бы две команды, сыгравшие одинаковое число матчей.
Вершины — 12 команд, ребро соединяет команды, уже сыгравшие между собой. Круг один, поэтому кратных рёбер нет и граф простой, а степень вершины равна числу матчей команды.
В простом графе с 12 вершинами каждая вершина соединена не более чем с \(12 - 1 = 11\) остальными, а меньше всего рёбер у изолированной: степень — одно из 12 чисел \(0;\ 1;\ 2;\ \ldots;\ 11\).
Пусть все 12 команд сыграли разное число матчей. Тогда 12 попарно различных степеней исчерпывают все 12 значений, в том числе 0 и 11. Но вершина степени 11 соединена со всеми остальными, в том числе с вершиной степени 0, у которой рёбер нет вовсе. Противоречие.
Значит, хотя бы у двух вершин степени совпадают, то есть хотя бы две команды сыграли одинаковое число матчей. Рассуждение не опиралось на то, сколько матчей уже прошло, поэтому оно верно в любой момент чемпионата.
Ответ: в любой момент чемпионата хотя бы две команды сыграли одинаковое число матчей: иначе 12 команд имели бы все 12 различных значений от 0 до 11, а команда, сыгравшая со всеми одиннадцатью соперниками, и команда, не сыгравшая ни одного матча, существовать одновременно не могут.
В чемпионате города по футболу участвует 12 команд. Чемпионат проводится в один круг. Докажите, что в любой момент проведения чемпионата всегда найдутся хотя бы две команды, сыгравшие одинаковое число матчей.
Сопоставим каждой из 12 команд вершину графа; ребро соединяет две команды, если они уже сыграли между собой. Чемпионат проводится в один круг, поэтому каждые две команды играют друг с другом не более одного раза: кратных рёбер нет, и граф простой. Степень вершины равна числу матчей, сыгранных этой командой.
В простом графе с 12 вершинами каждая вершина соединена не более чем с \(12 - 1 = 11\) остальными, а меньше всего рёбер у изолированной вершины. Значит, степень каждой вершины — одно из 12 чисел: \(0;\ 1;\ 2;\ \ldots;\ 11\).
Предположим, что все 12 команд сыграли разное число матчей. Тогда 12 степеней попарно различны, а возможных значений тоже ровно 12, поэтому встретится каждое значение — в том числе и 0, и 11.
Но вершина степени 11 соединена со всеми остальными вершинами, в том числе с той, у которой степень 0, — а у вершины степени 0 рёбер нет вовсе. Получилось противоречие.
Значит, предположение неверно: хотя бы у двух вершин степени совпадают, то есть хотя бы две команды сыграли одинаковое число матчей. Рассуждение не опиралось на то, сколько матчей уже прошло, поэтому оно верно в любой момент чемпионата.
Ответ: в любой момент чемпионата хотя бы две команды сыграли одинаковое число матчей: иначе 12 команд имели бы все 12 различных значений от 0 до 11, а команда, сыгравшая со всеми одиннадцатью соперниками, и команда, не сыгравшая ни одного матча, существовать одновременно не могут.
