Combinatorics: looking for an alternative solution

It's definitely a good strategy to approach problems in a systematic way like that. It helps to have a clear understanding of what is being asked and what information is provided before diving into the calculations.
  • #1
member 587159

Homework Statement



Show that every subset with 6 elements of {1,2,3,4, ..., 9} contains 2 elements with sum 10.

I solved this (solution below) but I want to do this easier using the pidgeon hole principle.

Homework Equations



Pidgeon hole principle
Combinatorics

The Attempt at a Solution



Claim: Every subset of {1,2,3, ..., 9} has either the following number combinations in it:
(1,9),(2,8),(3,7),(4,6)

Proof:

Let A be the set with subsets with 6 elements of {1,2, ..., 9} that have (1,9) in it.
Let B be the set with subsets with 6 elements of {1,2, ..., 9} that have (2,8) in it.
Let C be the set with subsets with 6 elements of {1,2, ..., 9} that have (3,7) in it.
Let D be the set with subsets with 6 elements of {1,2, ..., 9} that have (4,6) in it.

##|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap D| - |B \cap C| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| + |B \cap C \cap D| + |A \cap C \cap D| - |A \cap B \cap C \cap D|
= 4\binom{7}{4} - 6\binom{5}{2} + 4\binom{3}{0} + 0
= 84##

But, the total amount of subsets with 6 elements is ##\binom{9}{6} = 84##. We deduce that every subset has 2 elements with sum 10.

Can someone give a hint on a good way to do this using the pidgeon hole principle? This is supposed to be an exercise that has to be solved using PHP.
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
You could put pairs that sum up to 10 into a box. Now try to select six numbers.
 
  • #3
fresh_42 said:
You could put pairs that sum up to 10 into a box. Now try to select six numbers.

What exactly do you mean?
 
  • #4
Math_QED said:
What exactly do you mean?
If you pair numbers that add up to ten, e.g. ##(2,8)## and consider the set of these pairs (box, container, whatever), then the task turns into choosing six numbers, such that no pair will end up in the set of your choice. Is this possible?
 
  • Like
Likes member 587159
  • #5
fresh_42 said:
If you pair numbers that add up to ten, e.g. ##(2,8)## and consider the set of these pairs (box, container, whatever), then the task turns into choosing six numbers, such that no pair will end up in the set of your choice. Is this possible?

Okay. Here is the new attempt:

Suppose we take 4 elements out of {1,2, ..., 9} such that the sum is not 10. This means, we selected from each pair (1.9), (2.8), (3,7), (4.6) one element and the other one can't be chosen. But then, the only possibility left is to choose a 5. If we would take a sixth element, we would need to take another number that was not yet selected from the pairs, and this is the only option left. Thus we find in every subset of 6 element 2 elements that sum up to 10.
 
  • #6
This was the idea.

As a general hint (not necessarily for you, but all students who might read this): As I saw your statement with all these sets ##A,B,C,D## I first read it to the end without checking any formulas. You wrote "pigeonhole principle", so I looked it up. I've read something about containers, so I thought about the way these containers could be shaped according to the task. This gave me "sum up to ten" for the containers, and the pairs to be in them.

I only mention this, because it is always a good idea to get an overview of a task, before starting to solve it. I usually recommend:
  1. Read it without calculating anything. Only to find out what it's about.
  2. Read it again and only write down all the information that is given. Again without calculations, but eventually with units!
  3. Determine what has to be calculated, resp. found, and which data it depends on (e.g. in case of exercises like cross-multiplication)
  4. Make sure you have all definitions correct and at hand, which might be needed.
This procedure often helps a lot to save time during tests (and homework).
 
  • #7
Math_QED said:
Okay. Here is the new attempt:

Suppose we take 4 elements out of {1,2, ..., 9} such that the sum is not 10. This means, we selected from each pair (1.9), (2.8), (3,7), (4.6) one element and the other one can't be chosen. But then, the only possibility left is to choose a 5. If we would take a sixth element, we would need to take another number that was not yet selected from the pairs, and this is the only option left. Thus we find in every subset of 6 element 2 elements that sum up to 10.

I would organise the set 1-9 as:

1, 9
2, 8
3, 7
4, 6
5

Now, pick any six of those!
 
  • Like
Likes member 587159
  • #8
PeroK said:
I would organise the set 1-9 as:

1, 9
2, 8
3, 7
4, 6
5

Now, pick any six of those!

That makes it pretty visual haha, but is equivalent to what I wrote. Anyway, thanks for your help!

fresh_42 said:
This was the idea.

As a general hint (not necessarily for you, but all students who might read this): As I saw your statement with all these sets ##A,B,C,D## I first read it to the end without checking any formulas. You wrote "pigeonhole principle", so I looked it up. I've read something about containers, so I thought about the way these containers could be shaped according to the task. This gave me "sum up to ten" for the containers, and the pairs to be in them.

I only mention this, because it is always a good idea to get an overview of a task, before starting to solve it. I usually recommend:
  1. Read it without calculating anything. Only to find out what it's about.
  2. Read it again and only write down all the information that is given. Again without calculations, but eventually with units!
  3. Determine what has to be calculated, resp. found, and which data it depends on (e.g. in case of exercises like cross-multiplication)
  4. Make sure you have all definitions correct and at hand, which might be needed.
This procedure often helps a lot to save time during tests (and homework).

Thanks for the help and hint!
 

Related to Combinatorics: looking for an alternative solution

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or elements in a specific way. It involves the study of combinations, permutations, and other methods of organizing and selecting objects.

2. Why is an alternative solution needed in combinatorics?

An alternative solution may be needed in combinatorics when the traditional methods are not applicable or when the problem is too complex to solve using traditional means. It can also provide a different perspective and approach to solving a problem.

3. How do you find alternative solutions in combinatorics?

Finding alternative solutions in combinatorics often involves creative thinking and exploring different approaches to the problem. It may also involve combining different techniques or adapting methods from other areas of mathematics.

4. What are some common alternative solutions in combinatorics?

Some common alternative solutions in combinatorics include using generating functions, applying graph theory, and using probabilistic methods. Other techniques such as recursion, symmetry, and constructive counting can also be helpful in finding alternative solutions.

5. Is it important to consider alternative solutions in combinatorics?

Yes, it is important to consider alternative solutions in combinatorics as they can provide insights and new approaches to solving problems, particularly in complex or unsolved cases. It also helps to expand our understanding of combinatorial problems and can lead to further discoveries and advancements in the field.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
544
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
979
  • Calculus and Beyond Homework Help
Replies
4
Views
832
  • Calculus and Beyond Homework Help
Replies
4
Views
1K

Back
Top