Homework due Wednesday, August 24, 2011

We saw in class how to solve the Die Hard 3 water problem: given a 5 gallon jug and a 3 gallon jug. The solution ultimately involved filling the 5 gallon jug twice and emptying the 3 gallon jug 2 twice, giving 4 = 2*5 - 2*3 gallons. In more detail, we filled the 5 gallon jug, used that to fill the 3 gallon jug which we dumped out giving us 5 - 3 = 2 gallons in the 5 gallon jug. We poured those 2 gallons into the now empty 3 gallon jug so we could then fill the 5 gallon jug a second time. Again we used the water in the 5 gallon jug to fill the 3 gallon jug (which you remember already has 2 gallons in it). This gave us 4 gallons in the 5 gallon jug, and we dumped out the water in the 3 gallon jug leaving us with 4 gallons all together. But even though there was a certain amount of moving the water back and forth in the two jugs, ultimately we filled the 5 gallon jug twice and emptied the 3 gallon jug twice, giving us 4 = 2*5 - 2*3 gallons in the end.

This solution first involved writing 4 as a multiple of 5 minus a multiple of 3. We also had a second solution, which we can write as 4 = 3*3 - 1*5, and we saw in class how to obtain other exact quantities of water:
2 = 5 - 3
3 = 0*5 + 1*3
4 = 2*5 - 2*3
5 = 1*5 + 0*3
6 = 0*5 + 2*3
7 = 2*5 - 1*3
8 = 1*5 + 1*3
We didn't in class decide whether we can get 1, but we did notice that we can't get more than 8 gallons, because we have only the two jugs and they add up to a total volume of 8 gallons.

In each of these cases, the arithmetical expression can be converted into an actual real life way of getting an exact amount of water in the jugs. For example, as we saw in class, to get 2 gallons, fill the 5 gallon jug and use those 5 gallons to fill the 3 gallon jug, which we dump out, giving 5 - 3 = 2 gallon left over in the 5 gallon jug.

Problem 1: Is it possible to write 4 as a difference of a multiple of 3 and a multiple of 5 in any way other than those we found in class; i.e., other than 4 = 2*5 - 2*3 and 4 = 3*3 - 1*5? (The answer is yes, but how?) Can any of these other arithmetical expressions be used to get a real life solution to the water problem?

Problem 2: Is it possible to write 1 as an integer linear combination of 3 and 5?