Zbiór i różnica

[mol_ksiazkowy]

Niech \(\displaystyle{ f(n)}\) będzie najmniejszą liczbą naturalną taką, że jest twierdzeniem:

Wśród dowolnych \(\displaystyle{ f(n)}\) różnych liczb ze zbioru \(\displaystyle{ \{ 1, ..., n \}}\) są takie których różnica jest równa \(\displaystyle{ 4}\)

Czy można wyznaczyć \(\displaystyle{ f(n)}\) ?

[Slup]

Lemat. Niech \(\displaystyle{ n}\) będzie liczbą naturalną. Wówczas wśród \(\displaystyle{ \left[ \frac{n}{2}\right]+1}\) różnych elementów zbioru \(\displaystyle{ \{1,2,...,n\}}\) istnieją dwa, które różnią się o \(\displaystyle{ 1}\). Istnieje też podzbiór zbioru \(\displaystyle{ \{1,2,...,n\}}\), który ma \(\displaystyle{ \left[ \frac{n}{2}\right]}\) elementów i żadne dwa elementy nie różnią się o \(\displaystyle{ 1}\).
dowód. Książka z matematyki dyskretnej. Jest to też łatwe i pożyteczne ćwiczenie. Każdy to w życiu robił albo powinien zrobić.

Niech \(\displaystyle{ k}\) będzie liczbą całkowitą dodatnią.
I przypadek. Mamy równość \(\displaystyle{ f(4k)=4\cdot \left[ \frac{k}{2}\right] +1}\).
Zauważmy, że zbiór \(\displaystyle{ \{1,2,...,4k\}}\) można rozbić na cztery ciągi arytmetyczne długości \(\displaystyle{ k}\) tzn.
\(\displaystyle{ \{4s\mid 1\leq s\leq k\}}\), \(\displaystyle{ \{4s+1\mid 0\leq s\leq k-1\}}\), \(\displaystyle{ \{4s+2\mid 0\leq s\leq k-1\}}\), \(\displaystyle{ \{4s+3\mid 0\leq s\leq k-1\}}\)
Jeżeli ze zbioru \(\displaystyle{ \{1,2,...,4k\}}\) wybraliśmy \(\displaystyle{ 4\cdot \left[ \frac{k}{2}\right] +1}\) różnych elementów, to z jednego z tych ciągów wybraliśmy \(\displaystyle{ \left[ \frac{k}{2}\right] +1}\) różnych elementów i na mocy Lematu w wybraliśmy w szczególności dwa sąsiednie wyrazy tego ciągu.
Ponadto Lemat orzeka, że możemy z każdego z tych czterech ciągów wybrać \(\displaystyle{ \left[ \frac{k}{2}\right]}\) różnych wyrazów w taki sposób, żeby żadne dwa nie były sąsiednie. Dzięki temu dostaniemy \(\displaystyle{ 4\cdot \left[ \frac{k}{2}\right]}\) elementów zbioru \(\displaystyle{ \{1,2,...,4k\}}\), z których żadne dwa nie różnią się o \(\displaystyle{ 4}\).
II przypadek. Mamy równość \(\displaystyle{ f(4k+1)=3\cdot \left[ \frac{k}{2}\right] +\left[ \frac{k+1}{2}\right]+1}\).
III przypadek. Mamy równość \(\displaystyle{ f(4k+2)=2\cdot \left[ \frac{k}{2}\right] +2\cdot \left[ \frac{k+1}{2}\right]+1}\).
IV przypadek. Mamy równość \(\displaystyle{ f(4k+3)= \left[ \frac{k}{2}\right] +3\cdot \left[ \frac{k+1}{2}\right]+1}\).