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