В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Может ли оказаться так, что у каждого из учеников - не более 12 друзей?

задан 14 Ноя '17 12:33

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

Да, могло.

Разобьём 25 человек на две группы по 12 и 13 в каждой. Пусть все 12 дружат между собой, все 13 дружат между собой, а больше никто не дружит. Тогда у каждого не более 12 друзей. Среди любых троих есть двое, попавшие в одну группу, а они дружат. Все условия выполнены.

ссылка

отвечен 14 Ноя '17 12:59

@falcao, большое спасибо!

Можно даже менее абстрактно - не просто на две группы по 12 и 13, а представить, что в классе 12 мальчиков и 13 девочек. Все мальчики дружат друг с другом и не дружат с девочками, а все девочки дружат друг с дружкой и не дружат с мальчиками :) Так и задумывалась задача :)

(14 Ноя '17 13:17) Аллочка Шакед

@falcao, а вот не более 11 друзей у каждого быть, кстати, не может. Знаете, почему?

(14 Ноя '17 13:19) Аллочка Шакед
2

@Аллочка Шакед: да, с мальчиками и девочками наглядней.

Я сначала думал, что ответ будет отрицательным, и хотел применить теорему Турана к дополнительному графу. Для 11 друзей там степени вершин будут >=13, и рёбер будет строго больше 25^2/2. В принципе, возможно и более прямое доказательство, но тут сам "инстрУмент" довольно стандартный.

(14 Ноя '17 13:24) falcao

@falcao, простите за оффтоп, но Ваше слово "инстрУмент" напомнило мне стихотворение "Ленин и Печник" :)

(14 Ноя '17 17:32) Аллочка Шакед
1

@Аллочка Шакед: дык, классика! :)

А ещё бывает "докУмент", и многое другое.

(14 Ноя '17 18:18) falcao

@Аллочка Шакед, @falcao. Вы ведете себя не толерантно по поводу мальчиков и девочек. Отвлекитесь на день от математики и узнаете, что в расслабленной Европе гендерная политика уже не хочет делить людей на 2.

(15 Ноя '17 11:37) nynko

@nynko: я как раз думал об этом обстоятельстве, но олимпиадных задач это почти не коснулось. Там разве что Васи и Пети не должно быть, ибо явное неравноправие, а должны быть Алиса и Боб, причём Алису следует упоминать первой :)

(15 Ноя '17 12:18) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,130
×1,077
×338
×276
×147

задан
14 Ноя '17 12:33

показан
390 раз

обновлен
15 Ноя '17 12:18

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

по почте:

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

по RSS:

Ответы

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

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