The Coin Machine
A coin machine accepts coins of 32 different colors. Every time you insert a coin of a certain color, it gives you two fixed choices to choose from. Every choice consists of receiving a monetary amount between $0 and $10 and maybe another coin of the 32 colors. You and Daniel both have a white coin to start with. You see Daniel win $500 from the machine. Can you win $1000 from the machine?
Details and Assumptions :
For example, the coin machine might have that inserting a blue coin outputs either a white coin and $5 or a yellow coin and $1. This output is constant; the machine won't output something different next time you insert a blue coin.
Image Credits: tomtilley.net
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Problem credit goes to the UW Math Olympiad.
Define a loop to be a sequence of coin insertions such that I end up with a coin that I previously owned.
I claim that there exists a loop that gives a positive payout.
First, if there were no loops, then the maximum number of payouts is 3 2 , the number of coins. But then that means the maximum total payout is 3 2 × $ 1 0 = $ 3 2 0 which is less than what Daniel won.
Thus, there must exist at least one loop. If all of the loops did not have payouts though, then going through them is the same as not going through them at all, so the payout still does not exceed $ 3 2 0 .
Thus, there must exist a loop with a positive payout. But then, just go through this loop over and over again to win infinite moneys. We win!