wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> very hard puzzle
        
(Message started by: avenger421 on Aug 18^th, 2005, 6:35am)

Title: very hard puzzle
Post by avenger421 on Aug 18^th, 2005, 6:35am

Prove that any pair of timers that time a different prime number of minutes each can time any length of time in whole minutes.

Title: Re: very hard puzzle
Post by JocK on Aug 18^th, 2005, 11:02am

Not sure whether I understand the problem correctly.

Is the intention to asks us to prove that:
for any positive integer N and any two primes P and Q satisfying P =/= Q, one can find an integer solution to the linear Diophantine equation P x + Q y = N ...?

[hideb]... and that is easy as the equation P x - Q y = 1 for any P and Q that are relatively prime has a solution that is defined by the continued fraction for P/Q. [/hideb]

Title: Re: very hard puzzle
Post by River Phoenix on Aug 18^th, 2005, 11:35am

I think it's more complicated than that Jock. It seems to me that there is no way to measure for negative values of p and q using the clocks, but there are a host of other strategies to eventually quantify a N-minute long length of time. I think that this is very similar to the buckets of integral amounts of water problem.

Title: Re: very hard puzzle
Post by JocK on Aug 18^th, 2005, 11:54am

on 08/18/05 at 11:35:17, River Phoenix wrote:

But that is exactly what I mean (see Icarus' post in the thread http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1124002339 in which he uses the same argument to solve the buckets of water problem.)

Don't know what you mean by "to measure for negative values of p and q using the clocks".
A negative value for one of the unknowns (x or y) would imply that you have to start both clocks at the same time and use the time difference between two specific alarms. For instance:

2 x + 3 y = 1

has the integer solution x = -1 and y = 1.

This corresponds to starting a 2 minutes timers and a 3 minutes timer at the same time and subsequently time 1 minute by observing the difference in time between the alarms.

Title: Re: very hard puzzle
Post by River Phoenix on Aug 18^th, 2005, 12:29pm

OK I get it. That's pretty solid 8)

Title: Re: very hard puzzle
Post by SWF on Aug 18^th, 2005, 5:29pm

If the two timers time p and q minutes with p>q and you want to measure r minutes, use the p timer r*((p-1)! +1)/p times and the q timer r*(p-1)!/q times. The difference between those two is r minutes.

For example, suppose you are feeling hungry and want to cook a 3 minute egg but only have a 13 minute timer and a 7 minute timer. Start the two timers at the same time and as soon as one runs out reset it. After the 7 minute timer finishes 205286400 times, start cooking the egg. Three minutes later the 13 minute timer will finish (for the 110538831st time) and you can satisfy your hunger.
;)

Title: Re: very hard puzzle
Post by avenger421 on Aug 19^th, 2005, 1:26am

[quote author=SWF

For example, suppose you are feeling hungry and want to cook a 3 minute egg but only have a 13 minute timer and a 7 minute timer. Start the two timers at the same time and as soon as one runs out reset it. After the 7 minute timer finishes 205286400 times, start cooking the egg. Three minutes later the 13 minute timer will finish (for the 110538831st time) and you can satisfy your hunger.
;)[/quote]

:o

Title: Re: very hard puzzle
Post by Grimbal on Aug 19^th, 2005, 1:55am

I think I'll take cereals for breakfast.

Title: Re: very hard puzzle
Post by Sjoerd Job Postmus on Aug 19^th, 2005, 3:06am

Ok, if you need to measure 1 minute, with 7m and 13m timers, start them, and restart the 7m when it makes rings.

When the 13 is done, it takes 1 more minute for the 7 to end once more.

To measure 3 minutes... time the 13 one 3 times, and the 7 one 6 times. when the 13 has made 3 ticks, it takes another 3 minutes for the 7 to tick.

Title: Re: very hard puzzle
Post by Icarus on Aug 19^th, 2005, 3:56pm

Just to be thorough: As Jock mentioned, the timers do not have to be prime, just relatively prime to each other. For instance timers of 12 and 25 minutes are also capable of measuring any integer length of time (assuming that you get to determine when the interval starts).

This is a consequence of this fundemental theorem of number theory:

If g is the greatest common divisor of two integers n, m, then g is the least positive value of S = {an + bm | a, b integer}.

Proof: because g|n and g|m, g|(an+bm). Hence g divides every element of S. Let d = xn + ym be the least positive value of S. There exists q, r (0 <= r < d) such that n = dq + r (division algorithm). So, r = d - qn = (xn+ym) - qn = (x-q)n + ym, and thus r is in S. Since d is the least positive value in S, r can only be 0. Therefore d|n. Similarly, d|m. Since d is a common divisor of n and m, it must divide the greatest common divisor g. So d|g, and g|d since d is in S, and both are positive by definition. Therefore d = g.

So if you have two timers with relatively prime times of n and m minutes, and you want to time 1 minute, since n and m have greatest common divisor 1, there exist a and b such that an + bm = 1. Except when n or m is 1, one of a or b is going to be negative and the other positive. Turn over both timers to start at the same time. As soon as each runs out, turn it back over. Once you have turned over the n-timer -a times (and letting it run out), your 1 minute interval starts. It will end when the m-timer runs out.

To time an interval of length d, find x,y such that xn + ym = d ((da)n + (db)m = d, but you can usually find smaller values). Assuming again that x < 0, start your interval after running the n-timer -x times, and end it after the m-timer runs y times.