Choose subset of n+1 from 2n set

  • Thread starter xax
  • Start date
  • Tags
    Set
In summary, the conversation discusses a statement that every subset of n+1 numbers from a set of 2n numbers has a pair of numbers with a greatest common divisor of 1. However, it is proven that this statement is not always true. The conversation also mentions the use of the pigeonhole principle and the fact that the greatest common divisor of two consecutive numbers is always 1.
  • #1
xax
26
0
Every subset of n+1 from a 2n set has a pair of numbers with gcd=1. How can I prove this?
 
Physics news on Phys.org
  • #2
Well, you can't because it's not true. For example let [tex]S = \left\{2, 4, 6, 8\right\} [/tex].
 
  • #3
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:
  • #4
Edgardo, you're right.
 
  • #5
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}?
 
  • #6
Thank you both, but I solved it using pigeonhole principle and the fact that gcd(n,n+1)=1
 
  • #7
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:
  • #8
cause n+1 numbers in 1..2n includes 2 consecutive ones, whose gcd is 1
 

1. What is a subset?

A subset is a collection of elements from a larger set, where the elements in the subset are also present in the larger set.

2. How do you choose a subset from a set?

To choose a subset from a set, you must select a specific number of elements from the larger set and create a collection that only contains those elements.

3. What does "n+1" represent in this context?

In this context, "n+1" represents the number of elements in the subset, which is one more than the number of elements in the original set.

4. Why is the number of elements in the subset one more than the original set?

This is because when choosing a subset from a set, at least one element must be added to the subset in order for it to be a proper subset. Otherwise, the subset would be equivalent to the original set.

5. How many possible subsets can be chosen from a set with 2n elements?

There are 2^n possible subsets that can be chosen from a set with 2n elements. This is because for each element in the set, you have two options: to include or not include it in the subset. Therefore, the total number of possible combinations is 2^2n, which simplifies to 2^n.

Similar threads

  • Linear and Abstract Algebra
Replies
6
Views
755
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
816
  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
881
  • Linear and Abstract Algebra
Replies
8
Views
855
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
3
Views
355
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
Back
Top