Four people are in a bar.

Ben owes Glen a drink. Glen owes Rhen two drinks. Rhen owes Sven three drinks. Sven owes Ben four drinks.

To settle up, what is the minimum number of drinks that need to be bought by who for whom?

Three. Each of the others buys Ben a drink.

Proof:

First Glen buys Rhen the first of the two drinks he owes. Rhen uses it to pay off one of the three drinks he owes to Sven, who passses it on to Ben, who sends it around a second time until it winds up back in Ben's hands. At this point, Ben has given Glen one drink and is square. Glen has given Rhen two drinks and is square. Rhen has given Sven two drinks and still owes him one. Sven has given Ben two drinks and owes him two.

Now Rhen buys a drink fr sven who passes it to Ben. Rhen is now square with Sven, and Sven owes Ben one drink, which he then buys.

So each of the other three has bought a drink which eventually went to Ben

Posted by TomM on 2002-12-18 03:22:05