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,557
767
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
0
Views
1K
  • Last Post
Replies
4
Views
13K
  • Last Post
Replies
1
Views
7K
Replies
6
Views
4K
  • Last Post
Replies
6
Views
707
Replies
4
Views
795
Replies
1
Views
1K
Top