База ответов ИНТУИТ

Дискретный анализ и теория вероятностей

<<- Назад к вопросам

Не меньше какого числа должно быть n, чтобы выполнялось следующая теорема? Пусть M_1,... n-элементные подмножества какого-то множества, причем каждый элемент этого множества принадлежит не более чем n множествам M_i, тогда существует одноцветная раскраска данного n-элементного подмножества.

(Ответ необходимо ввести в поле ввода.)
Варианты ответа
Похожие вопросы
Пусть n \geqslant 9.Пусть M_1,... n-элементные подмножества какого-то множества, причем каждый элемент этого множества принадлежит не более чем n множествам M_i, тогда существует одноцветная раскраска данного n-элементного подмножества. При применении к данной ситуации локальной леммы Ловаса чему равно d?
Пусть n \geqslant 9.Пусть M_1,... n-элементные подмножества какого-то множества, причем каждый элемент этого множества принадлежит не более чем n множествам M_i, тогда существует одноцветная раскраска данного n-элементного подмножества. Пусть событие A_i состоит в том, что M_i множество одноцветно. Чему равна вероятность A_i?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Допустим, A_1 \in {\cal F}. Выберите все множества, которые в таком случае также попадают в {\cal F} кроме A_1?
Как называется граф KG_{n,k}(V,E) построенный следующим образом? Имеется R_n=\{1,....n \} - множество натуральных чисел от 1 до n. Множество вершин данного графа образуют все k-элементные подмножества из множества R_n. Говорят, что пара v_1 \sim v_2 образуют ребро графа, тогда и только тогда v_1 \cap v_2 =\varnothing.
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что является наиболее точной верхней оценкой мощности {\cal F}\cap{\cal A}?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что верно относительно мощности {\cal F}\cap{\cal A}?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что верно относительно | {\cal F}\cap{\cal A}|?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}.Среди множеств A_2,...,A_k и A_{n-k+2},...,A_{n} выберите множество, с котором не пересекается A_3.
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}.Среди множеств A_2,...,A_k и A_{n-k+2},...,A_{n} выберите множество, с котором не пересекается A_2.
Пусть G(n,p) -случайный граф, множество, состоящее из n вершин, а каждое ребро проводим с вероятностью p, которая независит от вероятности проведения других ребер и может зависеть от n. Пусть случайная величина T_n - число треугольников в случайном графе. Если p=o\left(\frac 1 n\right), то к чему ассимтотические стремится математическое ожидание MT_n?