Feladat: 16.21.
** Bizonyítsuk be, hogy egy
nk+1 tagú sorozatban vagy van
n+1 szám, amelyek a sorozatbeli sorrendjükben szigorúan monotonan növekednek, vagy van
k+1 szám, amelyek a sorozatbeli sorrendjükben monotonan csökkennnek. (Erdős Pál, Szekeres György, vö. [
173], 240. oldal.)
Megoldás: 16.21
A sorozat minden tagja mellé képzeletben odaírjuk, hogy mekkora a leghosszabb, vele kezdődő szigorúan monoton növekvő sorozat.
Nyilvánvaló, hogy ha a sorozat két tagja mellé ugyanaz a szám kerül, akkor közülük a korábbi nem kisebb a későbbinél. Másrészt az is nyilvánvaló, hogy ha valamelyik tag mellé az
n+1 (vagy annál nagyobb) szám kerül, akkor kész vagyunk: van
n+1 tagú szigorúan monotonan növekvő sorozat. Ha viszont minden szám mellé az
1,2,…,n számok valamelyik kerül, akkor van a sorozatnak
k+1 tagja, amelyek mellé ugyanaz a szám kerül. Ezek viszont az előbb mondottak szerint egy monoton csökkenő sorozatot alkotnak.