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