2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 В группе 9 школьников
Сообщение18.08.2017, 10:07 
Аватара пользователя


21/06/08
476
Томск
В группе есть 9 школьников, у двух любых школьников есть общий знакомый. Доказать, что можно выбрать 3 школьника, у которых список знакомых будет содержать все 6 оставшихся!

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение23.08.2017, 21:55 
Аватара пользователя


27/02/09

416
Мегаполис
"У любых двух - общий знакомый" - всего пар, у которых должен быть общий знакомый, равно 36 (сочетаний из 9 по 2).
Далее можно представить реальные ситуации тройками: наша пара и общий знакомый
из списка 1..9, (X,Z) - пара, а Y - общий знакомый: (X,Y,Z).
Минимальное количество разных Y, чтобы составлялись корректные тройки, равно 3, ибо составляются "тройки" разных чисел. Тогда очевидно, что эти трое, у которых в списках знакомых все остальные, и есть эти 3.
Максимальное количество разных Y равно 9. Если представить все знакомства графом, где вершины - школьники, а ребра - знакомства, то максимальная возможная валентность вершины при условии, что общими знакомыми будут все вершины, равна 6, ((36/9)+2=6), что соответствует как раз 6 знакомствам у любого школьника.
Если валентности каких-либо вершин понижать, то валентность других вершин будет только повышаться, но при этом и меньше трех вершин, отвечающих общим знакомым при нашем построении, быть не может.

PS Валентность вершины - число ребер при вершине. Степень вершины - число ориентированных ребер, выходящих из вершины.

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение25.08.2017, 06:36 
Аватара пользователя


21/06/08
476
Томск
Мастак в сообщении #1242629 писал(а):
"У любых двух - общий знакомый" - всего пар, у которых должен быть общий знакомый, равно 36 (сочетаний из 9 по 2).
Далее можно представить реальные ситуации тройками: наша пара и общий знакомый
из списка 1..9, (X,Z) - пара, а Y - общий знакомый: (X,Y,Z).
Минимальное количество разных Y, чтобы составлялись корректные тройки, равно 3, ибо составляются "тройки" разных чисел. Тогда очевидно, что эти трое, у которых в списках знакомых все остальные, и есть эти 3.
Максимальное количество разных Y равно 9. Если представить все знакомства графом, где вершины - школьники, а ребра - знакомства, то максимальная возможная валентность вершины при условии, что общими знакомыми будут все вершины, равна 6, ((36/9)+2=6), что соответствует как раз 6 знакомствам у любого школьника.
Если валентности каких-либо вершин понижать, то валентность других вершин будет только повышаться, но при этом и меньше трех вершин, отвечающих общим знакомым при нашем построении, быть не может.

PS Валентность вершины - число ребер при вершине. Степень вершины - число ориентированных ребер, выходящих из вершины.

Не понимаю у Вас опредедение корректных тройк? и почему минимальное количество разных Y равно 3.

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение29.08.2017, 21:19 
Заслуженный участник


10/01/16
2315
Пусть А не знаком с двумями (или меньше). Тогда А и его незнакомые дают то что надо.
Пусть А не знаком с $a,b,c$, и $x$ - общий для $a,b$. Тогда А, $x$ и $c$.
Пусть А не знаком с $a,b,c,d$, и $x$ - обший для $a,b$, $y$ - для $c,d$. Тогда А, $x$ и $y$.
Пусть А знаком не более чем с двумя , тогда А и его знакомые - что надо (все незнакомые с А знакомы с его знакомыми).
Осталось заметить, что случай, когда у каждого ровно три знакомых, невозможен: трижды девять - нечетное оно...

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение30.08.2017, 05:27 


28/09/16
24
Допустим, все школьники знают 1,2 и 3го, и больше не знают никого. Тогда у любой пары будет общий знакомый и ни одна из троек не даст 6 знакомых в сумме

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение30.08.2017, 12:58 
Аватара пользователя


27/02/09

416
Мегаполис
daogiauvang в сообщении #1242849 писал(а):
Мастак в сообщении #1242629 писал(а):
"У любых двух - общий знакомый" - всего пар, у которых должен быть общий знакомый, равно 36 (сочетаний из 9 по 2).
Далее можно представить реальные ситуации тройками: наша пара и общий знакомый
из списка 1..9, (X,Z) - пара, а Y - общий знакомый: (X,Y,Z).
Минимальное количество разных Y, чтобы составлялись корректные тройки, равно 3, ибо составляются "тройки" разных чисел. Тогда очевидно, что эти трое, у которых в списках знакомых все остальные, и есть эти 3.
Максимальное количество разных Y равно 9. Если представить все знакомства графом, где вершины - школьники, а ребра - знакомства, то максимальная возможная валентность вершины при условии, что общими знакомыми будут все вершины, равна 6, ((36/9)+2=6), что соответствует как раз 6 знакомствам у любого школьника.
Если валентности каких-либо вершин понижать, то валентность других вершин будет только повышаться, но при этом и меньше трех вершин, отвечающих общим знакомым при нашем построении, быть не может.

PS Валентность вершины - число ребер при вершине. Степень вершины - число ориентированных ребер, выходящих из вершины.

Не понимаю у Вас опредедение корректных тройк? и почему минимальное количество разных Y равно 3.


Так все пары (X,Z), у которых должен быть общий знакомый, есть все сочетания из 1..9 по два.
И мои тройки (X,Y,Z) могут быть получены вставкой в пары чисел из 1..9.
И этих чисел может быть не менее 3.
Доказательство. Пусть этих чисел 2 и эти есть числа y1 и y2 из 1..9. Но среди пар, которые представляют собой ВСЕ ВОЗМОЖНЫЕ сочетания, должна быть пара (y1,y2) (либо (y2,y1)), а
тройка (y1,y1,y2) или (y1,y2,y2) не является корректной тройкой (общего знакомого).

То есть 3 - это минимальное количество возможных разных Y.

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение30.08.2017, 18:49 
Заслуженный участник


10/01/16
2315
Vadimovich
А 1,2,3?

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение30.08.2017, 23:16 


28/09/16
24
1 и 2 имеют общего знакомого 3, 1 и 3 - 2, 2 и 3 -1
Остальные знают кого-то из этих трех.

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение31.08.2017, 01:57 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Vadimovich в сообщении #1244013 писал(а):
Остальные знают кого-то из этих трех.
Следовательно, общий список (не список общих, а суммарный список) знакомых для этих трёх содержит всех оставшихся (6). чтд.

 Профиль  
                  
 
 Re: В группе 9 школьников
Сообщение31.08.2017, 09:35 


28/09/16
24
Таки да, прошу прощения

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

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



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

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


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

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