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:
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).
1 answer
You must be taking a test or something. Please understand that tutors won't do your work for you. You need to indicate exactly what you have done to solve each problem and where you're running into trouble.