Struggling with Pigeonhole Principle Homework? Need Hints?

In summary, the conversation discusses two homework problems related to the pigeonhole principle. The first problem states that any subset of n+1 distinct integers between 2 and 2n (n>=2) contains a pair of integers with no common divisor. The second problem states 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 are provided for both problems, with the first problem being solved using the pigeonhole principle and the second problem being solved using a generalization of the first problem. The conversation then moves on to discussing a different homework problem about finding subsets of integers that sum to different values. The conversation ends with the
  • #1
0rthodontist
Science Advisor
1,231
0
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.
 
Last edited:
Physics news on Phys.org
  • #2
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
Oh, right, thanks for pointing that out. But that's just the same as an earlier problem and doesn't help me much.
 
Last edited:
  • #4
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.
 
  • #5
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
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).
 
Last edited:
  • #7
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?
 
  • #8
That's good 0rthodontist.

AKG said:
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.
 
  • #9
I see, thanks.
 
  • #10
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?
 
  • #11
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.
 
Last edited:
  • #12
0rthodontist said:
"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.
 
  • #13
CRGreathouse said:
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?
 
  • #14
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
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
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.
 
Last edited:
  • #17
Very nice! Then you certainly don't need 2 pages.
 
  • #18
AKG said:
If H is the largest number in your set of 16 positive integers, why would this imply the existence of H 1's?

:bugeye: 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.
 

What is the Pigeonhole Principle?

The Pigeonhole Principle is a mathematical concept that states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon. In other words, if there are more objects than there are places to put them, then at least one place must have more than one object.

How is the Pigeonhole Principle used in mathematics?

The Pigeonhole Principle is used in various areas of mathematics, such as combinatorics, number theory, and probability. It is often used to prove the existence of a solution to a problem, or to show that a certain outcome is inevitable.

Can you give an example of the Pigeonhole Principle in action?

One example of the Pigeonhole Principle is the "birthday problem," which asks how many people need to be in a room for there to be a 50% chance that two people share the same birthday. The answer is surprisingly low (23 people), and it is based on the idea that there are only 365 possible birthdays, but more than 365 people in the room.

What are some common misconceptions about the Pigeonhole Principle?

One common misconception is that the Pigeonhole Principle only applies to physical objects, when in fact it can be applied to any situation where there are more items than there are categories or options. Another misconception is that it always leads to a straightforward solution, when in reality it may require more complex reasoning and mathematical tools to fully understand and apply.

How can the Pigeonhole Principle be used in everyday life?

The Pigeonhole Principle can be applied in everyday life situations, such as organizing and categorizing items, planning events, and even solving problems in relationships or at work. By understanding the principle, we can make more efficient use of our resources and make decisions that are more logical and practical.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top