Всесиб 2024, 9 класс, задача 5
( баллов) Авиакомпания, в которой служат пилотов, эксплуатирует самолётов попарно различных типов. Каждый день для рейсов случайно выбирают из пилотов. Пилот может быть обучен пилотировать самолёты нескольких типов. Обучение одного пилота пилотированию самолёта одного типа стоит миллион рублей. Какую наименьшую сумму нужно потратить авиакомпании на обучение пилотов, чтобы каждый день каждый из выбранных пилотов мог пилотировать порученный ему самолёт? Пилот не может пилотировать более одного самолёта в день.
Ответ. миллионов рублей.
Решение. Приведём пример такого обучения на сумму миллионов рублей. Занумеруем пилотов числами от до , а самолёты числами от до . Обучим каждого из первых пилотов пилотированию ровно одного типа самолётов: -й пилот учится водить -й самолёт для каждого . Каждого из остальных пилотов обучим пилотировать все типы самолётов. В сумме это стоит миллионов рублей. Если в случайно выбранной девятке уникальных пилотов, то они смогут пилотировать самолётов, а остальные самолёта возьмут универсальные пилоты.
Докажем, что меньшей суммой компания обойтись не сможет. Каждый самолёт должны уметь пилотировать не меньше пяти пилотов. Иначе можно назначить пилотов, не умеющих водить этот самолёт, и в этот день данный самолёт вести будет некому. Значит, суммарное количество обучений на всех самолётах не меньше .
Доказано, что сумма обучения не меньше, чем миллионов рублей
Приведён пример требуемого в условии обучения за миллионов рублей
Доказана оценка и приведён пример