Question

За круглым столом сидят 15 гостей так, что любой из них сидит рядом со своими знакомыми. Оказалось, что каждый из гостей знаком ровно с шестерыми из остальных, при этом среди любых троих есть двое незнакомых. Может ли такое быть?

Answer 1

Ответ:

Может.

каждый из гостей знаком ровно с шестерыми из остальных, при этом среди любых троих СИДЯЩИХ РЯДОМ!!! есть двое незнакомых.

Пошаговое объяснение:

1) начертим круг и разместим гостей

2) у каждого есть 6 друзей.

Мы не знаем кто с кем знаком, поэтому попробуем расположить знакомых, равномерно по кругу.

---1 точно знаком с 15 и 2 (по условию:любой из них сидит рядом со своими знакомыми)

---1 пусть знаком с 5 и 6 (четвертый и пятый человек, которые сидят слева от первого)

---1 пусть знаком с 12 и 11 (четвертый и пятый человек, которые сидят справа от первого)

Итого: у 1 - шесть знакомых

1 знаком с 2,15-12,11,-5,6

3) определим знакомых у каждого

3.1)первый, четвертый и пятый человек слева

3.2)первый, четвертый и пятый человек справа

1 знаком с 2,15,--12,11--5,6

2 знаком с 1,3,--7,6--12,13

3 знаком с 2,4,--8,7--13,14

4 знаком с 3,5,--9,8--14,15

5 знаком с 4,6,--10,9--15,1

6 знаком с 5,7,--11,10--1,2

7 знаком с 6,8,--12,11--2,3

8 знаком с 7,9,--13,12--3,4

9 знаком с 8,10,--14,13--4,5

10 знаком с 9,11,--15,14--5,6

11 знаком с 10,12,--1,15--6,7

12 знаком с 11,13,--2,1--7,8

13 знаком с 12,14--3,2--8,9

14 знаком с 13,15--4,3--9,10

15 знаком с 14,1--5,4--10,11

4) среди любых троих СИДЯЩИХ РЯДОМ есть двое незнакомых

Логично предположить, что из тройки 15-1-2, друг друга не знают 15 человек и 2 человек, а вот 1 человек знает и 15 и 2

Выделим незнакомых

15--1--2

1--2--3

2---3---4

3---4---5

4---5---6

5---6---7

6---7---8

7---8---9

8---9---10

9---10---11

10---11---12

11---12---13

12---13--14

13---14---15

14---15---1

5) Проверим на совпадения  незнакомых (пункт 4) и знакомых (пункт 3)

Вывод: совпадений нет

Ответ: да, может

Answer 2

Да, такая ситуация возможна.

Давайте представим гостей в виде вершин графа, где каждая вершина представляет одного гостя, а ребра соединяют знакомых друг с другом. В этом случае условие задачи означает, что у каждой вершины 6 соседей (знакомых) и 8 незнакомых.

Также из условия задачи следует, что любая тройка гостей содержит двух незнакомых. Это значит, что если мы возьмем любую тройку вершин в графе и соединим их ребрами, то эта тройка образует полный подграф размера 3, так как между всеми тремя вершинами есть ребра.

Теперь рассмотрим граф, который называется графом Петерсена - это простой нерегулярный граф на 10 вершинах. Он является примером графа, удовлетворяющего всем условиям задачи. В графе Петерсена каждая вершина имеет 3 соседа (знакомых) и 2 незнакомых. Также любая тройка вершин образует полный подграф размера 3, где каждая вершина соединена с двумя другими.

Теперь мы можем взять 15 копий графа Петерсена и расположить вершины так, чтобы каждая вершина из копий соответствовала гостю за круглым столом. Тогда каждый гость будет знаком с шестерыми из остальных (3 соседа из своего копия графа Петерсена и 3 соседа из двух соседних копий), и среди любых троих гостей будут двое незнакомых (потому что тройка гостей в графе Петерсена образует полный подграф размера 3).

Таким образом, такая ситуация, когда 15 гостей сидят за круглым столом и каждый из них знаком ровно с шестерыми из остальных, при этом среди любых троих есть двое незнакомых, возможна.