|
Какое наибольшее количество подмножеств можно выбрать из множества 1; 2; 3;…; 2013 так чтобы объединив два любых подмножества получить подмножество, содержащее 3 элемента. задан 28 Фев '13 20:19 
serg55 |
|
Подмножества должны содержать равное количество элементов. По одному мало. По три много. Остается по 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)
Танюша
|
|
Наибольшее количество равно $%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 
falcao |