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