Для полета на Марс набирают группу людей, в которой каждый должен владеть хотя бы одной из профессий повара, медика, пилота или астронома. При этом в техническом задании указано, что каждой профессией из списка должно владеть ровно 6 человек в группе. Кроме того указано, что в группе должен найтись ровно один человек, владеющий всеми этими профессиями; каждой парой профессий должны владеть ровно 4 человека; каждой тройкой — ровно 2. Выполнимо ли такое техническое задание?

задан 26 Сен '17 23:02

изменен 26 Сен '17 23:47

Условие задачи как-то неожиданно обрывается. Не сказано, что требуется найти.

(26 Сен '17 23:34) falcao

Выполнимо ли такое техническое задание?

(26 Сен '17 23:47) Икс
10|600 символов нужно символов осталось
1

Подсчитаем общее количество человек в группе через формулу включений и исключений. Рассматриваем 4 множества людей, владеющей той или иной профессией. Поскольку каждый владеет хотя бы одной, общее число равно 6+6+6+6-4x6+2x4-1=7. Здесь учтено, что двойных пересечений 6, а тройных 4. Но тогда получается, что всеми всеми профессиями владеет более одного человека. Рассуждаем на двудольном графе. Из одной доли выходит 24 ребра. Если "мастер на все руки" один, то в другой доле одна вершина имеет степень 4, а остальные 6 имеют степень не более 3. Итого 22 < 24 -- противоречие. Значит, задание невыполнимо.

ссылка

отвечен 27 Сен '17 0:12

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

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

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

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

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

отмечен:

×1,295
×14

задан
26 Сен '17 23:02

показан
1345 раз

обновлен
27 Сен '17 0:12

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

по почте:

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

по RSS:

Ответы

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

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