Какое наибольшее количество подмножеств можно выбрать из множества 1; 2; 3;…; 2013 так чтобы объединив два любых подмножества получить подмножество, содержащее 3 элемента.

задан 28 Фев '13 20:19

изменен 28 Фев '13 20:41

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

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

Подмножества должны содержать равное количество элементов. По одному мало. По три много. Остается по 2, причем все подмножества должны иметь общую цифру. Выбрать эту цифру можно 2013 способами, для выбора второй есть 2012 вариантов (любое число без уже выбранного). Тогда число всех подмножеств $%2013\cdot 2012 /2 $%, с учетом того, что множество не изменяется при перестановке его элементов.

ссылка

отвечен 28 Фев '13 23:56

1

Здесь подсчитано общее количество двухэлементных подмножеств. Но среди них есть, например, $%{1,2\}$% и $%\{3,4\}$%. Их объединение не будет трёхэлементным.

(1 Мар '13 10:45) falcao

Согласна, что немного перестаралась. Посчитано общее число комбинаций. А разных подмножеств при фиксированном одном элементе будет 2012.

(1 Мар '13 14:43) Танюша
10|600 символов нужно символов осталось
2

Наибольшее количество равно $%2012$%. Оно получается так: фиксируем один из элементов, и рассматриваем все двухэлементные подмножества, его содержащие. Их будет столько, сколько имеется оставшихся элементов, то есть $%2012$%.

Докажем, что именно это число является наибольшим. Понятно, что в нашей системе не может быть подмножеств более чем из трёх элементов. Допустим, что имеется трёхэлементное множество. Тогда все остальные множества будут в нём содержаться, а таких подмножеств явно мало: "рекорд" этим не будет превзойдён. (Здесь получается максимум $%4$% подмножества: система из $%\{a,b,c\}$%, $%\{a,b\}$%, $%\{a,c\}$%, $%\{b,c\}$% условиям задачи в принципе удовлетворяет, но в ней всего $%4$% подмножества.)

Итак, пусть в каждом из подмножеств не более двух элементов. Легко понять, что пустого подмножества в системе нет. Если есть одноэлементное подмножество $%\{a\}$%, то оно всего одно. Остальные будут двухэлементными, и среди них любые два обязаны иметь общий элемент, отличный от $%a$%. Если они имеют общий элемент $%b$%, то таких подмножеств не более $%2011$%, и вместе с $%\{a\}$% получается система из $%2012$% подмножеств. А если общего элемента нет, то легко проверить, что тогда подмножеств без $%a$% максимум три: они имеют вид $%\{b,c\}$%, $%\{b,d\}$%, $%\{c,d\}$%.

Наконец, если все рассматриваемые подмножества двухэлементны, то либо все они имеют общий элемент, и тогда их $%2012$%; либо это не так, и тогда их максимум три -- с описанной в предыдущем абзаце структурой.

ссылка

отвечен 1 Мар '13 2:11

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

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

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

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

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

отмечен:

×846

задан
28 Фев '13 20:19

показан
1276 раз

обновлен
1 Мар '13 14:43

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

по почте:

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

по RSS:

Ответы

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

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