Sunday, July 10, 2016

Two lessons from a simple puzzle

Suppose you're given a set of fifteen integers for a puzzle:

$A = \{ 1, 3, 7, 11, 19, 23, 35, 37, 41, 43, 57, 59, 61, 67, 71\}.$

The puzzle is to add six of these numbers to make up $101$.

Take a moment to try to solve it.

Ready to proceed?

Before we get to the puzzle, one of the people along the chain that brought me this puzzle said that there were "hundreds of combinations."

True. There are indeed fifty "hundred combinations" (plus five), since $\left(15 \atop 6\right) = 5005$.

Apparently a number of children and adults had been searching for the solution and someone thought that writing a search program would be a good idea; they didn't know how to do it, though, since none of them were programmers. Personally, I'd do it in Prolog, since tree searches are so easy to program in it.


Except that all the numbers in $A$ are odd, as is $101$. And a sum of six odd numbers is necessarily an even number. The problem has no solution.
PROOF: Each number we pick, $n_i \in A$, is odd so it can be written as $n_i = 2 \times k_i +1$ for $k_i$ integer; adding six of them yields 
$2\times (k_1 + k_2 + k_3+ k_4+ k_5+ k_6) + 6$, 
which is even for any $k_i$.
Some of the adults involved were primary school teachers. Who teach basic arithmetic. And apparently not one of them abstracted from the numbers long enough to see that the problem was impossible. I'm told some of them didn't want to believe there was no solution.

So, here are two lessons from this simple puzzle:

1. Understanding beats blind search.

2. Statements of "impossible" require a proof.