Zasada szufladkowa podciąg monotoniczny

[joasia317]

Wykaż za pomocą ZSD, że każdy \(\displaystyle{ (mn+1)}\)-wyrazowy ciąg liczb rzeczywistych zawiera \(\displaystyle{ (m+1)}\)-wyrazowy podciąg nierosnący lub \(\displaystyle{ (n+1)}\)-wyrazowy podciąg niemalejący.

[tomwanderer]

To jest bardzo pouczające zadanie i pamiętam, jak sam przez kilka dni zasypiałem później niż zwykle, bo nie dawało mi ono spokoju przed snem. Niestety w końcu nie wytrzymałem i przeczytałem rozwiązanie, ale Tobie radzę się zastanowić, bo co się zobaczy, tego nie da się odzobaczyć

Ukryta treść:    

Oznaczmy wyrazy naszego ciągu poprzez \(\displaystyle{ a_1,a_2,...,a_{mn},a_{mn+1}}\). Z każdym wyrazem możemy skojarzyć dwie liczby - powiedzmy \(\displaystyle{ u(a_k)}\) - długość podciągu niemalejącego, jaki możemy utworzyć z elementów \(\displaystyle{ a_k,a_{k+1},...,a_{mn},a_{mn+1}}\) oraz \(\displaystyle{ d(a_k)}\) - długość podciągu nierosnącego.

Załóżmy nie wprost, że \(\displaystyle{ 1\leq u(a_k) \leq n}\) oraz \(\displaystyle{ 1\leq d(a_k) \leq m}\). Wszystkich par \(\displaystyle{ (u(a_k),d(a_k))}\) jest \(\displaystyle{ mn}\). Mamy zatem \(\displaystyle{ mn+1}\) wyrazów ciągu, które umieszczamy w \(\displaystyle{ mn}\) szufladkach. Do jednej z szufladek muszą trafić co najmniej 2 wyrazy, co prowadzi do sprzeczności (dlaczego?)