• Support PF! Buy your school textbooks, materials and every day products Here!

Counting and Pigeonhole, Incl- Excl

  • Thread starter snaidu228
  • Start date
  • #1
9
0

Homework Statement


Prove that, in any set of n + 1 positive integers (n ≥ 1) chosen from the set {1, 2, . . . 2n}, it must be that two of them are relatively prime (i.e. have no common divisor except 1). ( Hint: two consecutive integers are relatively prime. Make boxes labelled by pairs of consecutive integers. ).


Homework Equations





The Attempt at a Solution


In boxes does it mean to write:

[1,2]
[2,3]
[3,4]
[4,5]
[5,6]
[6,7]....

and i dont understand how two consecutive integers are relatively prime.
 

Answers and Replies

  • #2
33,154
4,838

Homework Statement


Prove that, in any set of n + 1 positive integers (n ≥ 1) chosen from the set {1, 2, . . . 2n}, it must be that two of them are relatively prime (i.e. have no common divisor except 1). ( Hint: two consecutive integers are relatively prime. Make boxes labelled by pairs of consecutive integers. ).


Homework Equations





The Attempt at a Solution


In boxes does it mean to write:

[1,2]
[2,3]
[3,4]
[4,5]
[5,6]
[6,7]....

and i dont understand how two consecutive integers are relatively prime.
When you post a question and no one responds, you can "bump" the post and provide additional information, but don't start another thread about the same problem.

I believe the hint means to label the boxes so they are distinct, like so...
[1,2]
[3,4]
[5,6]
[7,8]
[9,10]
[11,12]
.
.
.
[2n-1,2n]

For any two consecutive integers, one must be even and the other odd, so they can't be divisible by 2. If one is divisible by 3, the other one can't be, because they're only 1 apart. Similarly, both can't be divisible by 5, 7, 11, 13, and so on. We don't need to check 4, 6, 8, and so on, or any other multiple of 2, since one of the numbers isn't even. We also don't need to check multiples of 3, or 4, or 5, or ...
 
  • #3
329
0
Suppose d divides n and n+1.
Then d must divide (n+1) - n = 1.
So d must be plus or minus 1.
 

Related Threads for: Counting and Pigeonhole, Incl- Excl

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
6K
Replies
12
Views
856
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
6
Views
2K
Top