2

I have multiple events (labeled $a, b, c,\dots$) that happen every $t_a, t_b, t_c$ times, they are certain (not random!).

An easy example would be: 3 events, (a) one every hour ($t_a = 60$ min), (b) one every two hours ($t_b = 120$ min), (c) one every three hours ($t_c= 180$ min).

My question is: How long do I have to wait that I have witnessed 5 events (no matter which)?

I guess I could just wait 5 hours and would have witnessed event (a) 5 times. But this is not time-efficient, because already after 3 hours I should have witnessed event (a) 3 times, event (b) once and (c) once.

Is there a general formula I could use? I want to have the possibilities for events occurring at same intervals.

I am happy for every hint, because I cannot solve that problem :(

Kenta S
  • 16,151
  • 15
  • 26
  • 53
  • No no, nothing is random here. I know times t_x, I just can’t wind my head around a formula to calculate – canIchangethis Jul 23 '20 at 10:16
  • Sorry, seems I have misunderstood the question. – Peter Jul 23 '20 at 10:17
  • No worries, it helps me to improve my question writing. – canIchangethis Jul 23 '20 at 10:17
  • Not very efficient, but always feasible is to take the gcd of the times and to calculate the number of events after every multiple of this gcd. But there should be a better approach. – Peter Jul 23 '20 at 10:20
  • Are the events synchronized -- is there a time, $T$ (perhaps $0$ in the example you gave) where all the events occur at the same moment? And do we, solving the problem, know what $T$ is? – John Hughes Jul 23 '20 at 10:24
  • @JohnHughes they are nearly synchronised, I think for the question this can be assumed. We don’t know what time $T$ is but it is save to assume it is t==0. One could also do two cases, one that you are right before $T$ and one where you just missed thy sycronised start $T$, that actually would be my favourite! – canIchangethis Jul 23 '20 at 10:28

1 Answers1

2

One way to approach this is to think adversarially: suppose that I'm the one who gets to start the three different trains of events, and I want you to wait as long as possible.

By renaming, let's assume that $t_a < t_b < t_c$. (The case where two or more are equal I leave to you). I'm going to say that you start waiting for your five events at time $T = 0$, but I'm going to be very particular here: If there's an event at time $0$, I want that to not count, i.e., you're looking for events in the interval $0 < T \le Q$ for some value of $Q$. Again, if you want to include the "starting moment", that's a case you have to work out for yourself.

By changing units of time, I'm going to assume $t_a$ is $1$. (I.e., if $t_a$ is 11 seconds, then I'm going to declare a gleep to be $11$ seconds, and say that $t_a$ is $1$ gleep, and measure $t_b$ and $t_c$ in gleeps as well.)

If $t_b$ and $t_c$ are huge (larger than $5$), you have to wait $5$ to observe $5$ events, for I, as your adversary, will put the first $A$ event at $T = 0$ (which you'll miss), another at $T = 1, 2, 3, 4, 5$, and by $T = 5$ you'll have observed one "A" event at each of those five times, so the total wait will be $5$. (or $5$ gleeps, if you like.)

But what if, as in your example, $t_b < 5$. Then I can avoid any $B$ events as long as possible by starting the $B$ sequence at $0$ as well --- you'll JUST miss the first one, notice a second one (the first that you count) at time $t_b$, another at time $2t_b$, and so on.

The same rationale applies to $t_c$: I can delay your seeing any $C$ events as long as possible by placing the first $C$ event at $T = 0$ as well.

What I'm doing in each case is trying to make sure that you have to wait as long as possible for five events to accumulate.

Let me simplify for a moment, and look at just TWO events, with $t_a = 1$ and $t_b = 2$. Drawing a picture, we have

*---*---*---*---*---*---*---
*-------*-------*-------*---
    1   3   4   6   7

where the first row shows event $A$ happening every so often, and the second shows event $B$ happening twice as often, and the third row shows the count of events "since time 0" (ignoring the two events at time zero).

Notice here that there is never a moment when this count is exactly five.

The function that takes "time" to "events seen so far" is not 1-to-1, so there's not going to be a "formula" for the inverse. But there will be a good algorithmic way to compute the inverse, so it's OK.

Let's look at cases. (I apologize for this rambling approach...I'm developing the answer as I type).

Case 1: $t_b, t_c \ge 5$. Solution: $T = 5$ is the longest you might have to wait for one event.

Case 2: $t_b < 5; t_c \ge 5$. Solution: because $t_b < 5$, you're going to see at least one $B$ event before you get to the 5th $A$ event. If $t_b$ is between $4$ and $5$, then the $B$ event will be the fifth one you see, and we're done. If $t_b < 4$, then things are more subtle: you might see TWO $B$ events before time $5$. If the second one is between $4$ and $5$, then we'll ignore it, because we'll already have seen 4 $A$ events and 1 $B$ event. But if the second comes before $4$, then we have to count it. So the solution for the case $t_c \ge 5, t_b < 5$ looks like this:

  1. If $4 \le t_b < 5$, then you'll see (at least) 5 events in time $T = t_b$. Otherwise...

  2. if $3 \le 2 t_b < 4$, then you'll see (at least) 5 events in time $T = 4$. Otherwise...

  3. if $2 \le 2 t_b < 3$, you'll see 5 events in time $T = 2t_b$, Otherwise...

  4. if $2 \le 3 t_b < 3$, then $T = 3$. Otherwise...

  5. if $1 \le 3 t_b < 2$, then $T = 3t_b$ ...

I've probably got some of those cases wrong, but I'll bet you can work them out. The point is that after $S$ seconds, you'll have seen $$ \newcommand{\floor}{\operatorname{floor}} $$

  • $\floor(S/t_a)$ events of type $A$
  • $\floor(S/t_b)$ events of type $B$
  • $\floor(S/t_c)$ events of type $C$

The sum of these is the number of events you'll have seen in $S$ units of time, when the adversary schedules the events as nastily as possible. You want to find the largest $S$ where this sum is five. The good news is that there are finitely many possibilities, all of them being multiples of $t_a, t_b, t_c$. The magic moment could be any of $t_a, 2t_a, 3t_a, \ldots, 5t_a$, $t_b, 2t_b, \ldots, 5t_b$, $t_c, \ldots, 5t_c$. That's exactly 15 cases to check. You can slightly reduce this by letting $$ M = \floor(5 t_a / t_b) \\ K = \floor(5 t_A / t_c). $$ Then you need to check $$ t_a, 2t_a, \ldots, 5t_a\\ t_b, 2t_b, \ldots, M t_b \\ t_c, 2t_c, \ldots, Nt_c $$ where each of $M$ and $N$ will be at most 5, but probably less (and could be less than $1$, in the case where $t_b$ and $t_c$ are "large" (i.e., greater than $5 t_a$).

Summary: there's not a formula, but there's a very well-bounded computational problem to solve. If you wanted to know how long you had to wait for $3187$ events, it'd be a mess. For five? Not so bad.

John Hughes
  • 93,729