В классе 10 человек, у каждого три друга среди одноклассников. Они разбились на 5 команд по 2 человека, в каждой команде друзья. Учительница сказала переделиться по другому, так как Вася и Петя не должны быть в одной команде. Вася заметил: ѕНо тогда какая-то из команд обязательно не будет дружнойї. Приведите пример, как такое может быть.

задан 21 Сен '19 17:40

10|600 символов нужно символов осталось
0

Построим пример в виде графа. Для начала нарисуем контур 5-угольника ABCDE, проводя все его стороны. Добавим к нему диагонали BD и CE. Сделаем копию этого рисунка в виде A'B'C'D'E', и соединим A с A' (это будут Вася и Петя). Легко понять, что каждая вершина графа соединена ровно с тремя другими. Ребро A-A' представляет собой "мостик". Если его убрать, то граф распадается на части, в каждой из которых по 5 вершин. Ввиду нечётности этого числа, разбиение на пары друзей оказывается невозможным.

Заметим, что есть пример компании из 16 человек, где у каждого ровно 3 друга, но разбиение на пары друзей невозможно. Это известная задача похожего содержания. Здесь надо взять третью копию 5-угольника в виде A''B''C''D''E'', а потом соединить новую точку P с вершинами A, A', A''.

ссылка

отвечен 21 Сен '19 18:31

10|600 символов нужно символов осталось
1

Это (как и другие две, предложенные anna48) задача с текущей олимпиады :( http://yumsh.ru/cms/sites/default/files/zao_45678_2019.pdf

ссылка

отвечен 28 Сен '19 15:57

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2

задан
21 Сен '19 17:40

показан
839 раз

обновлен
28 Сен '19 15:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru