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