Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В классе 9 человек, которые изучают некоторое количество предметов. Каждый предмет хорошо знают ровно три человека. Для участия в многопредметной олимпиаде хочется выбрать команду, в которой были бы знатоки всех предметов.
Ясно, что если количество предметов не превосходит 3, наименьшее число членов команды, которое можно гарантировать не зная распределения учеников по предметам, совпадает с числом предметов.
А для какого наименьшего количества предметов может не хватить 3 участников?
Пример оценивается в задаче Графы-1, его здесь приводить не требуется. Необходимо доказать, что для любого числа предметов, меньшего, чем в построенном примере, трёх участников будет достаточно. Оцениваться будет текст решения.
1.Так как каждый предмет хорошо знает ровно 3 человека то для каждого предмета найдется хотя бы один человек знающий его хорошо,следовательно необходимое и достаточное кол-во участников не будет превышать числа предметов 2.Пусть наименьшее необходимое число предметов-n,тогда имеем граф в котором N+9 вершин и 3n ребер