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,559
773
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 on Pigeonhole principle question

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
3
Views
2K
Replies
13
Views
2K
Replies
12
Views
2K
Replies
7
Views
4K
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
1K
Top