|Perl: the Markov chain saw|
Re: Challenge: Egg Timer Puzzlesby blokhead (Monsignor)
|on May 03, 2006 at 01:04 UTC||Need Help??|
My assumptions: We have an unlimited supply of timers in each available time amount. We can flip two timers simultaneously (don't need to be able to flip more simultaneously for the solutions this produces).
Generalizing from your examples, it doesn't take long to see that you can only make "new" egg-timer numbers by adding or subtracting existing egg-timer numbers. So the set of egg-timer numbers are all the numbers that can be written as a sum 7a+4b for integers a & b.
More generally, if X1 .. XN are the different kinds of timers you have, the egg-timer numbers you can generate from these are exactly the linear combinations of X1 .. XN. From number theory, we know that this set of numbers is the same as the multiples of GCD(X1 ... XN).
So once we know how to put exactly GCD minutes on a timer, we can time any valid egg-timer number by first generating a bunch of these GCD timers, and then running them successively many times in a row (the target number is just a multiple of this GCD).
Now all that's left is to figure out how to get GCD minutes on a timer. Fortunately, number theory can help us again! The standard algorithm for computing the GCD can also be augmented to give integers b1 .. bN such that
GCD(X1 .. XN) = b1 * X1 + b2 * X2 + ... + bN * XN(called Bezout coefficients). Now we're getting closer!
How do we get from these coefficients back to the egg-timer problem at hand? Let's look at an example: For egg timers of 7 and 4 minutes, we have
GCD(4,7) = 1 = 2*4 - 1*7So to get 1 minute of time inside a timer, we do the following two steps in parallel:
More generally, we can split the X's up into those which have positive and negative Bezout coefficients. Start the appropriate number of timers for each group, one after the other (but the two groups in parallel). The negative-coefficient group will finish earlier, in fact, there will be exactly GCD minutes left on the last timer. Since the GCD is never bigger than any of the X's, these GCD minutes of time will always fit on the last timer, no matter which order we start them in. We set aside this last timer, and make as many GCD-timers as we want!
In code, it looks like this:
OK, so this finds terrible solutions for most numbers, if you'd actually have to do these things with the timers. But they are solutions nonetheless, and you didn't really say anything about optimality of solutions. Anyway, this method has its own intrinsic beauty from the application of number theory.
Update: see Re^3: Challenge: Egg Timer Puzzles for how you can extend this technique and get rid of the infinite # of timers assumption.