2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Комбинаторика на графах
Сообщение28.02.2021, 13:37 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение28.02.2021, 16:54 


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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение28.02.2021, 18:40 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Sender, спасибо!

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

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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение28.02.2021, 19:37 


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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение28.02.2021, 19:41 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение28.02.2021, 19:52 


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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение01.03.2021, 10:14 


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

 Профиль  
                  
 
 Re: Комбинаторика на графах
Сообщение01.03.2021, 12:00 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: epros, Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group