A magician told his friend(X) that he will do a magic trick and gave X 3 cards with 5 distinct non-negative integers written on each card. X was asked to choose a number from each card and tell the sum of the 3 chosen numbers to him. For every possible sum X told him, he answered all the 3 chosen numbers correctly. If you sum all these possible sums, what is the minimum value it can take?
Note: The integers on a card are distinct but integers on two different cards may not be distinct.
An obvious way would be to place representations of base-5 units values, 5's values and 25's values on the three cards:
card 1: 0, 1, 2, 3, 4
card 2: 0, 5, 10, 15, 20
card 3: 0, 25, 50, 75, 100
There are 125 possible totals, zero through 124, just as there are 125 possible sets of three that could have been chosen. The sum of the possible sums is Sigma{0 to 124} n = 7750. This would be the minimum possible sum of sums. (except, see last paragraph below)
However, the puzzle mentions the possibility that separate cards might repeat given numbers. If that's the case, and we wish only to identify the numbers, and not which card a given number might come from, then consider the following set:
Each card contains 0, 1, 4, 16, 64
If the total is 1, 2 or 3, you know there were that many 1's and the rest were zeros (as we are assuming we don't have to identify which card had which number). If the total was 12 you'd know they were all 4's, etc. A decoding table follows:
sum 0's 1's 4's 16's 64's
0 3 0 0 0 0
1 2 1 0 0 0
2 1 2 0 0 0
3 0 3 0 0 0
4 2 0 1 0 0
5 1 1 1 0 0
6 0 2 1 0 0
8 1 0 2 0 0
9 0 1 2 0 0
12 0 0 3 0 0
16 2 0 0 1 0
17 1 1 0 1 0
18 0 2 0 1 0
20 1 0 1 1 0
21 0 1 1 1 0
24 0 0 2 1 0
32 1 0 0 2 0
33 0 1 0 2 0
36 0 0 1 2 0
48 0 0 0 3 0
64 2 0 0 0 1
65 1 1 0 0 1
66 0 2 0 0 1
68 1 0 1 0 1
69 0 1 1 0 1
72 0 0 2 0 1
80 1 0 0 1 1
81 0 1 0 1 1
84 0 0 1 1 1
96 0 0 0 2 1
128 1 0 0 0 2
129 0 1 0 0 2
132 0 0 1 0 2
144 0 0 0 1 2
192 0 0 0 0 3
While the sums now go up to 192, there are fewer possible sums, so the sum of the sums is smaller: just 1785.
Perhaps there's an even better way. It's not as immediately obvious that this is the minimum given the relaxed constraints, as compared with the way that identifies which number came from which card.
In fact, it just occurred to me that each successive number need not be 4 times the preceding, but only 1 more than 3 times the preceding:
Each card contains 0, 1, 4, 13, 40.
The decoding table is then:
sum 0's 1's 4's 13's 40's
0 3 0 0 0 0
1 2 1 0 0 0
2 1 2 0 0 0
3 0 3 0 0 0
4 2 0 1 0 0
5 1 1 1 0 0
6 0 2 1 0 0
8 1 0 2 0 0
9 0 1 2 0 0
12 0 0 3 0 0
13 2 0 0 1 0
14 1 1 0 1 0
15 0 2 0 1 0
17 1 0 1 1 0
18 0 1 1 1 0
21 0 0 2 1 0
26 1 0 0 2 0
27 0 1 0 2 0
30 0 0 1 2 0
39 0 0 0 3 0
40 2 0 0 0 1
41 1 1 0 0 1
42 0 2 0 0 1
44 1 0 1 0 1
45 0 1 1 0 1
48 0 0 2 0 1
53 1 0 0 1 1
54 0 1 0 1 1
57 0 0 1 1 1
66 0 0 0 2 1
80 1 0 0 0 2
81 0 1 0 0 2
84 0 0 1 0 2
93 0 0 0 1 2
120 0 0 0 0 3
and the sum of the sums is now only 1218.
More about first interpretation (identifying which card each number came from):
But it might even be possible, with repeat numbers on different cards, to arrange things such that with, say, a total of x+x+y, where x and y appear on some card(s) is possible only on one set, as y is unique to one card. Then, if x appears in a total by itself, it would have to be assured that the other numbers total's could uniquely identify their cards. So it sounds as if, with repeats, it might be possible to improve the 7750 of the first interpretation, but I don't think by much as it would seem that only one repeat would be possible.
|
|
Posted by Charlie
on 2009-05-10 17:05:33 |
some ideas
