Podzielmy z resztą
\(\displaystyle{ n}\) przez
\(\displaystyle{ k}\):
\(\displaystyle{ n=kp+q, \ p,q\in \ZZ, \ 0\le q<k}\)
Podzielmy zbiór
\(\displaystyle{ \left\{1,2\ldots n\right\}}\) na klasy abstrakcji, do tego samego worka trafiają liczby dające te same reszty z dzielenia przez
\(\displaystyle{ k}\). Mamy
\(\displaystyle{ q}\) worków o mocy
\(\displaystyle{ p+1}\) i
\(\displaystyle{ k-q}\) takich, w których jest dokładnie
\(\displaystyle{ p}\) elementów. W skład podzbioru
\(\displaystyle{ X\subset\left\{1,2\ldots n\right\}}\) bez elementów różniących się o
\(\displaystyle{ k}\) może wejść najwyżej
\(\displaystyle{ \left\lfloor \frac{p+2}{2}\right\rfloor }\) elementów klasy abstrakcji mocy
\(\displaystyle{ p+1}\) i co najwyżej
\(\displaystyle{ \left\lfloor \frac{p+1}{2}\right\rfloor }\) elementów z klasy abstrakcji mocy
\(\displaystyle{ p}\) (nic skomplikowanego, możemy wziąć najwyżej co drugi element, bo sąsiadujące różnią się o
\(\displaystyle{ k}\)).
Jeśli zatem wybierzemy co najmniej
\(\displaystyle{ q\left\lfloor\frac{p+2}{2}\right\rfloor+(k-q)\left\lfloor \frac{p+1}{2}\right\rfloor+1}\) elementów
\(\displaystyle{ \left\{1,2\ldots n\right\rfloor}\), to znajdą się wśród nich różniące się dokładnie o
\(\displaystyle{ k}\). Pozostaje więc wykazać, że
\(\displaystyle{ q\left\lfloor\frac{p+2}{2}\right\rfloor+(k-q)\left\lfloor \frac{p+1}{2}\right\rfloor+1\le \left\lfloor \frac{n+k}{2}\right\rfloor+1 \ (*)}\)
Nie mam na to żadnej sprytnej metody.
Rozpisałem po prostu cztery przypadki w zależności od parzystości
\(\displaystyle{ p}\) i
\(\displaystyle{ n+k}\).
\(\displaystyle{ 1^{\circ}}\) jeśli
\(\displaystyle{ 2|p, \ 2|(n+k)}\), to nierówność
\(\displaystyle{ (*)}\) sprowadza się do
\(\displaystyle{ q+\frac{kp}{2}\le \frac{n+k}{2}}\)
a pamiętając, że
\(\displaystyle{ kp+q=n}\), redukujemy to do oczywistej nierówności
\(\displaystyle{ q\le k}\)
\(\displaystyle{ 2^{\circ}}\) jeśli
\(\displaystyle{ 2\nmid p, \ 2\nmid(n+k)}\), to nierówność
\(\displaystyle{ (*)}\) przyjmuje postać
\(\displaystyle{ \frac{k(p+1)}{2}\le \frac{n+k-1}{2} }\)
czyli
\(\displaystyle{ kp\le n-1}\), co również jest niemal oczywiste, jako że
\(\displaystyle{ kp+q=n, \ q\ge 0}\)
Istotna uwaga: w tym przypadku nie może być
\(\displaystyle{ q=0}\), wszak wtedy byłoby
\(\displaystyle{ n=kp}\), a skoro
\(\displaystyle{ 2\nmid p}\), to wobec tego
\(\displaystyle{ n,k}\) miałyby tę samą parzystość, co sprzeczne z
\(\displaystyle{ 2\nmid(n+k)}\).
\(\displaystyle{ 3^{\circ}}\) jeśli
\(\displaystyle{ 2\nmid p, \ 2|(n+k)}\), to nierówność
\(\displaystyle{ (*)}\) tak się przedstawia, po zredukowaniu jedynek:
\(\displaystyle{ \frac{k(p+1)}{2} \le \frac{n+k}{2}}\)
a to jest równoważne oczywistemu
\(\displaystyle{ kp\le n}\) (wszak
\(\displaystyle{ n=kp+q}\)).
\(\displaystyle{ 4^{\circ}}\) jeżeli
\(\displaystyle{ 2|p, \ 2\nmid(n+k)}\), to dowodzona nierówność sprowadza się do
\(\displaystyle{ q+\frac{kp}{2}\le \frac{n+k-1}{2}}\)
a po wykorzystaniu z zależności
\(\displaystyle{ kp+q=n}\) redukuje się to do
\(\displaystyle{ q\le k-1}\), co jest jasne.
Pewnie jest jakaś prosta własność podłóg, która umożliwia ominięcie rozpisywania tych przypadków, ale ja już sporo zapomniałem z matmy.