Matematické Fórum

2) postupujme indukcí, řekněme, že pro k už jsme takové N(k) našli a hledejme N(k+1) pro k+1. Ukažme, že N(k+1)=N(k)(N(k)+1) stačí. Máme tak N(k)+1 bloků tvořených N(k) prvky. Z prvního bloku vybereme monotoónní (BÚNO nerostoucí) posloupnost délky k. Kdybychom pak z nějakého dalšího bloku vybrali neklesající posloupnost délky k, měli bychom vyhráno (porovnáním posledního prvku nerostoucí a prvního prvku neklesající posloupnosti docházíme k tomu, že v obou případech lze jednu posloupnost protáhnout). Pokud se nám toto nepovede, víme, že z každého bloku vybereme posloupnost nerostoucí. Vybrali jsme tedy k+1 nerostoucích posloupností, snadno ale nahlédneme, že jejich poslední prvky musí tvořit neklesající posloupnost délky k+1.