15
$\begingroup$

Tom works with a stingy boss that will deduct from his salary for every minute that he's late for work. Unfortunately, Tom has to pass by the boss's office on the way to his cubicle. Being a lazy worker, Tom decides to arrive at the office exactly 1 minute before his boss every day. Tom does not know when his boss will arrive at the office as the boss's office is located far away from Tom's cubicle. One thing that Tom knows is that the boss will arrive at the office at the same time every day, no sooner, no later. Tom can pull off the "go to the washroom" trick once every day to pass by the boss's office twice (to the washroom and back from the washroom with a 5-minute interval). How many days will it take for Tom to work out his boss's time of arrival?

$\endgroup$
  • 16
    $\begingroup$ Ooh, a non-fiction puzzle! $\endgroup$ – Milo Brandt Jan 23 '15 at 4:11
  • $\begingroup$ How long is the work day? Is it correct to assume that the Boss' work day is exactly as long as Tom's? Is it correct to assume that the Boss start time is strictly on or after Tom's and not before? $\endgroup$ – LeppyR64 Jan 23 '15 at 11:40
  • $\begingroup$ Also, is it correct to assume that the boss arrives at some point during Tom's day? (The boss does not arrive after Tom is done for the day) $\endgroup$ – LeppyR64 Jan 23 '15 at 11:54
  • $\begingroup$ If the question is "how many days will Tom take?" then how is "deduct his salary for every minute that he's late for work" and "5 minutes interval for the washroom" relevant? $\endgroup$ – Spikatrix Jan 23 '15 at 14:45
12
$\begingroup$

I assume that the boss's time of arrival should be determined to the minute (say, within an error of plus/minus 30 seconds). I furthermore assume that the arrival time is any time point between 0:00 and 24:00. These assumptions then leave us with a search space of $24*60=1440$ minutes.

  1. Since Tom can perform one query per day, the current search interval should always be divided into two equal-sized large pieces plus one small piece of 5 time points (corresponding to 5 minutes washroom break).

  2. After day 1, 2, 3, 4, 5, 6, 7 the length of the large search interval piece is down to 718, 357, 176, 86, 41, 18, 7 time points (in the worst case).

  3. On day 8 (or earlier), Tom is left with a search space of at most 7 consecutive time points. Then on day 8, Tom queries the middle time point, and then is left with 3 consecutive time points. On day 9, Tom queries the middle time point, and finally has solved his problem.

My answer: In the worst case, Tom needs nine days to determine the boss's time of arrival.

$\endgroup$
  • $\begingroup$ Where do you get the two queries per day from? $\endgroup$ – Taemyr Jan 23 '15 at 12:32
  • $\begingroup$ @Taemyr: Thanks for pointing this out. I misread the problem statement, and used two washroom breaks per day. I have updated and corrected my solution. $\endgroup$ – Gamow Jan 23 '15 at 12:49
11
$\begingroup$

Lets assume that Tom is required to work for 8 hours each day, and he is supposed to start at time $T_s$.

The boss arrives at some time $T_b$ where $T_s < T_b < T_s+8h$. Since there are 60 minutes in an hour, this gives 480 minutes in a working day.

We will make the following assumptions:

  1. If Tom arrives in the same minute as the Boss and the Boss is late, the Boss will see Tom arrive and fine him.
  2. If Tom goes to/returns from the bathroom at in the same minute that the Boss arrives, Tom will see the Boss arriving know exactly the time the Boss arrives.

This gives us discrete one minute intervals to work with.

Tom is lazy, so he wants to find the largest $t_{arrive} \lt T_b$. But Tom also doesn't want to be fined any amount of money, so he must always arrive before the Boss. If we relax this rule, Tom can find out the time quicker, but at added cost.

