Udowodnić, że wśród dowolnych \(\displaystyle{ k+2}\) różnych liczb ze zbioru \(\displaystyle{ \{ 1,…, 3k \}}\) istnieją takie \(\displaystyle{ m}\) i \(\displaystyle{ n}\) że \(\displaystyle{ k<|m-n|< 2k}\) o ile \(\displaystyle{ k>1}\)
Niech \(\displaystyle{ \mathcal{J}}\) będzie podzbiorem zbioru \(\displaystyle{ \{1,...,3k\}}\) takim, że teza nie zachodzi. Oznacza to, że zachodzi warunek: \(\displaystyle{ (\star)\,\,}\)\(\displaystyle{ |m-n|\leq k}\) lub \(\displaystyle{ 2k\leq |m-n|}\)
dla każdych \(\displaystyle{ m,n\in \mathcal{J}}\).
Rozpatrzmy dwa przypadki: I)\(\displaystyle{ \mathcal{J}\cap \{k+1,k+2,...,2k\}\neq \emptyset}\)
Wówczas istnieje \(\displaystyle{ 1\leq i\leq k}\) takie, że \(\displaystyle{ k+i\in \mathcal{J}}\). Zauważmy, że dla każdego \(\displaystyle{ m\in \{1,2,...,3k\}}\) zachodzi \(\displaystyle{ |m-(k+i)|<2k}\)
Na mocy \(\displaystyle{ (\star)}\) mamy zatem: \(\displaystyle{ |m-(k+i)|\leq k}\)
dla każdego \(\displaystyle{ m\in \mathcal{J}}\). Stąd mamy inkluzję \(\displaystyle{ \mathcal{J}\subseteq \{i,i+1,...,2k+i-1,2k+i\}}\)
Niech \(\displaystyle{ j_0,j_1\in \mathcal{J}}\) będą najmniejszą i największą liczbą w tym \(\displaystyle{ k+2}\)-elementowym zbiorze. Zauważmy, że \(\displaystyle{ k<j_1-j_0}\), bo między \(\displaystyle{ j_0}\) i \(\displaystyle{ j_1}\) znajduje się jeszcze \(\displaystyle{ k}\)-liczb ze zbioru \(\displaystyle{ \mathcal{J}}\).
Stąd na mocy \(\displaystyle{ (\star)}\) musi być \(\displaystyle{ j_0=i,\,j_1=2k+i}\), bo tylko wtedy zachodzi \(\displaystyle{ 2k\leq j_1-j_0}\)
a precyzyjniej wówczas \(\displaystyle{ j_1-j_0=2k}\). W tej sytuacji w \(\displaystyle{ k}\)-elementowym zbiorze \(\displaystyle{ \mathcal{J}\setminus \{j_0,j_1\}=\mathcal{J}\setminus \{i,2k+i\}\subseteq \{i+1,...,2k+i-1\}}\)
istnieje liczba \(\displaystyle{ j}\) mniejsza od \(\displaystyle{ k+i}\) lub większa od \(\displaystyle{ k+i}\)(tutaj korzystamy z założenia, że \(\displaystyle{ k\geq 2}\)). Jeżeli \(\displaystyle{ i+1\leq j<k+i}\), to \(\displaystyle{ 2k>j_1-j=2k+i-j>2k+i-(k+i)=k}\)
Jeżeli \(\displaystyle{ k+i<j\leq 2k+i-1}\), to \(\displaystyle{ 2k>j-j_0=j-i>k+i-i=k}\)
W obu przypadkach otrzymujemy sprzeczność z \(\displaystyle{ (\star)}\). II)\(\displaystyle{ \mathcal{J}\cap \{k+1,k+2,...,2k\}=\emptyset}\)
Stąd mamy inkluzję \(\displaystyle{ \mathcal{J}\subseteq \{1,2,...,k\}\cup \{2k+1,...,3k\}}\)
Niech \(\displaystyle{ s_0}\) będzie największą liczbą w zbiorze \(\displaystyle{ \mathcal{J}\cap \{1,2,...,k\}}\) zaś \(\displaystyle{ s_1}\) będzie najmniejszą liczbą w zbiorze \(\displaystyle{ \mathcal{J}\cap \{2k+1,2k+2,...,3k\}}\). Wówczas \(\displaystyle{ s_1-s_0\geq 2k+1-k=k+1>k}\)
Na mocy \(\displaystyle{ (\star)}\) musi zatem zachodzić \(\displaystyle{ 2k\leq s_1-s_0}\)
czyli \(\displaystyle{ 2k+s_0\leq s_1}\). Stąd otrzymujemy, że \(\displaystyle{ \mathcal{J}\subseteq \{1,2,...,s_0\}\cup \{2k+s_0,2k+s_0+1,...,3k\}}\)
Zauważmy, że zbiór po prawej stronie inkluzji ma \(\displaystyle{ s_0+(k-s_0+1)=k+1}\)-elementów, a zatem nie może zawierać zbioru \(\displaystyle{ k+2}\)-elementowego \(\displaystyle{ \mathcal{J}}\). Znowu sprzeczność.