Combinatorics: looking for an alternative solution

[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.

 

[fresh_42]

You could put pairs that sum up to 10 into a box. Now try to select six numbers.

 

[member 587159]

You could put pairs that sum up to 10 into a box. Now try to select six numbers.

What exactly do you mean?

 

[fresh_42]

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?

 

[member 587159]

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.

 

[fresh_42]

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).

 

[PeroK]

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!

 

[member 587159]

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!

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!