Lets say on a typical day that Tom arrives at time $t_{arrive}$, goes to the bathroom at time $t_{bathroom}$ and returns from the bathroom at time $t_{return}$. Then, we have the following possibilities:

  1. $T_b < t_{arrive}$ - The Boss is already at work when Tom arrives, so Tom is fined.
  2. $T_b = t_{arrive}$ - The Boss arrives at the same time as Tom, and Tom is fined.
  3. $t_{arrive} < T_b < t_{bathroom}$ - The Boss arrives after Tom, but before he goes to the bathroom.
  4. $T_b = t_{bathroom}$ - The Boss arrives as Tom goes to the bathroom.
  5. $t_{bathroom} < T_b < t_{return}$ - The Boss arrives while Tom is in the bathroom.
  6. $T_b = t_{return}$ - The Boss arrives as Tom returns from the bathroom.
  7. $t_{return} < T_b$ - The Boss arrives after Tom returns from the bathroom.

Using the above, this means that if we have an interval that includes 5 exact minute marks, we can determine exactly when the boss arrives in one day with no fines.

Proof: Let the interval at which the Boss can arrive be ${t_1, t_2, t_3, t_4, t_5}$. Tom will arrive at $t_{arrive}=t_1 -2$, go to the bathroom at $t_{bathroom}=t_2$, and return at $t_{return}=t_4$. Using the possibilities above:

  1. Can't happen because we've arrived before the boss.
  2. Can't happen because we've arrived before the boss.
  3. $T_b = t_1$ since the boss arrived after Tom, but before he goes to the bathroom.
  4. $T_b = t_2$ since Tom witnesses his arrival.
  5. $T_b = t_3$ since the Boss arrived while Tom was in the bathroom.
  6. $T_b = t_4$ since Tom witnesses his arrival.
  7. $T_b = t_5$ since the Boss arrived after Tom returned from the bathroom.

If we allow fines, then the interval can increase to 7 minutes.

No Fines Solution

In order to do this with no fines, the first day, Tom must arrive at $T_s$. We can assume that the Boss arrives later than this because if he arrives at the same time, then Tom will discover this the first day.

Thus, $T_s < T_b$. Also, the Boss must arrive before the end of work, so we will also assume $T_b < T_s + 480$.

Thus, there are $479$ possibilities for $T_b$ initially.

Tom use his bathroom break like a binary search. So at around lunch time ($t_{bathroom}=T_s + 238$), he will take his break and return 5 minutes later. Since we've excluded the possibilities of fines, only the last 5 are valid options.

  1. $t_{arrive} < T_b < t_{bathroom}$
  2. $T_b = t_{bathroom}$
  3. $t_{bathroom} < T_b < t_{return}$
  4. $T_b = t_{return}$
  5. $t_{return} < T_b$

For the $2^{nd}$ and and $4^{th}$ possibilities, Tom figures out exactly the Boss's arrival time. For the $3^{rd}$ Tom has narrowed it down to the four 1 minute intervals while Tom was in the bathroom. This means that he can figure it out exactly on the second day.

Thus, the only two possibilities we need to explore further are $1$ and $5$. Each narrow the interval down to $237$ (or less) possibilities.

On the end of the second day, this interval is cut to $116$.

On the third day, it is $55$.

On the forth day, it is $25$

On the fifth day, it is $10$.

So by the end of the sixth day, the interval is only $2$, and thus small enough to figure out the next day.

Answer: 7 days

With Fines

Since Tom is in this job for the long haul, perhaps a week of fines is worth it to find the answer quicker.

Instead of a binary search, we will employ a ternary search. Basically split the interval into 3 and arrive after the first interval, and go to the bathroom after the second.

On the first day, Tom will arrive at $t_{arrive}=T_s + 158$. He will go the bathroom at $t_{bathroom}=T_s+316$ and return at $t_{return}=T_s+321$.

There are then 7 possibilities:

  1. $T_b < t_{arrive}$
  2. $T_b = t_{arrive}$
  3. $t_{arrive} < T_b < t_{bathroom}$
  4. $T_b = t_{bathroom}$
  5. $t_{bathroom} < T_b < t_{return}$
  6. $T_b = t_{return}$
  7. $t_{return} < T_b$

Options 2, 4, and 6 all determine the Boss' arrival exactly. Option 5 reduces the interval to 5 minutes which can be done in an extra day. So, the remaining options 1, 3, and 7 need to be explored. All three of these reduce the interval to $158$ minutes by the end of the first day.

By the end of the second day, the interval is $51$.

By the third day, it is $15$.

By the end of the forth day, it is $3$ and small enough to determine on the next day.

