Tough Question

[Zarnaxus]

There are five clocks. Each one of them chime when it has made a full hour. They run at consistent rates but at different and incorrect rates. Each hour (according to an accurate clock) at least two clocks chime. How would i prove that i can throw away at least 3 of the 5 clocks and still end up hearing a chime at each true hour?

[Mr Skeptic]

Do you want at least two chimes every hour, or at least one?

[Zarnaxus]

at least one chime every hour with only two out of the five initial clocks

[Mr Skeptic]

OK, I think that you might be best off trying to show that at least one of the clocks must have a period of less than one hour (it runs fast rather than slow). Given that the clocks run at different rates they would get more and more desynchronized, and my guess is that 5 is not enough to chime twice every hour unless one of them runs fast. Otherwise, the clocks would have to be distributed such that they don't chime too many times sometimes and not enough others. (eg consider the number of numbers that are a multiple of both 61 and 62, clocks with 61 and 62 mins will occasionally chime simulataneously and then go an hour without chiming again). So for proof, see how many clocks will chime simultaneously.

[Zarnaxus]

Yeah... thanks for that input. I have thought some about it and i came to the same conclusion. All of the clocks can't run fast, all of the clocks cant run slow, or a multiple, like you said, of these minutes would amount so that there is an hour in which no clocks chime. BAD. ... So, i think that there is only two possibiltis to get at least two chimes per hour

fast, fast, slow, slow, slow (this is the way to get at least two chimes per hour using the most slows as possible)

fast fast fast slow slow (this is the way to get at least two chimes per hour using the most fasts as possible)

I now realize that there are at least one fast, and at least on slow in each situation. So, If i could get rid of all other clocks but a fast one and a slow one, would i get at least one chime per hour?

Is my logic correct? please, someone smart... come to my rescue!

[Mr Skeptic]

If a clock runs fast, won't it chime (more than) every hour? There can't be any hour that a fast clock wouldn't chime on.

[michel123456]

(completely edited) thinking (not so) quickly.

Take a clock that runs slow. When the right clock will show 1h, this clock will show 45min. It will chime roughly each 1h15 min. With this clock it will happen that you won't get any chime in some 1 real hour.

A clock that runs fast will chime lets say each real 5 min. With this clock you will always get a chime in every 1 real hour. You will get 12 chimes from the same clock in each hour. So a clock that runs fast will satisfy your demand.

 

IMO you have to prove that at least 2 of your 5 clocks are running fast in order to satisfy that:

Each hour (according to an accurate clock) at least two clocks chime

. Edited December 12, 2010 by michel123456

[Zarnaxus]

ok, so now i have come to the conclusion that, since a clock that ticks faster than a regular clock will have to chime at least once per hour, i must prove that taking away three of the five clocks will leave at least one fast ticking clock? sooo, how would i prove that out of these five clocks there are....four fast ticking clocks?? (if i take away three random clocks, i still might take away 3 fast ticking clocks, but will have one left to keep the one chime per hour)

[Mr Skeptic]

Oh... I thought you got to choose which clocks to throw away. If not than this is much harder than I thought, to the extent I don't think I'd be able to figure it out (if it is still possible).

[Zarnaxus]

I will reread the problem and see if i might have missed something important, if i find anything i will post it tomorrow, the problem might allow for you to choose the clocks to throw away, it might also allow for clocks to run the same as a regular clock. This would change a lot of answers and are actually big parts of the question. I'll have to see to that, but it is getting late for me.... yup

[uncool]

Oh... I thought you got to choose which clocks to throw away. If not than this is much harder than I thought, to the extent I don't think I'd be able to figure it out (if it is still possible).

You have to get to do so, as otherwise you could just have 2 really really rarely-going clocks and 3 clocks that chime on the hour.

 

 

 

So first, we only care about chimes on the hour. Therefore, if a clock chimes at an irrational fraction of an hour, then it can be thrown away as a 0. Otherwise, it chimes at a fraction a/b of the hour. We only really care about a, since that is how many hours it is until it chimes on the hour again. Now, if a is 1, then we are done. Otherwise, consider the proportion of the number of hours on which there are chimes (weighted by the number of chimes). That would be at least 2, and would have to be equal to the sum of the 1/a. Therefore, at least one of the 1/a is 1/2 (since 5*1/3 = 5/3 < 2). Now the rest have to add up to at least 1 1/2, so another one is 1/2.

 

We then have that either these two chime on different hours, or the same hours. If they chime on different hours, we are done. Therefore, assume they chime on the same hour. That means that we must get that between the 3, we have 2 chimes every 2 hours. Consider, then, the proportion of the number of these hours on which there are chimes. That would be at least 2, and would have to be equal to the sum of the 1/(a/2 if a is even, a if a is odd). Then one of them would have to be 1, so one of the clocks chimes every other hour on these hours. Therefore, take that one and the original 1/2, and we are done.

 

=Uncool-

[michel123456]

It is provable that for any δt (positive or negative difference between right and wrong hour) of 5 clocks, they will in a finite amount of time T, all chime together.

From this time T and after, the system still responds to the demand that "each hour (according to an accurate clock) at least two clocks chime".

The rest is in post #7. (edition 1)

Edited December 12, 2010 by michel123456

[Zarnaxus]

