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