Неразбиваемая на пары компания

[Ktina]

Приведите пример компании, в которой у каждого ровно трое друзей, но которую нельзя разбить на пары так, чтобы люди в каждой паре были друзьями.

[kotenok gav]

Надо покрутить 5 человек...

-- 02 ноя 2018, 23:14 --

Не, не выходит. Сейчас буду пытаться делать 7.

[wrest]

kotenok gav в сообщении #1351167 писал(а):

Надо покрутить 5 человек...

Да уж, пятерых на пары не разбить!

-- 02.11.2018, 15:45 --

kotenok gav в сообщении #1351167 писал(а):

Не, не выходит. Сейчас буду пытаться делать 7.

Думаете, если пятерых не удалось разбить на пары, то получится с семерыми?

[kotenok gav]

Ну так в этом и вся соль!

-- 02 ноя 2018, 23:18 --

wrest в сообщении #1351170 писал(а):

Думаете, если пятерых не удалось разбить на пары, то получится с семерыми?

Ktina в сообщении #1351127 писал(а):

но которую нельзя разбить на пары

-- 02 ноя 2018, 23:22 --

Похоже, для нечетных ровно 3 сделать не получится.

[Ktina]

kotenok gav в сообщении #1351171 писал(а):

Похоже, для нечетных ровно 3 сделать не получится.

Да, это так. Сопоставим каждой паре друзей телефонный провод, который их соединяет. Тогда от каждого друга отходят три конца. Поскольку всего друзей в компании - нечётное число, количество концов тоже будет нечётным. Но у каждого провода два конца, следовательно, в сумме должно быть чётное число концов, а это приводит к противоречию.

[kotenok gav]

Да, просто поздно уже, не догадался. Да и не думал.

[JohnDou]

(Возможный ответ)

Предлагаю усилить задачу, и найти достаточный критерий для выполнения условия.

[wrest]

Ну, у меня получилось из 16-ти.
Три пятерки из которых торчит по одной незакрытой "дружбе" и 16-й чел, эти пятерки объединяющий.

А, тов. JohnDou уже привел ответ.

-- 02.11.2018, 16:53 --

JohnDou в сообщении #1351181 писал(а):

Предлагаю усилить задачу, и найти достаточный критерий для выполнения условия.

Критерий, кажись, такой: не должно быть чела, при удалении которого компания распалась бы на три не связанных дружбой части.

Ну да, оно и понятно: такой чел, попав в одну из пар при разбиении на пары, "разрежет" компанию на две части (в каждой по нечетному количеству человек) так что кому-нибудь обязательно не найдется дружеской пары.

[JohnDou]

wrest,
туплю. Как насчёт необходимого критерия?

[wrest]

JohnDou
Критерий чего? Если есть такой чел как я написал, то разбить на дружные пары нельзя.

[kotenok gav]

wrest в сообщении #1351515 писал(а):

Критерий чего?

Неразбиваемости.