IMPORTANT In the problem, the clocks tick at POSSIBLY different and incorrect rates. So, some clocks could tick at same as regular time, and clocks can tick at the same rate. I have to prove that i can throw out three of the five clocks to hear at least one chime per hour. SO, i have come to the conclusion that this is a probability problem since if you could choose the clocks, you could just choose to keep the one that ticks at same as regular time or a faster ticking clock (there has to be some or there wouldn't be two chimes per hour with all five). And that would mean that you could just get rid of four. we have to throw away AT LEAST three of the five clocks though, but still. this is probably a probabilty problem somewhat or somehow. i should use somekind of math or proof or justification to show my understanding. buuut,

 

there could be two regular ticking clocks and three slow ticking clocks, and in this situation, i could end up throwing away both the regular ticking clocks and just have the slow ones. With just the slow ticking clocks there could be a situation (not likely) that they all chime together right before an hour is up in regular time. The next hour, they might not all chime! sooo, i have no idea what to do. Is there a percentage taking into consideration all variables that after taking away three clocks i'll still hear a chime per hour. im not at a very high level in my math skills. well, not yet...

[Mr Skeptic]

Oh, that changes the problem considerably. I was thinking the clocks had to be different rates, in which case they'd have to synchronize once in a while. But if they can run at the same rate then they can forever stay out of synch. For example, three clocks running 40 mins every real hour could chime once every real hour but never together. I think the only options to chime twice every correct hour are:

1) 2 clocks running at the correct rate or an integer times faster, the other clocks anything else

2) 1 clock running at the correct rate or an integer times faster, the others 4 @ once correctly every 4 hours, or 3 @ once correctly every 3 hours, or 2 @ once correctly every 2 hours

3) 3 @ once correctly every 3 hours, and 2 @ once correctly every 2 hours

 

In all cases, a group of 2 or less clocks is enough for once correctly every hour.

[Zarnaxus]

umm sorry, but could you explain the options 2 and 3 again? i am confused with the @s er i dunno. im confused when you say...@ once correctly ... palease?

[Mr Skeptic]

@ just means at. There's more than one way to get a clock to chime at a given interval of hours, for example one running at 40 min = 60 real min, and one running at 80 min = 60 real min, will both chime correctly every three hours.

[khaled]

There are five clocks. Each one of them chime when it has made a full hour. They run at consistent rates but at different and incorrect rates. Each hour (according to an accurate clock) at least two clocks chime. How would i prove that i can throw away at least 3 of the 5 clocks and still end up hearing a chime at each true hour?

 

? Just to let you know, this question is under Theoretical Computer Science - Distributed Systems - Synchronization & Clocks ...

 

> you have 5 Clocks, denoted C1, C2, .., C5 .. with different consistent rates ...

 

1. you calculate Clock-per-Clock Drift (difference in rate), so you have 10 drift rates ...

---- Dij = rate difference between Clock Ci and Clock Cj

 

2. get minimal Dij among the 10 Drift Rates

 

3. by choosing Dij, you keep Clock Ci and Cj only, throwing other clocks

 

:: you will get 2 ticks per hour, unless if Dij (minimal D) is Zero, but the error is minimized as possible ...

 

----------------------------------------------------------------------------------------------------

 

example:

 

assume that every clocks, gives the skew (difference in reading) per second:

-- C1 = -1.05, C2 = +0.8, C3 = +0.2, C4 = -1.0, C5 = +0.35

 

Dij: D12 = 1.85, D13 = 1.25, D14 = 0.05, D15 = 1.4, D23 = 0.6, D24 = 1.8,

-- D25 = 0.45, D34 = 1.2, D35 = 0.15, D45 = 1.35

 

choosing minimum Dij: D14 = 0.05

 

solution: keep clocks C1 and C4, throw other clocks

result: you will get two ticks with 0.05 difference every hour

constraint: the clocks must be hourly synchronized

[michel123456]

? Just to let you know, this question is under Theoretical Computer Science - Distributed Systems - Synchronization & Clocks ...

 

> you have 5 Clocks, denoted C1, C2, .., C5 .. with different consistent rates ...

 

1. you calculate Clock-per-Clock Drift (difference in rate), so you have 10 drift rates ...

---- Dij = rate difference between Clock Ci and Clock Cj

 

2. get minimal Dij among the 10 Drift Rates

 

3. by choosing Dij, you keep Clock Ci and Cj only, throwing other clocks

 

:: you will get 2 ticks per hour, unless if Dij (minimal D) is Zero, but the error is minimized as possible ...

 

----------------------------------------------------------------------------------------------------

 

example:

 

assume that every clocks, gives the skew (difference in reading) per second:

-- C1 = -1.05, C2 = +0.8, C3 = +0.2, C4 = -1.0, C5 = +0.35

 

Dij: D12 = 1.85, D13 = 1.25, D14 = 0.05, D15 = 1.4, D23 = 0.6, D24 = 1.8,

-- D25 = 0.45, D34 = 1.2, D35 = 0.15, D45 = 1.35

 

choosing minimum Dij: D14 = 0.05

 

solution: keep clocks C1 and C4, throw other clocks

result: you will get two ticks with 0.05 difference every hour

constraint: the clocks must be hourly synchronized

(emphasis mine)

 

That is a lot of calculation to finally choose the 2 clocks with negative value. See my post #7.

[khaled]

(emphasis mine)

 

That is a lot of calculation to finally choose the 2 clocks with negative value. See my post #7.

 

Your answer is true, if we are not working according to given Algorithm or a method,

Well, i study clocks and synchronization, calculations are needed to elect clocks ...

 

his problem has many options:

 

- choose two clocks that chime with minimal drift, 2 chimes hourly,

 

- choose two clocks that chime perfectly at some point, the second clock is faster by some rate, they meet

-- at some point, the faster clock should chime at (assuming that drift is measured by minutes) (60/drift)*60 O'clock

-- the slower clock will chime at ((60/drift)*60) - 1,

 

- choose two clocks with minimal drift from nominally perfect reference, to chime on a synchronization point

-- synchronization point is where clocks are synchronized to interpolated value between readings,