2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 2016 участников
Сообщение17.07.2017, 11:48 
Аватара пользователя


21/06/08
476
Томск
В конференции всего есть 2016 участников. Если А знаком с Б, и Б знаком с С то С не знаком с А. Какое максимальное отношение знакомства может существовать в конференции?

 Профиль  
                  
 
 Re: 2016 участников
Сообщение17.07.2017, 12:20 


08/05/08
593
$1008^2$ знакомств, если я правильно условие понял
Достигнуть понятно как, а что не больше, можно доказать по индукции с шагом от $2n$ -> $2n+2$ примерно такими рассуждениями:
возьмем два новых человека. Один знаком с $a$ человеками, другой знаком с $b$ При том $a+b \leqslant 2n$ а следовательно каждые новые 2 человека дают не более $2n+1$ новых знакомств

 Профиль  
                  
 
 Re: 2016 участников
Сообщение17.07.2017, 13:10 
Заслуженный участник


10/01/16
2315
ET в сообщении #1234086 писал(а):
примерно такими рассуждениями:

Точнее, так: возьмем $n+2$ чела; удалим пару знакомых; тогда....

(Оффтоп)

А за Ваше слишком вольное изложение вредный проверяющий мог влепить и "минус-плюс" (решения нет; есть правильная идея)

 Профиль  
                  
 
 Re: 2016 участников
Сообщение18.07.2017, 09:19 
Аватара пользователя


21/06/08
476
Томск
DeBill в сообщении #1234097 писал(а):
ET в сообщении #1234086 писал(а):
примерно такими рассуждениями:

Точнее, так: возьмем $n+2$ чела; удалим пару знакомых; тогда....

(Оффтоп)

А за Ваше слишком вольное изложение вредный проверяющий мог влепить и "минус-плюс" (решения нет; есть правильная идея)

Точнее возьмем $2n+2$ человека.

 Профиль  
                  
 
 Re: 2016 участников
Сообщение18.07.2017, 10:34 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
daogiauvang в сообщении #1234310 писал(а):
DeBill в сообщении #1234097 писал(а):
ET в сообщении #1234086 писал(а):
примерно такими рассуждениями:

Точнее, так: возьмем $n+2$ чела; удалим пару знакомых; тогда....

(Оффтоп)

А за Ваше слишком вольное изложение вредный проверяющий мог влепить и "минус-плюс" (решения нет; есть правильная идея)

Точнее возьмем $2n+2$ человека.

Точнее, на два человека больше, чем было. (Кто умеет взять ещё точнее? :D)

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

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



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

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


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

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