## Tuesday, December 10, 2013

### 13 Coins Puzzle

So a riddle today.

I have 13 coins. They like many other things have weights. These weights happen to be positive numbers (we're going for realism here).  They also have the property that if I remove any one coin I can split the remaining 12 into two groups of 6 which have the same total weight. Does this guarantee that all the coins have the same weight?

Part a. If the weights are integers.
Part b. If the weights are allowed to be any positive real.
Part c. Sod positivity and indeed reality. Let's let the weight of the coins be any complex number. .

Have fun. Solution to come soon.

1. I'm not a math guy so maybe this is a dumb question but how exactly would you compare the weights if they are complex numbers? Is 2 + i > 2 + 2i? The other way around? I have no understanding of this.

1. When you compare here you only need to say same or different. There is no good way to order the complex numbers.

2. This comment has been removed by the author.

3. Hmm... so for part a I want to say the answer is yes. So any combination of integer weights can be thought of as either an increasing or constant series for this question since the order doesn't matter. So like 1 1 1 1 1 or 1 2 1 2 1 = 1 1 1 2 2 (for only 5 coins) are a few examples. Obviously, for the constant series, it works fine.

For increasing series, there are also a few types, one that goes up weakly (I'm calling it this because I'm not sure what the proper term is) where it doesn't have to go up at every point such as 1 1 1 1 2 or 1 1 1 2 2 and one that increases strongly such as 1 2 3 4 5. These guys don't work.

So 1 2 2 4 5 is weakly increasing and removing 5 breaks the puzzle.
1 3 5 7 9 is strongly increasing and removing 3 or 7 breaks the puzzle.

So, since increasing series don't work. I conclude that they must all be the same weight. Obviously, I'm assuming if this works for 5 coins it works for 13 coins. I have no good reason for this other than it feels right. Hopefully, I haven't made a fool out of myself.

4. Weakly increasing is fairly standard terminology. You'd more typically use strictly increasing than strongly increasing though. As for the solution consider 1 2 2 3 5. It's weakly increasing but removing the 5 doesn't stop us from pairing 1 with 3 and 2 with 2.

5. Yes this is true but doesn't removing any number other than 5 break the puzzle in this series? I'm pretty sure the increasing series don't work but I need to think about how to prove this. Will ponder it and get back to you.

6. Yes removing any number except 5 doesn't work in the 1 2 2 3 5 example. The trouble is that we need to show it doesn't work for any series. The way you're suggesting we show this is to remove the largest coin if there are any ties. The 1 2 2 3 5 example is just to show that that particular strategy doesn't work. This is a very different from saying that 1 2 2 3 5 is workable (ignoring that it it's a string of 5 numbers and not a string of 13).

7. This comment has been removed by the author.

8. Okay I think I got it now except I used a different approach.

Let 3 coins = {a, b, c}, then for the puzzle to be true a=b, b=c, a=c (each permutation)

Add 2 coins {d, e} to the puzzle. It also needs to satisfy the original permutations (take out c then a=b, take out b then a=c, etc). Therefore,
a + d = b + e
b + d = c + e
a + d = c + e

Using some simple algebra, we show b + d = a + d therefore b = a

b + d = b + e
so d = e

b + d = c + d
so b = c

a - c = e - a
0 = e - a
e = a

All coins equal by transitive property.

I have proved that all must be equal with 5 coins (I think). Just extrapolate this to 13 coins. I think this generalizes to both all real numbers as well as complex numbers.

9. So the trouble with trying to induct on the number of hats here is that when you remove coin c for example it's as likely to be the case that a+b=d+e as the case that a+e=b+d and there is no particular reason for a=b in the 5 coin case just because things with the same label happened to in the 3 coin case.

10. This comment has been removed by the author.

11. O wait I see what you are saying. You could have:
B + C = D + E
A + D = C + E
A + E = B + D
This you can't solve. Before I'm implicitly assuming A = B and so on.

12. ok so 5 coin case.
If you remove coin A then sure
B+C=D+E and that's fine because you haven't labeled anything yet. However when you say B+C=D+E you implicitly label the coins on 1 side of the scale as B and C and the other side as D and E.

If you remove coin B then there is a difference between writing
A+C=D+E and writing A+D=C+E because D and E where together (same side of equation/scale) before while C and E where not.

13. And also even if you list out all 5 removals there is a combination that is unsolvable:
Remove A then B + C = D + E
Remove B then A + D = C + E
Remove C then A + E = B + D
Remove D then A + C = B + E
Remove E then A + B = C + D

Back to square one.

2. This comment has been removed by the author.

3. 4. well this is trivial once you modulo the matriks by 2

1. modulo 2 is certainly the key insight, I don't know what matricies you'retalking about.

5. For part a (integers):

Notice the following two things:
(1) If a collection of integers has the property in the question (i.e., if you remove any one, you can partition the remaining 12 into two groups of 6 with the same sum), then all integers in that collection have the same parity (they're all equal mod 2). Otherwise, if x1 is odd and x2 is even, then removing one of them will leave the sum of the remaining 12 to be odd, which implies that we won't be able to split them into two collections with equal sum.

(2) If a collection of integers has the property in the question, we can subtract the same constant amount from each of them, or scale them all, and preserve the property.

Let's say you have a collection of positive integers that have the property in the question. By subtracting the smallest integer from all of them, we can assume that at least one of them is 0. Note by observation (1) that all integers must be even now. So we can scale everything by 1/2 and repeat the observation that all of the integers must be even. This will give an infinite reduction type of contradiction UNLESS all the integers were 0, which would mean that all of the original weights were the same.

So, yes, if the weights are all integers, then they must all be the same.

Not really sure how to make progress on the others though. I was thinking that maybe we can try to "fudge" the real numbers by some amount e>0 each, to turn them into rational numbers, which we then might be able to relate to the integer problem?

Another way of saying the same thing is that if our original problem involves real numbers x1,x2,...,x13, we might consider the integer problem floor(k*x1),floor(k*x2),...,floor(k*x13) for some large values of k.

I don't know...just some ideas.