Sunday, December 15, 2013

13 Coins Solution

So here are the solutions to the 13 coin conundrum .

Part a was solved in the comments but to rehash it.

You begin by observing that the 13 coins must all be the same weight mod 2. If this was false, i.e. if there was a coin of even weight and a coin of odd weight then removing one of them would leave the rest of the coins with a total weight which is odd, and hence that cannot be split into 2 equal bits.

One then iterates this observation by observing that they must be the same weight mod 4,8,16 etc. Eventually you get beyond the size of the largest coin and hence they are the same weight. The easiest way to see this is to divide the weights by 2 if they are all even and to ad 1 and divide by 2 if they are all odd.

Part b requires less ingenuity but more advanced techniques. Consider the vector space over Z  generated by the 13 weights. It is clearly finite dimensional. Write each weight as a vector in this space and apply the result of part a to each co-ordinate.

Similiarly for part c it's a vector space of size 2 over R (i.e. part b).


16 comments:

  1. Why do you try generate a vector space (over Z, lol!). Simple take the matriks of relations modulo 2 and you see the zero Eigenspace has only one dimension.

    ReplyDelete
    Replies
    1. Assuming this isn't a troll. Which matrices are you talking about?

      Delete
  2. The matriks of relations of course. Remove coin 1. Then a linear combination of the other coins sum to zero. So the first row is like (0,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1). Remove coin 2. Then the second row is like (1,0,+-1,+-1,...,+-1). Exetera. When you modulo 2 there are zeros on the diagonal and 1 elsewhere. Compute the characteristic polynomial and you are done. Is this not evident?

    And no I am not a troll I am human just like you. So rude!!!

    ReplyDelete
    Replies
    1. Hans, firstly an apology on the troll comment. I have several friends who would
      happily post a couple of lines which vaguey relate to the real answer (but not really and very very vague),
      essentially as a joke at me (I even asked a couple if they where the one who posted your comment).
      This is usually called trolling . Anyway the intent wasn't to offend a genuine commentor and I apologise if I did so.

      On the math itself: I did not get that this is what you meant from the original comment, it seems to me
      that when you modulo the matrix entries by 2 you must also be moduling the weights by 2 for this to keep
      any meaning at all. Which means that you end up proving that all the weights are equal mod 2 (i.e. all
      even or all odd, or in part b maybe all of the form 2k+0.8149 for integer k). This is somewhat weaker
      than showing that they are all the same weight. Why does your approach prove anything more than this?

      Delete
    2. I accept your humble apology.

      As I explain before, the problem is to show that a certain matriks M with integer entries has a dimension 1 Eigenspace for the Eigenvalue zero. In Linear Algebra we call this the Nullspace. If we show the characteristic polynomial has x as a factor only once, we are done. Taking modulo by 2 is a ring homomorphism, so if we show that charpol(M) mod 2 = charpol(M mod 2) is of form x^13+...+x, the proof is complete. You do not need a Phd is Linear Algebra to see this.

      Delete
    3. Ok sure, we want to prove that a matrix M of a certain form (for every matrix of his form), the null-space is zero. Showing that x is a factor of the characteristic polynomial only once does get you there. So far so good.

      The trouble is showing charpol(M) does have 0 as a non-repeated factor. You decide to mod everything by 2 which means we need to talk about the solutions mod 2 (or a least be very very careful about which field we're working over where). Anyway you have this matrix with 0s on the diagonal and 1s everywhere else. I'm going to call that matrix A.

      I agree if we where working over R that charpol(A) ending with x would make 0 a non-repeated eigenvalue of A. But as we're working over F2 (i.e. working mod 2) an eigenvalue of 2 (over R) is the same as an eigenvalue of 0 (over F2). You really need to be very careful when going through these cases.

      I spoke to someone in RL (with a phd) who was convinced he could make this work with some argument about A being idempotent but this really strikes me as alot come complicated than the solution in the post.

      Delete
    4. I am not looking for eigenvalues over F2. I just use the fact that charpol(A) mod 2 is of the form x^13+...+x, which imply the coefficient of x of charpol(M) is not zero. We already now that the constant term of charpol(M) is zero, as (1,1,...,1) is in the nullspace. Must I explain you how to work out charpol(A)? I thought it was obvious.

      Maybe you think this solution is complicated, but you still have not explain what you mean by a vector space over Z. I think you do not know what a vector space is?

      Delete
    5. Ah co-efficent of x^1 being non-zero because it's 1 mod 2. That does work, very nice.

      I haven't explained what I mean by a vector space over Z because you didn't ask me what I meant by it and it is standard terminology.

      For more detail let's call the 13 coin weighs w_1,w_2,...,w_13.
      Then we write these as
      w_1=a_{1,1} * b_1 + a_{1,2}* b_2 +...a_{1,m}*b_m
      w_2=a_{2,1} * b_1 + a_{2,2}* b_2 +...a_{2,m}*b_m
      etc

      where a_{i,j} are integers and b_i are choosen to minimize m (the number of the b_i). Note we can write the w_i this way for m=13 so there is no problem doing this.

      The vector space I'm talking about is the set of things that can be written
      as c_1*b_1+c_2*b_2+...+c_m*b_m for integer c_i.

      We can now think of w_i as (a_{i,1},a_{i,2},...,a_{i,m}). Because m is minimal the only way to get the w_i to sum to 0 is to have each coordinate sum to zero. Which let's us use the result for integers.

      Delete
    6. That is incorrect. What you have is a maximal rank abelian group inside the Q-linear span of the weighs. But this is not called 'vector space'. I beleive it is called a latte.

      Delete
    7. I suppose I should have said "module" rather than "vector space" as Z isn't a field. You can ad them together and multiply them by scalars (in this case integers), so the substance of the argument still works.

      Alternately you can prove the result for rationals (easy from having it true for integers) and then apply the above argument over Q.

      Delete
  3. Hans-Dietrich, I think the word you're looking for is 'lattice'

    ReplyDelete
    Replies
    1. You maybe right. In fact, I first think like you, but then I remember lattuce is also a vegetable, yes? English is a funny language, lol.

      Delete
  4. You maybe right. In fact, I first think like you, but then I remember lattuce is also a vegetable, yes? English is a funny language, lol

    ReplyDelete
  5. You maybe right. In fact, I first think like you, but then I remember lattuce is also a vegetable, yes? English is a funny language, lol

    ReplyDelete
  6. You maybe right. In fact, I first think like you, but then I remember lattuce is also a vegetable, yes? English is a funny language, lol

    ReplyDelete