Олимпиада Туймаада по математике. Младшая лига. 2017 год

В стране любые два города соединены либо прямым автобусным, либо прямым авиасообщением. Клика — это набор городов, попарно соединенных авиарейсами. Клюка — это набор городов, попарно соединенных прямыми авиарейсами, и при этом таких, что из них выходит поровну автобусных рейсов. Кляка — это набор городов, попарно соединенных прямыми авиарейсами, и при этом таких, что из любых двух из них выходит разное число автобусных рейсов. Докажите, что размер любой клики не превосходит произведения размеров максимальной (по количеству городов) клюки и максимальной кляки. ( Y. Caro, P. Borg )

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

Пусть $C=\{ c_1,c_2,...,c_l\}$ — множество городов в наибольшей клике.

Рассмотрим мультимножество $S$, состоящее из количества городов, соединенных с городом $c_i$ автобусным маршрутом для каждого $i=1,2,...,l$.

Предположим, $S=\{ n_1\times b_1,n_2\times b_2,...,n_k\times b_k\}$ где $n_1,n_2,...,n_k\in \mathbb{Z}^+$

Понятно, что мы можем выбрать $k$ городов из $C$, чтобы создать клаку, и мы можем выбрать $\max_{i=1}^{k} \{ n_i\}$ городов в $C$, чтобы создать клаку.

Итак, мы хотим доказать, что $k\times \max_{i=1}^{k} \{ n_i\} \geq l$, что верно, поскольку $LHS\geq n_1+n_2+...+n_k=l$.