2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Графы
Сообщение29.06.2017, 13:47 


11/06/16
191
Здравствуйте, Уважаемые форумчане! Не очень понял задачу, помогите, пожалуйста, разобраться!

В заочной школе учится $204204$ ученика. При этом известно, что каждый ученик знаком ровно с $2828$ другими Чему равно количество таких различных учебных групп из трёх учеников,что в них либо все школьники знакомы друг с другом, либо все трое попарно незнакомы?

Я так понимаю, что здесь наверняка нужно будет использовать тот факт, что среди любых 6 людей найдутся либо 3 знакомых, либо трое незнакомых. Пытался к этому подвести. но не получилось. Можно, конечно взять просто разбить на группы по 6 человек всех учеников, получится $\dfrac{204204}{6}$ учеников в каждой группе. Это я так понимаю, что получится оценка снизу для количества таких групп. Но здесь не учитывалось число 2828, как его учитывать -- пока что не очевидно. Что-то мне подсказывает, что это число как раз позволит получить оценку сверху, но пока что не ясно -- как именно.

 Профиль  
                  
 
 Re: Графы
Сообщение29.06.2017, 21:12 
Заслуженный участник


23/07/08
10626
Crna Gora
Я не знаю, как решить эту задачу. Но я знаю, как найти верный ответ. :-)

Нарисуем (для красоты правильный) $204204$-угольник. В каждой вершине поставим школьника. Пусть каждый школьник знаком с теми, кто отстоит от него не более чем на $1414$ шагов (сторона — шаг) по или против часовой стрелки.
Раз отношение знакомства задано явно, нетрудно посчитать то, что нужно. Проблема в том, чтобы доказать, что в общем случае получится то же.

 Профиль  
                  
 
 Re: Графы
Сообщение30.06.2017, 19:57 


11/06/16
191
Извиняюсь, верная формулировка условия такая:

В заочной школе учится $204$ ученика. При этом известно, что каждый ученик знаком ровно с $28$ другими Чему равно количество таких различных учебных групп из трёх учеников,что в них либо все школьники знакомы друг с другом, либо все трое попарно незнакомы?

-- 30.06.2017, 20:00 --

svv в сообщении #1230578 писал(а):
Я не знаю, как решить эту задачу. Но я знаю, как найти верный ответ. :-)

Нарисуем (для красоты правильный) $204204$-угольник. В каждой вершине поставим школьника. Пусть каждый школьник знаком с теми, кто отстоит от него не более чем на $1414$ шагов (сторона — шаг) по или против часовой стрелки.
Раз отношение знакомства задано явно, нетрудно посчитать то, что нужно. Проблема в том, чтобы доказать, что в общем случае получится то же.


Идею я понял, кажется, получается в такой ситуации всех можно разбить на тройки знакомых, то есть исходное количество учеников нужно поделить на 3?

 Профиль  
                  
 
 Re: Графы
Сообщение01.07.2017, 01:32 
Заслуженный участник


23/07/08
10626
Crna Gora
Всех троек очень много — это число сочетаний из $204$ по $3$:
$\dbinom{204}{3}=\dfrac{204!}{201!\cdot 3!}=1394204$
Нет, нужные числа посчитать хоть и не очень сложно, но всё-таки не настолько просто, как в Вашем варианте. :-)

И потом, хочу напомнить, что моё решение нечестное — оно использует конкретную структуру графа (чего мне никто не разрешал делать). Я основываюсь на том недоказанном допущении, что ответ к задаче не зависит от этой структуры, если только соблюдены условия.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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