- #1

0rthodontist

Science Advisor

- 1,230

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

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: