Покрытие подмножествами

[rkrkrk]

Пусть $A$ - множество из $2^n$ элементов. Каждому $x$ сопоставили $A_x$ - подмножество $A$ из $2^m$ элементов, содержащее $x$.
Правда, что можно выбрать $2^n/Poly_1(n)$ элементов в $A$, а также подмножества вида $A_x$ так, что каждый элемент будет покрыт этими подмножествам, но не более $Poly_2(n)$ раз? ($Poly_i(n)$ - какие-то полиномы)

Я умею доказывать это утверждение, если известно, что каждый элемент покрыт не менее $k$ и не более $2k$ подмножествами. Тогда вероятность того, что случайный элемент будет покрыт случайно выбранным подмножеством $> 1 - 2^{m - n -1}$. Вероятность того, что случайный элемент будет покрыт $n\cdot 2^{n - m + 1}$ множествами $> (1 - 2^{m-n-1})^{n\cdot 2^{n- m +1}} \approx e^{-n} < 2^{-n}$. Это значит, что можно выбрать $n\cdot 2^{ n - m + 1}$ множеств так, что они будут покрывать все элементы. Каждый элемент в среднем будет покрыт $2n$ множествами, а элементов, которые покрываются $> 100n$ множествами меньше половины. Выкинем их - получим требуемое.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Приведите свои попытки решения и укажите конкретные затруднения.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[patzer2097]

rkrkrk в сообщении #890327 писал(а):

Правда, что можно выбрать $2^n/Poly_1(n)$ элементов в $A$, а также подмножества вида $A_x$

rkrkrk в сообщении #890327 писал(а):

Это значит, что можно выбрать $n\cdot 2^{ n - m + 1}$ множеств

так разве $n\, 2^{ n - m + 1}$ это $2^n/Poly_1(n)$, или есть дополнительные предположения о связи $m$ и $n$? Или первое процитированное предложение надо понимать как-то еще?

[rkrkrk]

Извиняюсь: имелось ввиду, что элементов $2^n/Poly(n)$, а подмножеств - сколько захотим

-- 26.07.2014, 12:12 --

что-то не вижу, где здесь можно редактировать((

[Deggial]

rkrkrk в сообщении #890377 писал(а):

что-то не вижу, где здесь можно редактировать((

Редактировать посты можно только в течение часа после их опубликования (либо - в Карантине)