Register to reply 
Pigeonhole principle 
Share this thread: 
#1
Sep1006, 12:35 AM

Sci Advisor
P: 1,253

I'm having trouble with some homework problems related to the pigeonhole principle. This HW is solitary work, but some more examples might helphere are some unassigned problems I haven't been able to do:
Show that any subset of n+1 distinct integers between 2 and 2n (n >= 2) always contains a pair of integers with no common divisor. Show that any sequence of n^2 + 1 distinct numbers contains an increasing subsequence of n+1 numbers or a decreasing subsequence of n+1 numbers. Hints? I have no idea how to start the first one (I hope it does not require much number theory, a course I haven't had). In the second one I have a vague notion that it has to do with dropping numbers into potentially increasing or decreasing subsequences. I can find a sequence that makes it plausibleone consisting of n contiguous subsequences of length n, such that each subsequence is monotone increasing and whose greatest number is smaller than the smallest number of the previous subsequence. This makes up n^2 numbers, and the final number you place must either allow one of the monotone increasing subsequences to be of length n+1, or it must allow the sequence consisting of the greatest numbers in each monotone increasing subsequence to be monotone decreasing of length n+1. 


#2
Sep1006, 01:47 AM

P: 695

For the first problem, you can actually prove something much stronger.
Suppose you were given a set S of n + 1 numbers between 2 and 2n. Write the numbers 2, ..., 2n in "matrix", like so: 2, 3 4, 5 ... (2n  1), (2n  2) 2n. Now, put some kind of mark on the numbers which are in S... 


#3
Sep1006, 02:24 AM

Sci Advisor
P: 1,253

Oh, right, thanks for pointing that out. But that's just the same as an earlier problem and doesn't help me much.



#4
Sep1006, 04:04 AM

Sci Advisor
HW Helper
P: 2,586

Pigeonhole principle



#5
Sep1006, 08:40 AM

Sci Advisor
HW Helper
P: 1,994

For the second, try considering the length of the longest increasing subsequence starting at the ith position. If any of these is n+1 you're done, otherwise use the pigeon hole to get a bunch that have the same maximimum length and see what you can do from there.
You can generalize this, if you have a sequence of any numbers longer than lmn, then there is either an increasing sequence of length greater than l, or a decreasing sequence of length greater than m, or a constant sequence of length greater than n. Your version takes this n=1 and has assumed the last case isn't true. You should try to prove your special case first, then this more general one. 


#6
Sep1006, 04:30 PM

Sci Advisor
P: 1,253

Okay, so by your argument you get n+1 increasing subsequences of the same length k. The first points of these form a decreasing subsequence of length n+1, since if the sequence any first point P were greater than its value at an earlier first point Q, then you could choose the points consisting of Q followed by the maximum increasing subsequence after P to get an increasing subsequence of length k+1 starting on Q.
In your second one, assume there is no constant sequence of length greater than n. Then form a new subsequence S by excluding all numbers such that an earlier number equals them. Since for each point in S you excluded at most n1 points from the original sequence, the size of S is greater than lm. Then if there is no increasing subsequence in S of length greater than l, you can find more than m points whose maximum increasing subsequences have the same length. Then by the argument above you have a decreasing subsequence of length more than m (consisting of the first points of the equallength increasing subsequences). 


#7
Sep1006, 06:06 PM

Sci Advisor
HW Helper
P: 2,586




#8
Sep1006, 06:10 PM

Sci Advisor
HW Helper
P: 1,994

That's good 0rthodontist.



#9
Sep1006, 06:44 PM

Sci Advisor
HW Helper
P: 2,586

I see, thanks.



#10
Sep1406, 06:36 PM

Sci Advisor
P: 1,253

Well, the homework has been passed in now. The question that I was having trouble with was this:
"Show that if 16 positive integers (not all distinct) sum to 30, some subset of the integers sums to n for n = 1, 2, ... 29." The way I solved it was to first prove that if x is an integer in the set, then the set contains at least x ones. Then I gave an algorithm that fills up to n with arbitrary integers in the set that are not one. If the algorithm goes over n, then you had at least as many ones as the number that caused it to go over n, so you can make exactly n that way. Of course, if the algorithm falls short of n with non1 integers, then all the unused elements are 1 and you can reach n that way also. This proof ran about two handwritten pages. However, the professor mentioned that he was able to solve it by breaking it up into a few cases, and he said his proof was about four lines. This was on Tuesday and he didn't give his proof today, so I'm wondering, what is it? 


#11
Sep1406, 06:57 PM

Sci Advisor
HW Helper
P: 2,586

Assume 14 < n < 30. Make boxes labelled 16n to 30n. Let S_{i} be the set of the first i elements. Let s_{i} be the sum of the elements of S_{i}. If s_{i} is less than or equal to 30n, put S_{i} in the box labelled s_{i}. Otherwise, put it in the box labelled s_{i}n. There are 15 boxes, and 16 subsets, so at least one box has two subsets. Clearly, a box with two subsets must have one, say S_{i}, with s_{i} = the box label, and one subset S_{j} with s_{j}n = the box label, with S_{j} containing S_{i}, obviously. So S_{j}  S_{i} is a subset whose elements have sum n. The complement of this set with respect to the full set of 16 elements has sum 30n.
You can probably express the above in 4 lines if you're especially terse. 


#12
Sep1406, 07:15 PM

Sci Advisor
HW Helper
P: 3,684

Here's my proof. It's not what your professor wrote, I imagine, since it's not exactly by cases, but it is less than 2 pages. Call the highest element H. You can sum to 1..H with 1s, H..2H with H and the 1s, and 30H..29 by taking out 1s, so you need only consider 2H+1..29H. If H >= 10 you're done. Otherwise, add up the highest numbers until you exceed the target number. The last number you add will be less than H by definition. Call this number n. Replace it with n 1s, then remove them one by one untilyou hit the target number. 


#13
Sep1406, 07:29 PM

Sci Advisor
HW Helper
P: 2,586

If H is the largest number in your set of 16 positive integers, why would this imply the existence of H 1's? 


#14
Sep1406, 07:52 PM

Sci Advisor
P: 1,253

CRGreathouse, that's the basic form of the proof I used (and just explained), except you don't need to reduce the cases, you can just argue from 1's. It came out to 2 pages, maybe I included more detail than I needed.
It is true though that you must have H 1's, though I used half a page to show that. The intuitive idea is that if you take out H, then you have 15  H "tokens of 1" to distribute among 15 numbers where each already has a "token." AKG, I am blown away. I suspect it took me longer to understand that than it took you to write it. How did you come up with that? 


#15
Sep1406, 08:29 PM

Sci Advisor
HW Helper
P: 2,586

I actually didn't come up with that proof, and every time I see it actually takes me some time to understand it too. It's quite clever though, I wish I had come up with it. It was a problem given in my Combinatorial Methods course at the University of Toronto last year.
Could you elaborate on why you must have H 1's? 


#16
Sep1406, 08:54 PM

Sci Advisor
P: 1,253

Oh, well it's still pretty smooth.
Anyway if you take out H, then you have 30H tokens that are 1 (+1 tokens, so if a number gets 3 tokens then that number equals 3) to distribute among the 15 remaining numbers in the set. But each number is at least 1, so you distribute 15 of the tokens to make each at least one, so you have 15 numbers that are 1 and you want to distribute 15  H tokens. So H of the 15 numbers must not get any more tokens, so those must be 1. Formally let T = the set of numbers other than H, let y = the number of ones in T, and let S = the sum of the elements of T. So T contains 15  y elements of at least two, so S >= 2 * (15  y) + y = 30  y. But since S = 30  H, 30  H >= 30  y, so y >= H. 


#17
Sep1406, 09:02 PM

Sci Advisor
HW Helper
P: 2,586

Very nice! Then you certainly don't need 2 pages.



#18
Sep1506, 11:06 AM

Sci Advisor
HW Helper
P: 3,684

Since 0rthodontist already proved that, I didn't want to duplicate effort by explaining it. 


Register to reply 
Related Discussions  
Pigeonhole principle and counting  Engineering, Comp Sci, & Technology Homework  1  
A pigeonhole problem  Set Theory, Logic, Probability, Statistics  4  
Pigeonhole principle  Calculus & Beyond Homework  12  
Combinatorics  Pigeonhole Principle  Calculus & Beyond Homework  13  
Concept of the pigeonhole principle  Set Theory, Logic, Probability, Statistics  5 