Answer: 5 days

$\endgroup$
  • $\begingroup$ +1 for using the fact that a fine gives you an exact answer. $\endgroup$ – Callidus Jan 23 '15 at 22:23
5
$\begingroup$

Does "late for work" mean "arriving later than the boss"? If so, and assuming that asking the boss or his/her secretary directly when they arrive is disallowed:

Tom arrives at a definitely late time, and asks finance how much he is being fined. If Tom doesn't know the per minute fine, he arrives one minute earlier the next day and asks again how much, then he can calculate when the boss arrives.

If there is a requirement to minimise the total number of minutes late, then this should be stated.

$\endgroup$
  • 7
    $\begingroup$ But Tom is fined for each minute from the start of his workday. Not from the time the boss arrives. It seems that the boss starts work later than the time Tom should start. $\endgroup$ – dmg Jan 23 '15 at 8:22
3
$\begingroup$

After reading the other answers, I get the impression that Tom is supposed (by contract) to start working before his boss arrives. but he doesn't want to, ok.
In order to find out about the exact moment his boss enters the company, Tom will have to be already around before his boss, obviously. I suggest there is some pattern he could follow that in the end will approximate the exact time.

But is it really necessary? If his boss arrives always at the exact point of time....why doesn't Tom simply go to work (as he is supposed to be) and wait in front of the boss' office until the boss arrives? When finally his boss is in sight, Tom uses the bathroom-trick. This way Tom would have to get up early once and would't lose a penny.

Not sure if I'm missing a detail but this would mean Tom can figure it all out within 1 day.

Edit: Obviously his co-workers are not his friends. They would tell their boss right away. So this won't work :(

$\endgroup$
  • $\begingroup$ You are missing a detail. Tom needs to be working in his office. He can be away from his desk for at most 5 minutes to "use the bathroom" $\endgroup$ – LeppyR64 Jan 23 '15 at 11:27
  • $\begingroup$ And this fact doesn't have to do anything with the boss? Even when the boss is not around Tom has to work, right? I think I get it then, thanks. $\endgroup$ – Avigrail Jan 23 '15 at 11:29
1
$\begingroup$

Let's assume that Tom is working full day (8 hours or 480 minutes).

1st day: Tom comes at 480/3=160 minute mark and goes to washroom at 160*2=320 minute mark. That way he will find out the right time with 160 minutes accuracy (divide the whole time by 3)

2nd day: Tom comes at 160/3=53.3 minute mark and goes to washroom at 53.3*2=320 minute mark (minute marks refered to the right time interval). That way he will find out the right time with 53.3 minutes accuracy.

3rd day: 17.7 minutes accuracy.

4th day: 5.9 minutes accuracy.

5th day: 1.9 minutes accuracy.

6th day: 39 seconds accuracy.

My answer is

6 days.

But I guess that "back in 5 minutes" trick will allow to do it in

5 days.

$\endgroup$
  • $\begingroup$ The problem doesn't state how Tom can determine if the boss arrived in the first third or the second third. $\endgroup$ – Ken Y-N Jan 23 '15 at 5:47
  • $\begingroup$ The "5 minutes" will not allow you to split the 5.9 minutes of day 4 in 3 parts. So at day 5 you will have 2.95 minutes. Day 6 - 1.475, day 7 - 0.7375 minutes. $\endgroup$ – dmg Jan 23 '15 at 8:20
  • $\begingroup$ @dmg 5 minutes counts after we pass by boss's office on our way to washroom. My solution doesn't work with the fact, that Tom will go back (he may even come back without peeking into boss's office). $\endgroup$ – Xellos Jan 23 '15 at 9:28
  • $\begingroup$ @Xellos I see. Nice. $\endgroup$ – dmg Jan 23 '15 at 9:38
0
$\begingroup$

Just one day.

Being lazy, Tom comes to work early, and awaits at the entrance, watching it in awe. When the Boss comes and asks why he's not working, Tom talks about how he recently discovered how beautiful world is and that he's going to paint the entrance to the factory when he gets back home, so he wants to remember the picture well. The boss will degrade him and maybe cut his payment this day, but Tom keep calm - soon he'll get to sleep much longer than before.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.