Choose subset of n+1 from 2n set

  • Thread starter xax
  • Start date
xax
26
0

Main Question or Discussion Point

Every subset of n+1 from a 2n set has a pair of numbers with gcd=1. How can I prove this?
 

Answers and Replies

39
0
Well, you can't because it's not true. For example let [tex]S = \left\{2, 4, 6, 8\right\} [/tex].
 
701
13
I think what xax meant was this:
Given is the set of integers from 1 to 2n. If you choose n+1 numbers from this set there is always a pair of numbers (among these n+1 numbers) with gcd=1.
 
Last edited:
xax
26
0
Edgardo, you're right.
 
39
0
Well that makes more sense!

Xax, given any natural number, b, what is the gcd(b, b+1)? In your subset of size n+1 must there be a pair of the form {b, b+1}?
 
xax
26
0
Thank you both, but I solved it using pigeonhole principle and the fact that gcd(n,n+1)=1
 
256
0
but the first counter example of rodigee is correct since the property this is true if and only if the set elements can be ordered sucht that the diference between consective numbers is equal to 1
 
Last edited:
cause n+1 numbers in 1..2n includes 2 consecutive ones, whose gcd is 1
 

Related Threads for: Choose subset of n+1 from 2n set

  • Last Post
Replies
2
Views
2K
Replies
1
Views
4K
  • Last Post
Replies
3
Views
3K
Replies
11
Views
5K
Replies
3
Views
2K
Replies
2
Views
2K
Replies
4
Views
3K
Replies
5
Views
3K
Top