Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
В классе 9 человек, которые изучают некоторое количество предметов. Каждый предмет хорошо знают ровно три человека. Для участия в многопредметной олимпиаде хочется выбрать команду, в которой были бы знатоки всех предметов.
Ясно, что если количество предметов не превосходит 3, наименьшее число членов команды, которое можно гарантировать не зная распределения учеников по предметам, совпадает с числом предметов.
А для какого наименьшего количества предметов может не хватить 3 участников?
Пример оценивается в задаче Графы-1, его здесь приводить не требуется. Необходимо доказать, что для любого числа предметов, меньшего, чем в построенном примере, трёх участников будет достаточно. Оцениваться будет текст решения.
В задаче Графы-1 я использовал 2 предмета. Меньше 2-х только 1. Но если мы берем один предмет, то его по условию знают 3 человека. Значит, их и можно взять, и они будут знать все(1) предметы. Следовательно, такой вариант нам не подходит.