LAST EDITED ON Aug-11-03 AT 05:41 AM (EST)
Hi jman_redYou think I am trying to be funny, don't you? (I am.)
Suppose that each dwarf gives up in each step all the milk he or she currently has. Call xi the amount of milk the i-th dwarf starts with. Create a 7 dimensional vector space above the ring of 7 dwarfs. The 7th dwarf must end up with no milk, which must be identical with the initial state. Therefore, x7 = 0. The following vector obviously is the solution, because the dwarfs just cycle the milk around the table with no change (what else can you expect from dwarfs with no babysitter?)
|x> = |x1, x2, x3, x4, x5, x6, x7> = |x1, 5/6·x1, 4/6·x1, 3/6·x1, 2/6·x1, 1/6·x1, 0>
Since
S7i=1 xi = 3
21/6·x1 = 3
x1 = 6/7
|x> = |6/7, 5/7, 4/7, 3/7, 2/7, 1/7, 0>
and this is the only solution. But you want the proof. Well, you asked for it. Let me define 7 linear operators on the vector space of 7 dwarfs as follows:
F1|x> = |0, x2 + x1/6, x3 + x1/6, x4 + x1/6, x5 + x1/6, x6 + x1/6, x7 + x1/6>
F2|x> = |x1 + x2/6, 0, x3 + x2/6, x4 + x2/6, x5 + x2/6, x6 + x2/6, x7 + x2/6>
...
F7|x> = |x1 + x7/6, x2 + x7/6, x3 + x7/6, x4 + x7/6, x5 + x7/6, x6 + x7/6, 0>
Each of these operators corresponds to one step in the milk exchange and their product F to the one full round:
F|x> = F7F6F5F4F3F2F1|x>
Next, I have to define a metric on the the vector space of 7 dwarfs - this will make it a Banach metric space of 7 dwarfs. The usual euclidian metric d will do:
d2(|x>, |y>) = S7i=1 (xi - yi)2
For arbitrary 2 vectors |x> and |y> such that
S7i=1 xi = S7i=1yi (= 3)
the operators F1, F2, ..., F7 produce vectors such that
|u> = Fk|x>
|v> = Fk|y>
S7i=1 ui = S7i=1vi (= 3)
For the operator F1, the distance of the vectors |u> = F1|x> and |v> = F1|y> is
d2(F1|x>, F1|y>) = S7i=2 (xi + x1/6 - yi - y1/6)2 =
= S7i=2 (xi - yi)2 + 2/6·(x1 - y1) S7i=2 (xi - yi) + 1/6·(x1 - y1)2 =
= S7i=2 (xi - yi)2 - 1/6·(x1 - y1)2 £ d2(|x>, |y>)
where the equal sign is valid only for x1 = y1. In the last step I used:
S7i=1 (xi - yi) = 0
S7i=2 (xi - yi) = -(x1 - y1)
Similarly for the other operators F2, F3, ..., F7:
d2(Fk|x>, Fk|y>) = Si¹k (xi - yi)2 - 1/6·(xk - yk)2 £ d2(|x>, |y>)
where the equal sign is valid only for xk = yk. Let k be the index for which the difference between xk and yk is maximum:
(xk - yk)2 = max{(xi - yi)2}, i = 1, 2, ..., 7
The difference for this index will be still a maximum after the application of the operators F1, ..., Fk-1 (if any). Denote
|u> = Fk-1...F1|x>
|v> = Fk-1...F1|y>
(uk - vk)2 = max{(ui - vi)2}, i = 1, 2, ..., 7
d2(Fk|u>, Fk|v>) = Si¹k (ui - vi)2 - 1/6·(uk - vk)2 = d2(|u>, |v>) - 7/6·(uk - vk)2 £
£ d2(|u>, |v>) - 1/6·d2(|u>, |v>) = 5/6·d2(|u>, |v>)
For the full round operator F I get
d2(F|x>, F|y>) = d2(F7F6F5F4F3F2F1|x>, F7F6F5F4F3F2F1|y>) £
£ d2(FkFk-1......F1|x>, FkFk-1......F1|y>) £
£ 5/6·d2(Fk-1......F1|x>, Fk-1......F1|y>) £
£ 5/6·d2(|x>, |y>)
I proved that for vectors |x> and |y> such that
S7i=1 xi = S7i=1yi (= 3)
the full round operator F on the Banach metric space of 7 dwarfs is a contracting operator with the coefficient of contraction a £ Ö(5/6) < 1. According to the fixed-point theorem, a contracting operator on the Banach metric space has a unique fixed point such that
|xF> = F|xF>
Moreover, if |x0> is an arbitrary vector in the Banach metric space of 7 dwarfs such that
S7i=1 x0i = 3
the sequence |x0>, |x1>, |x2>, ... defined by
|xk+1> = F|xk>
is convergent with respect to the metric d:
lim d(|xk>, |xF>) = 0 for k ® ¥
Q.E.D.
Could we do this for an infinite number of dwarfs ?
Printer-friendly copy
Email this topic to a friend
