Mariolys's Monotonic Subsequences

Discrete Mathematics Level 5

Mariolys is creating a numbered list of distinct integers. Luigis sees that there are \(N\) numbers in the list, and states that he can find either a subsequence of length 13 with increasing terms or a subsequence of length 17 with decreasing terms. What is the minimum value of \(N\) for Luigis' claim to be true?

Details and assumptions

You may choose to refer to an explanation of the Pigeonhole Principle.

Luigis doesn't know the numbers on Mariolys list.

The chosen terms of the subsequence need not be consecutive. In the list \( \{ 1, 45, 23, 56, 25, 58, 8, 2 \}\), we have an increasing subsequence of length 4 formed by \( 1, 23, 25, 58\) (which are the 1st, 3rd, 5th and 7th terms of the original list). We also have a decreasing subsequence of length 4 formed by \( 56, 25, 8, 2\) (which are the 4th, 5th, 7th and 9th terms of the original list).


Problem Loading...

Note Loading...

Set Loading...