This problem appeared in the previous blog: do
think about it before reading on.
“With any two jugs, holding a and b gallons when full
(where a and b are integers), can you make all of the values from 1 to a+b?”
This clearly cannot be done if a and b are both
multiples of the same thing. For example, if they are
both multiples of 3 then the only answers that can be made must also be
multiples of 3 (since we will be adding or subtracting multiples of 3 each
time). I think the easiest one to
consider is where a and b are both even. The only numbers you can make are also even.
If they are not multiples of the same thing (ie they are
co-prime) then I think we can make every number up to a+b and I reckon the
addition/subtraction method used in the previous blog helps to show how it
works.
Here is an example for 7 and 4:
1 = 4+4-7
2 = 7+7-4-4-4
3 = 7-4
4 = 4
5 = 4+4+4-7
6 = 7+7-4-4
7 = 7
We could of course just use the values for 1 each time
and repeat as many times as is necessary.
This would mean that 3 would be made by doing three lots of (4+4-7), but
4+4-7+4+4-7+4+4-7 is significantly less neat than 7-4.
For the rest of the numbers up to 11 we can put the
numbers already obtained into the small jug and fill the bigger one to the brim
(so 8 is 7+1, etc).
This doesn’t prove it is possible for all pairs of
co-prime jugs, nor does it explain how to do it, but it does give a method that
can be applied to work it out.
3 comments:
Hello Mark,
Greetings and Happy New Year from London! I look forward to reading more of your blog in due course!
It strikes me that this is a restatement of Bézout's identity:
Let a and b be co-prime integers
Therefore, there exist integers j and k such that:
ja + kb = 1
Let n be the target number of gallons.
Multiplying through by n gives:
nja + nkb = n
So to obtain n gallons, you fill* jug a nj times, and jug b nk times.
(* empty if j or k is negative.)
The only question that remains is whether there are any further constraints which make the problem more complicated than repeatedly adding or subtracting two co-prime integers, or whether some combinations of addition and subtraction are impossible within the confines of only one jug of each size. Intuitively I suspect that there are no further complications, but that's maybe an exercise for someone else...
Looks like Blogger didn't include my name first time round - sorry!
Hello Michael,
Thanks for the Bézout comment.
Intuitively I suspect that there are no further complications
I agree. As long as the running total doesn't either exceed the total capacities of the two jugs or become negative then there is no problem, and it is always possible to remain within these confines, so it should all work out fine.
Post a Comment