BRC Problem of the Month - February 2000

Could Euclid win a "Car Talk" tee shirt (and would he wear it)?

Background

A recent "Puzzler" on Car Talk  was:
      How do you measure exactly two gallons of water with 13 and 7-gallon jugs?
     
This was a timely problem for one of my classes.  They had just seen this theorem about the greatest common divisor of two integers:

Theorem. If a and b are positive integers and , then there exist integers s and t such that
        


The Extended Euclidean Algorithm (TI program) can be used to find the values of g, s, and t.  Note: You don't need to know the algorithm to work on this problem.

This Month's Problem

(a)  How is the fact that gcd(13, 7) = 1 = 13(-1) + 7(2)  related to a solution to the puzzler

(b)  Can every measuring problem (measure x gallons with a and b gallon jugs) be solved if you know s and t?

BRC Problem Index