Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
В классе 9 человек, которые изучают некоторое количество предметов. Каждый предмет хорошо знают ровно три человека. Для участия в многопредметной олимпиаде хочется выбрать команду, в которой были бы знатоки всех предметов.
Ясно, что если количество предметов не превосходит 3, наименьшее число членов команды, которое можно гарантировать не зная распределения учеников по предметам, совпадает с числом предметов.
Постройте пример класса из 9 человек и некоторого количества предметов, для которого нельзя выбрать 3 человек, так, чтобы каждый предмет был известен хотя бы одному из них.
Объясните, почему Ваш пример удовлетворяет этому условию.
Чем меньше количество предметов, тем выше будет оценка.
Для построения примера используйте манипулятор "Графы". Вершины слева обозначают учеников, вершины справа - предметы. Вы можете добавлять новые вершины и проводить рёбра между старыми. При клике на вершину, она подсвечивается красным, а все смежные с ней - оранжевым.
Каждый ученик знает не более 4 предметов из 9. Команда из 2 учеников знает от 4 до 8 предметов. По 4 предмета знают только 2 ученика, их наборы предметов пересекаются (см. граф). Значит, команда из 2 учеников знает до 6 предметов. Достаточно сделать так, чтобы не было ученика, знающего одновременно три остальные предмета (которые не знают первые два), тогда команду из 3 человек сделать будет невозможно.