Задание №177328: Турнир городов

6. Два дворца спорта набрали школьников в секции. В каждой секции первого дворца не меньше,
чем по n детей, а в каждой секции второго — не меньше, чем по k детей. Оказалось, что каждый
школьник посещает столько же секций в первом дворце, сколько и во втором. Кроме того, в любых
двух секциях из разных дворцов есть не более одного общего школьника. Докажите, что в первый
дворец попало не меньше nk детей.
Н. Верещагин, А. Ромащенко

Решение. Пусть в первом дворце a секций, а во втором — b секций. Пусть общее количество
задействованных школьников равно s, и i-й школьник участвует в d секций первого дворца (и d
i i
секций второго). Тогда есть d2 пар секций из разных дворцов таких, что i-й школьник ходит в обе
i
секции пары. Поскольку в каждой из ab пар секций из разных дворцов не более одного общего
школьника, получаем
s
(cid:32)
s
(cid:33)2
(cid:88) 1 (cid:88)
ab ≥ d2 ≥ d .
i s i
i=1 i=1
Просуммируем теперь количества школьников во всех секциях первого дворца, а также количества
s
(cid:80)
школьников во всех секциях второго дворца; в обоих случаях получится d . С другой стороны, в
i
i=1
первом случае получается не меньше, чем an, а во втором — не меньше, чем bk. Значит,
(cid:32)
s
(cid:33)2
1 (cid:88) an · bk
ab ≥ d ≥ .
i
s s
i=1
Сокращая на ab, получаем s ≥ nk, что и требовалось.









3