Изменения

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M</tex>\{<tex>a</tex>}. Пусть <tex>\alpharho:M^m\rightarrow</tex> {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\alpharho': M_0^{m-1}\rightarrow</tex> {1,2}, определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\alpharho'(В) = \alpharho(B U</tex>{a}<tex>)</tex>.Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, для которого <tex>\alpharho'(В)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, для которого <tex>\alpharho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex> -элементное подмножество <tex>N_1 \subset M_1</tex>, для которого <tex>\alpharho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, для которого <tex>\alpharho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup </tex>{<tex>a</tex>}. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\alpharho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A</tex>\{<tex>a</tex>}<tex>\in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\alpharho(A)=\alpharho'(A</tex>\{<tex>a</tex>}<tex>)=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\alpharho:M^m \rightarrow [1..k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\alpharho':M^m \rightarrow </tex>{<tex>0,k</tex>}, в которой цвета <tex>1,...,k-1</tex> раскраски <tex>\alpharho</tex> склеены в цвет 0. Тогда существует либо таксе подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(k-1;n_1,...,n_{k-1})</tex> и <tex>\alpharho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\alpharho(A)=\alpharho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\alpharho'(A)=0</tex> следует <tex>\alpharho(A) \in [1..k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,...,k-1</tex>