- #1
life is maths
- 38
- 0
Hi, I love the pigeonhole principle subject, but the problem is I'm not very sharp to solve questions easily. I'm stuck with this one:
Show that in any set of n+1 positive integers not exceeding 2n, there must be two that are relatively prime.
I tried mathematical induction, but I couldn't finish it. Say n=2, and we have n+1= 3 integers not exceeding 2n=4. It is 1, 2 and 3. It's okay for the base case. Then let's assume it holds for n=k, integers smaller than 2k. Then we add another number so that we have k+1 numbers and they are smaller than 2k+2. How can I prove that those numbers are relatively prime? Is there an easier and more practical way to solve this? Thank you for any help.
Show that in any set of n+1 positive integers not exceeding 2n, there must be two that are relatively prime.
I tried mathematical induction, but I couldn't finish it. Say n=2, and we have n+1= 3 integers not exceeding 2n=4. It is 1, 2 and 3. It's okay for the base case. Then let's assume it holds for n=k, integers smaller than 2k. Then we add another number so that we have k+1 numbers and they are smaller than 2k+2. How can I prove that those numbers are relatively prime? Is there an easier and more practical way to solve this? Thank you for any help.