Quiz 2 10 Problem 6. [15 points] A subsequence is obtained from a sequence by deleting one or more terms. For example, the sequence(1, 2, 3, 4, 5)contains(2, 4, 5) as a subsequence Theorem. Every sequence of n2+ 1 distinct integers contains an increasing or decreasing subse- quence of length n+1 For example, in the 3+1= 10 term sequence(5,6,1, 4, 9, 0, 2, 7, 8, 3), the underlined terms increasing sequence of length 3+1=4. Fill in the outline of a proof provided OW Proof (a)label each term in the sequence with the length of the longest increasing subse quence that ends with that term. For example, here is a sequence with the corre- ponding labels listed below. 121口□口口□□ Solution 2,1,2,2,3,1,3,2,3 (b) Now there are two cases. If some term is labeled n+l or higher, then the theorem is true because Solution. this means there is an increasing sequence of length at least n+1 that ends with that term (c)Otherwise, at least n+ 1 terms must have the same label b E 1, 2 Solution. of the Pigeonhole Principle. Regard the labels a pigeons and the numbers 1, 2,..., n as pigeonholes. Assign each label to its value. Since there are n2+1 pigeons and only n pigeonholes, some n+ I pigeons must be assigned to some hole (d ) The theorem is also true in this case because Solution. Each of the n l terms labeled b must be smaller than the one befo (Otherwise, a term labeled b could be appended to the length-b increasing sequence that ends at its predecessor to obtain a length-(6+ 1)increasing sequence. But then the term should actually be labeled b+ 1. ) Therefore, the n+ l terms labeled b form a decreasing subsequence� Quiz 2 10 Problem 6. [15 points] A subsequence is obtained from a sequence by deleting one or more terms. For example, the sequence (1, 2, 3, 4, 5) contains (2, 4, 5) as a subsequence. Theorem. Every sequence of n2 + 1 distinct integers contains an increasing or decreasing subse￾quence of length n + 1. For example, in the 32+1 = 10 term sequence (5, 6, 1, 4, 9, 0, 2, 7, 8, 3), the underlined terms form an increasing sequence of length 3 + 1 = 4. Fill in the outline of a proof provided below. Proof. (a) Label each term in the sequence with the length of the longest increasing subse￾quence that ends with that term. For example, here is a sequence with the corre￾ponding labels listed below. ( 2, 6, 1, 5, 4, 9, 0, 8, 3, 7 ) 1 2 1 Solution. 1, 2, 1, 2, 2, 3, 1, 3, 2, 3 (b) Now there are two cases. If some term is labeled n+1 or higher, then the theorem is true because Solution. this means there is an increasing sequence of length at least n + 1 that ends with that term. (c) Otherwise, at least n + 1 terms must have the same label b ∈ {1, 2, . . . , n} because Solution. of the Pigeonhole Principle. Regard the labels a pigeons and the numbers 1, 2, . . . , n as pigeonholes. Assign each label to its value. Since there are n2 + 1 pigeons and only n pigeonholes, some n + 1 pigeons must be assigned to some hole b. (d) The theorem is also true in this case because Solution. Each of the n + 1 terms labeled b must be smaller than the one before. (Otherwise, a term labeled b could be appended to the length­b increasing sequence that ends at its predecessor to obtain a length­(b + 1) increasing sequence. But then the term should actually be labeled b + 1.) Therefore, the n + 1 terms labeled b form a decreasing subsequence