Processing math: 100%

12-я Международная Жаутыковская олимпиада, 2016 год


В Графландии 60 городов, каждые два из которых соединены дорогой с односторонним движением. Докажите, что можно покрасить четыре города в красный цвет, а другие четыре — в зелёный так, чтобы каждая дорога, соединяющая красный город с зелёным, была направлена от красного к зелёному. ( А. Голованов )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Скажем, что город A обслуживает четвёрку городов B1, B2, B3, B4, если из него ведут дороги во все эти четыре города. Если всего из города выходит k дорог, то он обслуживает C4k четвёрок (мы считаем C4k=0 при k<4). Пусть количества дорог, выходящих из всех городов — k1, k2, , k60. Сумма этих количеств равна числу всех дорог C260=3059. Сумма количеств четвёрок, обслуживаемых всеми городами, равна S=C4k1+C4k2+C4k60. Докажем, что наименьшее значение этой суммы при условии k1+k2++k60=3059 равно 30C430+30C429. Действительно, множество наборов целых неотрицательных ki c суммой 3059 конечно, поэтому один из них доставляет наименьшее значение этой суммы. Предположим, что в этом наборе есть два числа m4 и n, для которых mn2. Тогда замена m и n на m1 и n+1 уменьшит нашу сумму (так как C4m+C4nC4m1C4n+1=C4m1C3n>0). Таким образом, наименьшее значение суммы S достигается для набора ki, никакие два из которых не отличаются более, чем на 1. Такой набор, очевидно, только один, и состоит из 30 чисел, равных 30 и 30 чисел, равных 29.
Итак, все 60 городов вместе обслуживают не менее 30C430+30C429 четвёрок. Но это число, как легко проверить, больше, чем 3C460, то есть утроенное количество всех четвёрок. Поэтому есть четвёрка, которую обслуживают хотя бы четыре города, что и требовалось доказать.

  0
2 года 1 месяца назад #

Пусть 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 -- в зеленый, так что каждая дорога, соединяющая красный город с зеленым, будет направлена от красного к зеленому. Это доказано.

  0
2 года 1 месяца назад #

Поздравляю с первым комментарием!