12-я Международная Жаутыковская олимпиада, 2016 год
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Скажем, что город A обслуживает четвёрку городов B1, B2, B3, B4, если из него ведут дороги во все эти четыре города. Если всего из города выходит k дорог, то он обслуживает C4k четвёрок (мы считаем C4k=0 при k<4). Пусть количества дорог, выходящих из всех городов — k1, k2, …, k60. Сумма этих количеств равна числу всех дорог C260=30⋅59. Сумма количеств четвёрок, обслуживаемых всеми городами, равна S=C4k1+C4k2+…C4k60. Докажем, что наименьшее значение этой суммы при условии k1+k2+…+k60=30⋅59 равно 30⋅C430+30⋅C429. Действительно, множество наборов целых неотрицательных ki c суммой 30⋅59 конечно, поэтому один из них доставляет наименьшее значение этой суммы. Предположим, что в этом наборе есть два числа m≥4 и n, для которых m−n≥2. Тогда замена m и n на m−1 и n+1 уменьшит нашу сумму (так как C4m+C4n−C4m−1−C4n+1=C4m−1−C3n>0). Таким образом, наименьшее значение суммы S достигается для набора ki, никакие два из которых не отличаются более, чем на 1. Такой набор, очевидно, только один, и состоит из 30 чисел, равных 30 и 30 чисел, равных 29.
Итак, все 60 городов вместе обслуживают не менее 30⋅C430+30⋅C429 четвёрок. Но это число, как легко проверить, больше, чем 3⋅C460, то есть утроенное количество всех четвёрок. Поэтому есть четвёрка, которую обслуживают хотя бы четыре города, что и требовалось доказать.
Пусть G -- это граф, состоящий из 60 городов, связанных дорогами с односторонним движением. Тогда каждое ребро (u,v) в G направлено от u к v. Построим новый граф G′, в котором ребра направлены в обратном направлении. Тогда в G′ каждое ребро (u,v) направлено от v к u.
Теперь разобьем города G на две части: S и T, где S состоит из 4 городов, а T -- из остальных 56. Тогда в графе G′ каждое ребро (u,v) из S в T указывает от v к u.
Таким образом, мы покрасим 4 города в красный цвет, а остальные 56 -- в зеленый, так что каждая дорога, соединяющая красный город с зеленым, будет направлена от красного к зеленому. Это доказано.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.