Комбинаторика на графах

[grizzly]

Пусть есть $C=1000$ различных цветов и $N=100$ разноцветных шаров. Каждый шар покрашен в (как минимум) $M=250$ различных цветов (из данного набора цветов). У любых $k=5$ шаров имеется хотя бы один общий цвет. Сколько всего найдётся (гарантированно) шаров, имеющих общий цвет?

Вряд ли возможен точный ответ, но, может, какие-то оценки / асимптотики / характер поведения ответа при различных параметрах $C,N,M,k$ -- хоть что-нибудь.

Интересуют подходы к таким задачам (ссылки на учебники / статьи или помощь в поиске). Что-то похожее попадалось в лекциях А.М. Райгородского, но именно такого я там не встретил или не узнал.

[Sender]

Может, попытаться воспользоваться принципом Дирихле, чтобы получить оценку? Число всевозможных групп из $k$ шаров равно, очевидно, $C_N^k$. Каждая такая группа по условию имеет хотя бы один общий цвет. Значит, среди имеющихся $C$ цветов найдётся хотя бы один, являющийся общим для не менее, чем $\frac{C_N^k}{C}$ групп из $k$ шаров. Пусть в этот цвет окрашены $L$ шаров, тогда, очевидно, справедливо $C_L^k \geqslant \frac{C_N^k}{C}$. Осталось подобрать минимальное $L$, удовлетворяющее этому условию, в данном случае это $27$.

[grizzly]

Sender, спасибо!

Действительно, таким простым способом уже получается хорошая оценка -- с ростом $N$ (при фиксации остальных параметров) ответ растёт очень близко к $N/4$ (можно оценить чуть точнее, но сейчас это не так важно). Но я хочу получить что-то ближе к $N/3$, нетривиально используя, если понадобится, более сильные ограничения на $M$ (количество цветов, в которые окрашен каждый шар). В граничных случаях очевидно, что $M$ влияет на ответ, но таким простым методом отследить это влияние вряд ли получится.

Я ещё подумаю и попытаюсь подобрать какой-то явный пример с небольшими параметрами, который можно было бы пощупать руками.

[lel0lel]

Что если самим попробовать раскрасить шары? Если каждую краску из $1000$ использовать ровно $25$ раз, то этого хватит чтобы раскрасить $100$ шаров в $250$ расцветок.

[grizzly]

lel0lel
Такая раскраска дала бы в ответе 25, что меньше доказанного выше 27. Следовательно, при такой раскраске нельзя выполнить условие "каждые 5 шаров имеют общий цвет".

[lel0lel]

grizzly
Условие про $5$ шаров почему-то воспринял как утверждение, которое при любой раскраске заведомо выполняется в силу неравенства $5\times 250>1000$. Так что пока не видно проблемы с $25$.

[Sender]

Стоп, разве можно из этого неравенства вывести нечто большее, чем "как минимум какие-то 2 из 5 любых шаров имеют общий цвет"? Это вроде как несколько слабее требуемого условия.

[lel0lel]

Да, я это условие именно так интерпретировал. Сейчас понял, что подразумевалось. Спасибо.