Fibonacci
The problem of the milk cans.
The objective is to measure 4 liters
using three cans of respectively 3, 5 en 8 liters, by repeated pouring.
If
you want to give it a try, click on one of the drawn cans.
We put the
following general question.
Suppose I have 3 cans of
Fn-1, Fn and Fn+1
liters. What quantities (in whole liters) can I measure by repeated
pouring?
We are going to answer this question.
After pouring at the
most 2 times we can reach the following trivial situations: The first 2
cans are both empty or both full or one of both is empty and the other is
full. We try to avoid the uninteresting trivial situations (if possible).
Note that each pouring has the following characteristic.
The can, with
which you pour, is emptied completely, or: another can is filled completely.
In short, there is always an empty can and/or a filled can.
If the can is
filled, you have to pour with that can, for otherwise you obtain a 'trivial
situation'. If a can is empty, then you have to pour into that can, again to
avoid a 'trivial situation'.
The start position is special, because 2
cans are empty. We have to make a decision into which can we pour. Let us pour
the milk from the 3rd can into the 2nd. (The other possibility is equally
good). From this moment each pouring step is unambiguously fixed (if we stick
to the above mentioned rules: pour with full cans and pour into empty cans;
and never reverse the last pouring).
We proceed by
induction.
Suppose that at a certain moment the first can contains a liters
and can 2 is empty, and that in the preceding step the a liters were poured
from the 2nd into the 1st can.
Note that in the start
situation a=0.
The situation in step x: a ... 0 ... b
(=Fn+1-a)
In the next step we will fill the empty can,
and the a liters are not poured back, so the result is
step x+1: a ...
Fn ... b-Fn
Now, use the full can and
do not pour back:
step x+2: Fn-1 ...
a+Fn-2 ... b-Fn
Now again, use the full
can and do not pour back. This yields:
step x+3: 0 ...
a+Fn-2 ... b-Fn-2
Pour into the empty
can and don't pour back. Now we get 2 different situations, namely if
a+Fn-2 < Fn-1, then:
step x+4:
a+Fn-2 ... 0 ...
b-Fn-2
otherwise:
step x+4: Fn-1 ...
a-Fn-3 ... b-Fn-2
followed by
step
x+5: 0 ... a-Fn-3 ... b+Fn-3
and as a
<= Fn-1 (see the start situation)
step x+6:
a-Fn-3 ... 0 ... b+Fn-3
After 4 to 6
steps we end up in a same situation, but now the 1-st can contains
Fn-2 liters more or, if the can is to small for that, the
can contains Fn-3 liters less.
Conclusion: The 1-st can
is always empty or full or contains
kFn-2-mFn-3 liters, for certain
non-negative integers k en m.
We want to reverse this conclusion, that
is, if k and m are non-negative integers and t =
kFn-2-mFn-3, is positive and less than
Fn-1, then after some pouring can 1 contains t
liters.
Well, after a number of pourings there will be poured out m times
Fn-3 liters from the first can. Then there are say
k1Fn-2-mFn-3 liters in the
first can. Now k1 = k or k1 = k0+1 or k1 = k0-1 (for
2Fn-2>Fn-1). If k1 = k, then there are
t liters in can 1. If k1 = k+1, then there are t+Fn-2 liters
in the can. 4 to 6 steps earlier either Fn-2 liters are
added and we had t liters in can 1, or Fn-3 liters are
poured out of the can and t+Fn-2+Fn-3
liters were in can 1. But that is impossible because that is more than what
can 1 may contain.
If k1 = k-1, then there are t-Fn-2
liters in can 1. Then, 4 steps later there are t liters in can 1.
This
shows, that if k and m are non-negative integers and t =
kFn-2-mFn-3, is positive and less than
Fn-1, then after some pouring can 1 contains t
liters.
In order to prove that any amount of liters can be measured, we
use the following general formula for Fibonacci
numbers.
(-1)pFq-p =
Fp-1Fq -
FpFq-1
Substitute q=n-2 and, if
n is even p=n-3, and if n is odd p=n-4. This yields:
1 =
Fn-4Fn-2 -
Fn-3Fn-3 if n is odd and
1 =
Fn-5Fn-2 -
Fn-4Fn-3 if n is even.
Note that the
number 1 can be written as kFn-2-mFn-3
with k and m non-negative integers. But then this is also true for each number
between 1 and Fn-1
Thus after a number of steps can 1
is filled with t liters (for each 0 <= t <=
Fn-1).
t liters in can 1 and Fn liters
in can 2 yield in the next step t2 = t+Fn-2 liters in can 2,
and t2 can have each value between Fn-2 and
Fn.
Fn+1-t is a number between
Fn and Fn+1. So, in short, each integer
number of liters less or equal to Fn+1 can be
measured.