1

In any set consisting of exactly 7 different numbers chosen from the first 9 positive whole numbers, there are always 3 different numbers whose sum is 15. Is this true or false?

There's a follow-up question that asks if the same is true when we choose only 6 different numbers. In class, we showed the follow-up question was false by using the counter-example 1,9,6,7,3,4, and apparently, the question I've listed above (when we use 7 numbers) is true.

I'm not sure how to go about proving the first question (We're working on pigeon-hole in class, so I assume we'll have to somehow show that 6 of the numbers we choose will not produce 15 when added to two others from the group but when a 7th is chosen they will), and for the second, I was wondering if there was a more rigorous way to prove it as opposed to just randomly looking for a counter-example.

Thanks.

Questioneer
  • 57
  • Looking for a counter-example is usually the best way to prove something is not true. Usually the counter-example that you find gives you insight into why the claim is not true. – Mike Pierce Jan 05 '15 at 18:13

2 Answers2

3

The answer to the first question is affirmative: $(8,3,4),(9,1,5),(2,6,7)$

Asinomás
  • 105,651
  • I realize the answer can seem cryptic, this is on purpose, try to use what I wrote, I'll be here if you can't. – Asinomás Jan 05 '15 at 18:10
  • Perhaps a few words connecting this with a pigeonhole argument would be in order, since the Question asks for an argument of that type? – hardmath Jan 05 '15 at 18:12
  • So if I pick numbers from the three groups you gave me such that I would get the worst-case distribution, I'd end up with 8,9,2,3,1,6... and if I picked a 7th number, I'd have to end up back in the first group picking 4, which would give me 8+3+4=15.

    How did you come up with (8,3,4),(9,1,5),(2,6,7) though? I realize that these combinations all give you 15, but there are other ones that do the same thing, such as (1,6,8). Did you just want to create enough groups so that you covered all the numbers from 1-9 once and only once, and how'd you get the ones in your answer?

     – Questioneer Jan 05 '15 at 18:17
  • Well, when the ones in my answer I got just by luck, but there is a better way to do it. break the numbers ${1,2,3,4\dots 9}$ into three parts ${1,2,3},{4,5,6},{7,8,9}$ and to each of the three parts you are going to create give a small number, a middle number and a large number from the three sets. – Asinomás Jan 05 '15 at 18:21
  • 1
    You might do the same thing with (1, 6, 8), (2, 4, 9), (3, 5, 7), for example. :) – Brandon Humpert Jan 05 '15 at 18:21
  • 1
    My Idea on using that for the proof is that if you choose $7$ out of $9$ it is the same as taking away two numbers. But no matter which two you take at least one of the numbers in the parenthesis will stay complete, so the numbers in the parenthesis add $15$. – Asinomás Jan 05 '15 at 18:22
  • Okay, thanks for the explanation! I find it a bit difficult to apply pigeon-hole to the variety of questions we get in class, and sometimes, we don't even get very good explanations about our results xD – Questioneer Jan 05 '15 at 18:26
  • 1
    An application of the general pigeonhole principle here is that if you put $7$ pigeons in $3$ holes then there must be at least $3$ pigeons in at least one of the holes (because $7>2\cdot3$); therefore if you must make $7$ choices from among $3$ sets of numbers you must choose at least $3$ numbers from at least one of the sets--which in this case means you must choose all the numbers from one of the sets. – David K Jan 05 '15 at 18:57
2

HINT: Consider this $3\times 3$ magic square:

$$\begin{array}{c|c|c} \color{brown}8&\color{brown}1&6\\ \hline \color{brown}3&5&\color{brown}7\\ \hline 4&\color{brown}9&\color{brown}2 \end{array}$$

The six brown cells are significant, as is the square itself.

Brian M. Scott
  • 616,228