Author |
Topic: very hard puzzle (Read 1971 times) |
|
avenger421
Guest
|
Prove that any pair of timers that time a different prime number of minutes each can time any length of time in whole minutes.
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Re: very hard puzzle
« Reply #1 on: Aug 18th, 2005, 11:02am » |
 Quote  Modify
|
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 ...?
| hidden: | | ... 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. |
|
| « Last Edit: Aug 18th, 2005, 11:34am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: very hard puzzle
« Reply #2 on: Aug 18th, 2005, 11:35am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 18th, 2005, 11:35am by River Phoenix » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: very hard puzzle
« Reply #3 on: Aug 18th, 2005, 11:54am » |
Quote Modify
|
on Aug 18th, 2005, 11:35am, River Phoenix wrote:| 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. |
|
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_med ium;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.
|
| « Last Edit: Aug 18th, 2005, 12:03pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: very hard puzzle
« Reply #4 on: Aug 18th, 2005, 12:29pm » |
Quote Modify
|
OK I get it. That's pretty solid 
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: very hard puzzle
« Reply #5 on: Aug 18th, 2005, 5:29pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
avenger421
Guest
|
[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]
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: very hard puzzle
« Reply #7 on: Aug 19th, 2005, 1:55am » |
Quote Modify
|
I think I'll take cereals for breakfast.
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: very hard puzzle
« Reply #8 on: Aug 19th, 2005, 3:06am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 19th, 2005, 3:07am by Sjoerd Job Postmus » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: very hard puzzle
« Reply #9 on: Aug 19th, 2005, 3:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove