Różnica

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 747 razy

Różnica

Post autor: mol_ksiazkowy »

Udowodnić, że dowolny podzbiór \(\displaystyle{ \{1,...,n \}}\), który ma co najmniej \(\displaystyle{ \lfloor \frac{n+k}{2} \rfloor +1}\) elementów, ma też jakieś elementy o różnicy \(\displaystyle{ k}\).
Ostatnio zmieniony 20 kwie 2021, o 09:49 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Interpunkcja.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Różnica

Post autor: Premislav »

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.
ODPOWIEDZ