Skip to content
Get started

Forcing a monotone subsequence

MediumCombinatorics5 min

What is the smallest NN such that every sequence of NN distinct real numbers is guaranteed to contain a subsequence of length 55 (not necessarily consecutive) that is either strictly increasing or strictly decreasing?

Show hints (3)+
  1. Attach to each term the longest increasing and decreasing subsequences ending there.
  2. Why must two different terms get different label pairs?
  3. Build a 16-term example out of decreasing blocks.

Answer

Reveal answer →

17

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Systematic & Data-Driven Trading

Related questions