Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В классе 9 человек, которые изучают некоторое количество предметов. Каждый предмет хорошо знают ровно три человека. Для участия в многопредметной олимпиаде хочется выбрать команду, в которой были бы знатоки всех предметов.
Ясно, что если количество предметов не превосходит 3, наименьшее число членов команды, которое можно гарантировать не зная распределения учеников по предметам, совпадает с числом предметов.
Постройте пример класса из 9 человек и некоторого количества предметов, для которого нельзя выбрать 3 человек, так, чтобы каждый предмет был известен хотя бы одному из них.
Объясните, почему Ваш пример удовлетворяет этому условию.
Чем меньше количество предметов, тем выше будет оценка.
Для построения примера используйте манипулятор "Графы". Вершины слева обозначают учеников, вершины справа - предметы. Вы можете добавлять новые вершины и проводить рёбра между старыми. При клике на вершину, она подсвечивается красным, а все смежные с ней - оранжевым.
Пример. Первые 3 вершины соединены с группами вершин по 3 остальные соединенны ровно с одной вершиной из каждой группы. Если мы не берем первые 3 вершины, то мы никак не можем заполнить группы.(т.к. нужно 3 вершины чтобы заполнить ее => еще 3 школьника) Если же мы их берем мы не можем получить нижнюю вершину.(иначе не можем получить вершины из групп)