Pigeon Hole Principle Mathematical Preliminaries Part 3 Computability Theory by ComputeNow - October 8, 20180 Share on Facebook Share Share on TwitterTweet Share on Pinterest Share Share on LinkedIn Share Share on Digg Share Send email Mail Print Print Pigeon Hole Principle If n+1 or more objects are placed into n boxes, then there is at least one box containing two or more objects. In other words, if A and B are two sets such that |A| > |B|, then there is no one-to-one function from A to B. Theorem 1: Let n be a positive integer. Every sequence of n2 + 1 distinct real numbers contains a subsequence of length n+1 that is either increasing or decreasing. Proof. For example consider the sequence (20, 10, 9, 7, 11, 2, 21, 1, 20, 31) of 10 = 32 + 1 numbers. This sequence contains an increasing subsequence of length 4 = 3 + 1, namely (10, 11, 21, 31). The proof of this theorem is by contradiction, and uses the pigeon hole principle. Let (a1, a2,…..,an2+1) be an arbitrary sequence of n2 + 1 distinct real numbers. For each i with 1 ≤ i ≤ n2 + 1, let inci denote the length of the longest increasing subsequence that starts at ai, and let deci denote the length of the longest decreasing subsequence that starts at ai Using this notation, the claim in the theorem can be formulated as follows: There is an index i such that inci ≥ n + 1 or deci ≥ n + 1. We will prove the claim by contradiction. So we assume that inci ≤ n and deci ≤ n for all i with 1 ≤ i ≤ n2 + 1. Consider a set B = {(b,c): 1 ≤ b ≤ n, 1 ≤ c ≤n }, and think of the elements of B as being boxes. For each i with 1 ≤ i ≤ n2 + 1, the pair (inci, deci) is an element of B. So we have n2 + 1 elements (inci, deci), which are placed in the n2 boxes of B. By the pigeon hole principle, there must be a box that contains two (or more) elements. In other words, there exist two integers i and j and (inci,deci) = (incj,decj). Recall that the elements in the sequence are distinct. Hence, ai ≠ aj. We consider two cases. First assume that ai < aj . Then the length of the longest increasing subsequence starting at ai must be at least 1 + incj, because we can append ai to the longest increasing subsequence starting at aj. Therefore, inci ≠ incj which is a contradiction. The second case is when ai > aj. Then the length of the longest decreasing subsequence starting at ai must be at least 1 + decj, because we can append ai to the longest decreasing subsequence starting with aj. Therefore, deci ≠ decj, which is again a contradiction. Share this:Share on TumblrTweetWhatsAppMoreRedditTelegramPocketPrint Share on Facebook Share Share on TwitterTweet Share on Pinterest Share Share on LinkedIn Share Share on Digg Share Send email Mail Print Print