В шестиэлементном множестве выбрано 32 подмножества, каждые три из которых имеют общий элемент. Докажите, что все эти подмножества имеют общий элемент.

задан 8 Ноя 0:47

изменен 11 Ноя 0:24

1

Частный случай этой задачи http://www.problems.ru/view_problem_details_new.php?id=73560

(11 Ноя 4:36) splen
10|600 символов нужно символов осталось
2

Из двух подмножеств A и A' (дополнение) не более одного принадлежит системе. Значит, ровно одно принадлежит, так как пар таких подмножеств всего 32.

Если A принадлежит системе, и A<=B, то B должно принадлежать системе: в противном случае B' принадлежит, и тогда A не пересекается с B'.

Предположим, что общего элемента у множеств системы нет. Тогда никакое одноэлементное множество системе не принадлежит. Нет также и 2-элементных множеств. В противном случае для A={x,y} мы указали какое-то множество системы без x, и какое-то без y, получая три множества без общего элемента.

Из 20 трёхэлементных множеств в системе есть ровно половина, и тогда все 22 подмножества из >=4 элементов системе принадлежат. Если у 3-элементных множеств есть общий элемент, то он есть и у всех множеств. Далее можно "сжать" систему до 10 трёхэлементных подмножеств.

Рассмотрим множество A={x,y,z} из системы. Так как x не является общим элементом, найдётся множество системы без x. Допустим, что в нём нет y или z. В первом случае, если в нём нет y, рассмотрим множество системы без z. Тогда у трёх подмножеств не будет общего элемента. Таким образом, любое подмножество, отличное от A, содержит два элемента из A.

Пусть a, b, c -- три элемента, не вошедшие в A. Подмножеств, содержащих x, y, в "сжатой" системе имеется всего три. То же для двух других пар. Так как кроме A у нас 9 подмножеств, все такие комбинации должны быть реализованы, то есть любая пара из трёх элементов A с любым из трёх оставшихся. Но тогда возникают подмножества {x,y,c}, {x,z,b}, {y,z,a}, для которых нет общего элемента.

ссылка

отвечен 11 Ноя 1:31

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

(2 дня назад) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,191
×567
×269
×6
×4

задан
8 Ноя 0:47

показан
57 раз

обновлен
2 дня назад

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

по почте:

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

по RSS:

Ответы

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

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