Математикадан «Туймаада» олимпиадасы. Кіші лига. 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$.