Suppose that the set $M=\{1,2,\cdots,n\}$ is split into $t$ disjoint subsets $M_{1}$, $\cdots$, $M_{t}$ where the cardinality of $M_i$ is $m_{i}$, and $m_{i} \ge m_{i+1}$, for $i=1,\cdots,t-1$. Show that if $n>t!\cdot e$ then at least one class $M_z$ contains three elements $x_{i}$, $x_{j}$, $x_{k}$ with the property that $x_{i}-x_{j}=x_{k}$.
Problem
Source:
Tags: inequalities, floor function
11.01.2008 21:16
This result is known as Schur Theorem. Here's a proof: Using Taylor series approximation for $ f(x) = e^x$ at $ 0$ (and later at $ x = 1$) we have the well-known $ e = 1 + \frac1{1!} + \frac1{2!} + \frac1{3!} + \ldots$. So $ t!\cdot e = 1 + 2! + \ldots + t! + t! + \frac1{t + 1} + \frac1{(t + 1)(t + 2)} + \ldots$. Because $ \frac1{t + 1} + \frac1{(t + 1)(t + 2)} + \ldots < \frac1{t + 1} + \frac1{(t + 1)^2} + \frac1{(t + 1)^3} + \ldots = \frac1t < 1$, we have $ S_t = \lfloor t!e \rfloor = t!(1 + 1! + 2! + \ldots + t!)$. From here, it is easy to see that the sequence $ (S_t)_{t\ge1}$ satisfies the recurrence relation $ S_t = tS_{t - 1} + 1$, with $ S_0 = 1$. This recurrence relation is one of the main ideas of the proof. Take now a partition in $ t$ subsets of the set $ \{1,2,\ldots,S_t\}$. Assume no subset of the partition contains three elements s.t. $ a + b = c$. Since $ t\not|S_t$, at least $ \lfloor\frac {S_t}t\rfloor + 1 = S_{t - 1} + 1$ numbers lie in the same subset, say $ X_1$. Let $ x_1 < x_2 < \ldots < x_k$ be the elements of $ X_1$, where $ k = S_{t - 1} + 1$. Then the $ k - 1 = S_{t - 1}$ numbers $ y_1 = x_2 - x_1$, $ y_2 = x_3 - x_1,\ldots,y_{k - 1} = x_k - x_1$ do not lie in $ X_1$. These numbers, hence, lie in the remaining $ t - 1$ subsets. Using similar arguments, at least $ \lfloor\frac {S_{t - 1}}{t - 1}\rfloor + 1 = S_{t - 2} + 1$ elements of $ \{y_1,\ldots,y_k\}$ lie in the same subset - $ X_2$. Now, any two numbers in $ X_2$ are of the form $ x_i - x_1$, $ x_j - x_1$, so their difference can't be in $ X_1$ or in $ X_2$. Ordering the numbers $ z_1 < z_2 < \ldots < z_l$ of $ X_2$, we have that the $ S_{t - 2}$ differences $ z_2 - z_1,\ldots,z_l - z_1$ aren't in $ X_1$ or $ X_2$, so $ \lfloor\frac {S_{t - 2}}{t - 2}\rfloor + 1 = S_{t - 3} + 1$ of them must lie in the same subset $ X_3$. Continuing so, we get that there are at least $ S_{t - k} + 1$ elements in the same subset $ X_k$. Finally, the set $ X_t$ will contain at least $ S_0 + 1 = 2$ elements, say $ a < b$. But then $ b - a$ must lie in one of the sets $ X_1,\ldots,X_t$, say $ X_i$. One the above arguments show that $ a$ and $ b$ are of the form $ q_m - q_r$ and $ q_n - q_r$, where $ q_r < q_m < q_n$ are in $ X_i$. Then $ b - a = q_n - q_m\in X_i$ and we've reached a contraditction. Ok, the idea used but not clearly expressed is that if $ a,b\in X_j$, where $ j\ge i$, then $ a,b$ are of the form $ z_m - z_k$ and $ z_n - z_k$, for some $ z_m,z_n,z_k\in X_i$. This results clearly from the construction of the sets $ X_1,X_2,\ldots,X_t$.
29.05.2009 09:12
A similar proof for Schur Theorem Consider a gragh with vertices $ V_1,V_2,...V_{n+1}$ We color the edge $ V_pV_q$ with color $ i$ iff $ |p-q$|is the element of the set $ M_i$ By Ramsey theorem,this gragh consists a triangle whose edges are of the same color,that is,$ a-b,b-c,a-c$,lie in the same $ M_x$.This prove our theorem.