Linear Algebra at a Math Olympiad
A puzzle from the 1977 USSR math Olympiad can be solved naturally with linear algebra:
Seven dwarfs are sitting at a round table. Each dwarf has a cup partially filled with milk. Each dwarf in turn divides all his milk evenly between the six other cups. After the seventh dwarf has done this, every cup happens to contain the initial amount of milk. What was the initial distribution of milk?
Can you use linear algebra to intelligently solve this puzzle?
Share:
Misha:
Wait, if each dwarf divides ALL his milk between the other 6, he is left with no milk after his turn. Does he keep 1/7 to himself and gives 1/7 to each of the rest? That would make more sense.
13 October 2008, 5:52 amMisha:
Sorry, it makes sense either way. Slightly off topic: the Russian national idea explained
13 October 2008, 4:56 pmMisha:
Perron-Frobenius theorem + conservation of the total amount of milk tell us that there is a solution, actually finding it is a matter of calculating an eigenvector of a matrix.
13 October 2008, 7:24 pmChrist Schlacta:
if the 7th dwarf divides all his milk he must initially have no milk, however this contradicts the stated initial state.
13 January 2011, 1:44 pmReila:
find eigenstates to:
ones(7,7) – identity(7,7) = lambda*identity(7,7)
1 July 2013, 1:20 am