Linear Algebra for Pirates
I’ve got this puzzle from Nick Petry.
Captain Flint is dying. All his treasures are buried far away. He only has 99 pieces of gold with him. Filled with remorse at the last moments of his life, he decides that he only wants to take one piece of gold with him to his grave. The rest of the gold he will give to the families of two men that he had killed the day before.
Though Captain Flint is heavily drunk he notices that no matter which piece he takes for himself, he can divide the leftover 98 pieces into two piles of 49 pieces each of the same weight. Prove that all the gold pieces are of the same weight.
For an additional challenge, Sasha Shapovalov suggested the following generalization of the previous puzzle.
Captain Flint has N gold pieces and yesterday he killed not two but K men. He wants to take one piece with him to his grave and to divide the rest into equi-weighted piles, not necessarily of the same number of pieces. If he can choose any piece to take with him and is able to divide the rest, prove that N – 1 is divisible by K.
Both of these puzzles can be easily solved if the weight of every gold piece is an integer or even a rational number. If you don’t assume that the weights are rational numbers, then I do not know an elementary solution, but I do know a simple and beautiful solution using linear algebra for both puzzles.
Even pirates need linear algebra to divide their treasure. Hooray for linear algebra!
Share:
Mitka:
You can also use Abelian groups (which are almost linear algebra, but not quite.)
We can assume that Captain Flint’s lightest piece is magical and has zero mass (otherwise subtract the weight of the lightest stone from all of them, and check that solving this problem is equivalent to solving the original one.)
Now take the finite abelian group A generated by all the weights, m_1, .., m_99. Suppose the total weight is M. Then we have M/2 is in A (because the pieces can be be divided into two equal parts when he takes away the 0-weight piece,) and we also have M-m_i/2 is in A for any index i (this is the total in one of the piles after removing the i’th piece and dividing.) But this means that the difference, m_i/2, is also in A for any i.
But this means that any linear combination of the m_i/2 is also in A, in particular m_j/2 is a linear combination of the m_i and so m_j/2/2=m_j/4 is in A. So by induction, m_j/2^n is in A for any n.
Now suppose some m_j is not zero for some fixed j. Then there’s a problem: any subgroup of an abelian group with finitely many generators will still be finitely generated. But the subgroup of A generated by m_j/2, m_j/4, .., m_j/2^n, … can’t be generated by a finite number of elements (if it were, all the generators would be rational multiples of m_j with a greatest common denominator.) But remember A is finitely generated by construction, so we have a contradiction. So after subtracting the lightest weight, all the weights are zero – hence they were equal at the start.
31 October 2008, 7:29 amtanyakh:
Suppose the weights are not the same. Consider a vector space V that is a space of Q-linear combinations of all weights. Space V has a one-dimensional factor space such that the images of the given weights are not all equal. But the images satisfy the same equations as the weights in the puzzle. The images are have rational ratios with respect to each other. Using the solution for rational numbers, we can conclude that they are all the same, creating a contradiction. A similar method works for the second question.
14 March 2023, 6:43 pm