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

Pigeonhole principle question

  • 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



pigeonhole

The Attempt at a Solution

 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,517
733
That's a pretty good hint. What have you tried or what ideas do you have? We aren't here to work it for you.
 

Related Threads for: Pigeonhole principle question

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
989
Replies
13
Views
1K
Replies
12
Views
823
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
8
Views
1K
Top