Областная олимпиада по математике, 2003 год, 11 класс

На международной конференции официальными являются четыре языка, причем любые два участника конференции могут разговаривать хотя бы на одном общем официальном языке. Докажите, что среди официальных языков найдется хотя бы один, на котором разговаривают не менее $60\%$ всех участников конференции.

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

Обозначим эти языки как $(1, 2, 3, 4)$ и $N$ — общее количество участников. Рассмотри несколько случаев:

Если в этой конференции все участники знают только по одному языку, в таком случае это должен быть один единственный язык (например язык $1$), иначе будет противоречия с условием, следовательно в этом случае будет $100\%$ знание этого языка.

Если участники знают только по $2$ языка, тогда каждый участник без огр общ должен знать языки в таком виде: $(1, 2)$, $(1, 3)$, $(2, 3)$ назовем треугольный вид или $(1, 2)$, $(1, 3)$, $(1, 4)$ назовем его звезда.

Если это треугольный вид, то в виду его построения, языки $1, 2, 3$ в сумме будут знать $2N$ человек, значит в среднем кол-во носителей на один язык $\dfrac{2N}{3} > 0.6N$ по принципу Дирихле, найдется язык которые знают больше $60\%$

Если это звездный вид, тогда это будет один общий язык для всех, в данном случае это язык $1$

Если все знают только по три языка, здесь подходит все сочетания языков: $(1, 2, 3)$, $(1, 2, 4)$, $(1, 3, 4)$, $(2, 3, 4)$ как видим эти языки пересекаются как минимум по $2$-ум языкам, а любые три из них по одному языку, значит если присутствуют все эти $4$ вида языка тогда в сумме участники будут знать $3N$ языков, тогда в среднем количество носителей на один язык $\dfrac{3N}{4} > 0.6N$ по тому же принципу найдется язык которые знают больше $60\%$, если же не все языки присутствуют, тогда $100\%$ можно выбрать один из присутствующих, это обеспечивается тем что сочетания любых $3$ видов сочетаний, пересекаются по одному языку

Ситуация когда кто то знает $1$ язык, а другие два и более , возможно тогда когда этот один язык имеется у всех, иначе противоречие, тогда $100\%$ можно выбрать его.

Ситуация когда кто-то из участников знает $2$ и $3$ языка: предположим что не нашлось языка на котором говорят $60\%$, то есть каждый язык знают $< 0.6N$ тогда верхняя граница всех языков равна $3 \cdot 0.6N = 1.8N$

в таком случае каждый участник который знает язык в треугольном виде и трёхязычник, увеличивает количество каждого языка на $2$ в общей сумме то есть нижняя оценку для языков $2N$ что противоречит верхней, значит такой язык найдетсяЕсли же двуязычные расположены в виде звезды, если таких двуязычных больше $60\%$ то выберем язык $1$, если меньше тогда с одной стороны максимальное количество языков $4 \cdot 0.6N = 2.4N$ с другой по факту $2 \cdot 0.6N + 3(N - 0.6N) = 2.4N + 1$ значит такой язык найдется