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