Register to reply

Pigeonhole principle

by 0rthodontist
Tags: pigeonhole, principle
Share this thread:
0rthodontist
#1
Sep10-06, 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 help--here 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 plausible--one 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.
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
Muzza
#2
Sep10-06, 01:47 AM
P: 696
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...
0rthodontist
#3
Sep10-06, 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.

AKG
#4
Sep10-06, 04:04 AM
Sci Advisor
HW Helper
P: 2,586
Pigeonhole principle

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.
There are only 2n-1 numbers to choose from. Suppose every number chosen, except the last one, has a gap after it, i.e. no two adjacent numbers are chosen. You could only get n numbers chosen, but you have to choose n+1, so this is impossible. Thus there must be at least one pair of adjacent numbers. This pair will have no common divisor, by elementary number theory.
shmoe
#5
Sep10-06, 08:40 AM
Sci Advisor
HW Helper
P: 1,995
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.
0rthodontist
#6
Sep10-06, 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 n-1 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 equal-length increasing subsequences).
AKG
#7
Sep10-06, 06:06 PM
Sci Advisor
HW Helper
P: 2,586
Okay, so by your argument you get n+1 increasing subsequences of the same length k.
How do you know you get n+1 increasing subsequences of this maximum length k?
shmoe
#8
Sep10-06, 06:10 PM
Sci Advisor
HW Helper
P: 1,995
That's good 0rthodontist.

Quote Quote by AKG
How do you know you get n+1 increasing subsequences of this maximum length k?
Pigeonhole principle, you have n "holes" (the possible sequence lengths) and n^2+1 "pigeons", so at least one hole has n+1 or more pigeons.
AKG
#9
Sep10-06, 06:44 PM
Sci Advisor
HW Helper
P: 2,586
I see, thanks.
0rthodontist
#10
Sep14-06, 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 non-1 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?
AKG
#11
Sep14-06, 06:57 PM
Sci Advisor
HW Helper
P: 2,586
Assume 14 < n < 30. Make boxes labelled 16-n to 30-n. Let Si be the set of the first i elements. Let si be the sum of the elements of Si. If si is less than or equal to 30-n, put Si in the box labelled si. Otherwise, put it in the box labelled si-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 Si, with si = the box label, and one subset Sj with sj-n = the box label, with Sj containing Si, obviously. So Sj - Si is a subset whose elements have sum n. The complement of this set with respect to the full set of 16 elements has sum 30-n.

You can probably express the above in 4 lines if you're especially terse.
CRGreathouse
#12
Sep14-06, 07:15 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by 0rthodontist
"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."
That's poorly written. (1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2) sum to 30, but none of the subsets {}, {1}, {2}, {1, 2} sum to n > 3. The subset should be over the indices, not the elements.


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 30-H..29 by taking out 1s, so you need only consider 2H+1..29-H.

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.
AKG
#13
Sep14-06, 07:29 PM
Sci Advisor
HW Helper
P: 2,586
Quote Quote by CRGreathouse
Call the highest element H. You can sum to 1..H with 1s
What makes you think there are H 1's?
so you need only consider 2H+1..29-H.
Assuming, falsely, that there were H 1's, you would only need to conisder 2H+1 to 29-2H.
If H >= 10 you're done.
So, under that false assumption, you'd be done if H > 7.
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.
The last number you add could also equal H, i.e. it's not necessarily less than H. Nonetheless, you can still replace the last added number n, whether it's H or less, by n 1's and then remove 1's until you reach your target. Again, however, this only holds under the assumption that there are H 1's.

If H is the largest number in your set of 16 positive integers, why would this imply the existence of H 1's?
0rthodontist
#14
Sep14-06, 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?
AKG
#15
Sep14-06, 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?
0rthodontist
#16
Sep14-06, 08:54 PM
Sci Advisor
P: 1,253
Oh, well it's still pretty smooth.

Anyway if you take out H, then you have 30-H 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.
AKG
#17
Sep14-06, 09:02 PM
Sci Advisor
HW Helper
P: 2,586
Very nice! Then you certainly don't need 2 pages.
CRGreathouse
#18
Sep15-06, 11:06 AM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by AKG
If H is the largest number in your set of 16 positive integers, why would this imply the existence of H 1's?
It's a simple application of the pidgeonhole principle. You have 15 numbers which must sum to 30-H. This gives you 15-H to apply as desired, since all must be at least 1. Thus at least 15-(15-H)=H must be 1.

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