2014 dxdy logo

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

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




 
 Неразбиваемая на пары компания
Сообщение02.11.2018, 12:45 
Аватара пользователя
Приведите пример компании, в которой у каждого ровно трое друзей, но которую нельзя разбить на пары так, чтобы люди в каждой паре были друзьями.

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 15:39 
Надо покрутить 5 человек...

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

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

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 15:44 
kotenok gav в сообщении #1351167 писал(а):
Надо покрутить 5 человек...

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

-- 02.11.2018, 15:45 --

kotenok gav в сообщении #1351167 писал(а):
Не, не выходит. Сейчас буду пытаться делать 7.

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

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 15:45 
Ну так в этом и вся соль! 8-)

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

wrest в сообщении #1351170 писал(а):
Думаете, если пятерых не удалось разбить на пары, то получится с семерыми? :facepalm:

Ktina в сообщении #1351127 писал(а):
но которую нельзя разбить на пары


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

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

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 16:03 
Аватара пользователя
kotenok gav в сообщении #1351171 писал(а):
Похоже, для нечетных ровно 3 сделать не получится.

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

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 16:06 
Да, просто поздно уже, не догадался. Да и не думал.

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение02.11.2018, 16:31 
Аватара пользователя

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

Изображение

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

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

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

-- 02.11.2018, 16:53 --

JohnDou в сообщении #1351181 писал(а):
Предлагаю усилить задачу, и найти достаточный критерий для выполнения условия.

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

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

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение03.11.2018, 21:43 
Аватара пользователя
wrest,
туплю. Как насчёт необходимого критерия?

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение03.11.2018, 22:18 
JohnDou
Критерий чего? Если есть такой чел как я написал, то разбить на дружные пары нельзя.

 
 
 
 Re: Неразбиваемая на пары компания
Сообщение04.11.2018, 03:03 
wrest в сообщении #1351515 писал(а):
Критерий чего?

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

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group