Wallis  » Galerie » Logické hádanky

Monotonní podposloupnost - obtížnost 8.0 (původní obtížnost 8)
Uvažujte konečnou posloupnost různých celých čísel. Podposloupnost může vzniknout pouze smazaním některých čísel, přičemž pořadí zbylých čísel zůstane zachováno. Podposloupnost se nazývá monotonní, pokud jsou její prvky uspořádány vzestupně nebo sestupně.
Příklad: posloupnost 4, 6, 3, 5, 7, 1, 2, 9, 8, 10, potom 4, 6, 8, 10 je monotonní (rostoucí) podposloupnost délky 4 a 6, 5, 2 je monotonní (klesající) podposloupnost délky 3.

1) Najděte posloupnost 9 různých celých čísel, která nemá žádnou monotonní podposloupnost délky 4.

2) Ukažte, že každá taková posloupnost délky 10 musí nutně obsahovat monotonní podposloupnost délky 4.
Přidat řešení | Diskuze | Zpět
TIP: Budu rád, když mi k nevyřešeným hádankám budete posílat svá řešení. Nezapomeňte vždy uvést jméno hádanky a stručný popis, jak jste dospěli k řešení.