Изменения

Перейти к: навигация, поиск

Fusion tree

2 байта добавлено, 21:41, 4 июня 2015
Утверждение (исправление)
|about=
|statement=Дана последовательность из <tex>r</tex> чисел <tex>b_0<b_1<\ldots <b_{r-1}</tex>. Тогда существует последовательность <tex>m_0<m_1\ldots <m_{r-1}</tex>, такая что:
 1) # все <tex>b_i + m_j</tex> различны, для <tex>0\leqslant i,j \leqslant r-1</tex>; 2) # <tex>b_0 + m_0\leqslant b_1 + m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}</tex>; 3) # <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.
|proof=
Выберем некоторые <tex>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \not\equiv m_j' + b_p</tex>. Предположим, что мы выбрали <tex>m_1' \ldots m_{t-1}'</tex>. Тогда <tex>m_t' \ne m_i' + b_j - b_k \; \forall i,j,k</tex>. Всего <tex>t\times r\times r < r^3 </tex> недопустимых значений для <tex>m_t'</tex>, поэтому всегда можно найти хотя бы одно значение.
Анонимный участник

Навигация