In the puzzle
Magic Trick
we are asked to find five numbers that a magician
has put on each of three cards such that adding any three of these numbers
yields a unique sum. The sum is always unique in the sense that it allows
the magician to say which three numbers were chosen.
In a simpler version
of the problem, the same five numbers have been written on each card, so, an individual number may be added more than once. Each sum is unique, and we are asked to find
the numbers that allow the trick to work and also give the minimum sum of all
possible sums.
The answer is (1, 2, 5, 16, 25) with a sum of all sums of 1029.
The next closest answer is (1, 2, 5, 17, 27) with a sum of sums of 1092,
and the next is 1, 3, 6, 15, 26 with a sum of 1113.
Another non-optimal
answer is (3, 6, 7, 16, 31) with a sum of sums of 1323.
It is noticed that
all answers to this optimization problem are different by multiples of 21. Why is this?
|
|
Submitted by Steven Lord
|
|
Rating: 4.0000 (1 votes)
|
|
|
Solution:
|
(Hide)
|
The answer is that any set of 5 distinct numbers, a, b, c, d, e, taken three at a time (with replacement)
and added, yield a sum of sums S:
S = 21(a+b+c+d+e)
The individual sums need not be distinct, while the groups of drawn numbers, E_i, are distinct. The formula may be understood by adding
all possible combinations. A general formula for the sum of all sums, S, found when drawing groups of k from n numbers, E_i, with replacement, can be found. Here we count a specific element present once in a group, twice, ..., k times in a group of k using the binomial coefficient C:
S = sum{i=1 to k} [ i C(n+k-i-2, k-i) ] sum{i=1 to n} [E_i]
In our special case, the number a was drawn once, twice, or three times within a group of 3, for i = 1, 2, and 3.
The fact that the particular sets of 5 listed in this puzzle were answers to the "Magic Trick" problem was incidental and was included as a red herring. |
