В группе 9 школьников

[daogiauvang]

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

[Мастак]

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

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

[daogiauvang]

Мастак в сообщении #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.

[DeBill]

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

[Vadimovich]

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

[Мастак]

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.

[DeBill]

Vadimovich
А 1,2,3?

[Vadimovich]

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

[grizzly]

Vadimovich в сообщении #1244013 писал(а):

Остальные знают кого-то из этих трех.

Следовательно, общий список (не список общих, а суммарный список) знакомых для этих трёх содержит всех оставшихся (6). чтд.

[Vadimovich]

Таки да, прошу прощения