17 Offices

[sputnik15]

Hello I am new here. I love riddles. This is one that was given to me by a Math professor. I hope it hasn't already been done in these forums. I had a lot of fun trying to figure this one out.

Albert and Brenda want to locate their professor. The professor has 17 offices in which she can be found, and moves from one office into an adjacent office precisely every hour, on the half hour (1:30, 2:30, 3:30 etc.). Albert and Brenda have classes every hour all day, and can only afford enough time to each search one office every hour, on the hour (1:00, 2:00, 3:00). The offices are arranged linearly, so the professor will not move directly from office 17 to office 1 or vise versa. The starting location of the professor is unknown.

If Albert and Brenda share information, how soon can they expect to find their professor? Give answer in number of hours, plus give your algorithm.


Remember, the problem is to find the professor in the most efficient manner possible. The answer that I and my Math prof have is the fastest one that we know of. Have fun.

[Snark]

How does the professor decide where to go? Is it a 50% chance either way?

[JBJ]

Can the professor move back into a previously used office?
In other words, can professor move from office 4, to office 5, to office 6, then back to office 5, then back to office 4? Or is the professor committed to moving in a single direction once started?

[Qaanol]

Assuming the professor can move in either direction, choosing which direction by a process unknown to the students, and assuming the students can communicate instantly, here’s my first attempt.

Spoiler:

This method takes a maximum of 8 search steps to locate the professor. Here are the pairs of offices to check:
(1, 2) or (2, 4), doesn’t matter which
(2, 4)
(4, 6)
(6, 8)
(8, 10)
(10, 12)
(12, 14)
(14, 16)
If they haven’t found the professor yet she is in 17, so go there immediately or go to 16 next hour.

[Snark]

Assuming the professor can move in either direction, choosing which direction by a process unknown to the students, and assuming the students can communicate instantly, here’s my first attempt.

Spoiler:

This method takes a maximum of 8 search steps to locate the professor. Here are the pairs of offices to check:
(1, 2) or (2, 4), doesn’t matter which
(2, 4)
(4, 6)
(6,
(8, 10)
(10, 12)
(12, 14)
(14, 16)
If they haven’t found the professor yet she is in 17, so go there immediately or go to 16 next hour.

Spoiler:

What if the professor moved in this manner: 5-6-5-4-3-2-1-2-1-2-1....

The improvement to your plan is this:
(2,4)
(2,4)
(4,6)
(4,6)
and so on doing each of the steps you did but twice. This solves the problem of missing the professor but increases the minimum number of steps necessary to find her.

[Nitrodon]

I believe this is optimal, but I don't have a proof:

Spoiler:

(2,4)
(5,7)
(8,10)
(11,13)
(14,16)
(2,4)
(5,7)
(8,10)
(11,13)
(14,16)

[Snark]

I believe this is optimal, but I don't have a proof:

Spoiler:

(2,4)
(5,7)
(8,10)
(11,13)
(14,16)
(2,4)
(5,7)
(8,10)
(11,13)
(14,16)

Spoiler:

Your solution is definitely exhaustive. The professor would be unable to avoid being found. But I also have no proof of optimality.

[sputnik15]

I believe this is optimal, but I don't have a proof:

Spoiler:

(2,4)
(5,7)
(8,10)
(11,13)
(14,16)
(2,4)
(5,7)
(8,10)
(11,13)
(14,16)

This is the most optimal answer. Or at least I have never seen a more optimal algorithm for 17 offices. Well done! You answered this fast.

Apparently the proof for this is too complex for my aforementioned Math professor to bother with.

[sputnik15]

Can the professor move back into a previously used office?
In other words, can professor move from office 4, to office 5, to office 6, then back to office 5, then back to office 4? Or is the professor committed to moving in a single direction once started?

The professor can move in any direction

[mfb]

I can prove that at least 9 checks are required:

Spoiler:

The professor can start in an even or in an odd office number. Let's begin with the case of an even number:
Consider the following patterns:
2->1->2->1->...
2->3->2->3->...
4->3->4->3->...
4->5->4->5->...
...
16->15->16->...
16->17->16->...

There are 16 patterns, each visit in a room can check 2 of them unless it is 17 or 1. A naive estimate would give 16/2/2=4 checks to find the professor.
However, the visits at odd and even hours have detection patterns which are shifted with respect to each other. If both are used, there has to be an overlap. Therefore, it is not possible to find the professor (beginning in an even office number) with 4 checks, if they happen at even and at odd hours*. It is possible to do so with 5, as Nitrodon showed.

*it is possible to find him, of course, but you cannot be sure about that. In addition, if the professor knows your algorithm and knows how to hide, you will never find him.

Extension: It is not possible to find the professor with 4 checks at hours (1,3,5,7).
Proof: Assume that this would be possible. Using the patterns 2->1->2, 4->3->4, ... it can be shown that these 4 checks have to visit all 8 even offices once. Therefore, no office can be visited twice. Now, look at an even office x (not 2 and not 16) which is checked at the second or third check (hour 3 or 5). Let the professor be in this office before the check. At hour 3 or 5, he can be in the office (x-2) or (x+2), as it is not possible to check both at the same time (together with the check of x), and return to office x for later checks. Therefore, no algorithm can guarantee to find the professor with these checking times.
Waiting an even number >2 hours before the first check or between two checks does not help, the professor can just "wait" an even number of hours by moving x->x+1->x too. Therefore, It is not possible to find the professor with 4 checks at odd hours.

In addition, It is not possible to find the professor with 4 checks at even hours, which is trivial as their are 9 odd office numbers.

Corollary: If the professor starts in an even office number, it is not possible to find the professor with 4 checks at all.
As I did not use the "first hour" in an explicit way, the same is true for an odd starting number.

In addition, it does not help to split checks between even and odd office numbers: You still have to visit more than 8 offices for each parity. As the professor can begin in even or in odd office numbers, both cases have to be checked with at least 9 visits, which require at least 9 hours where Albert and Brenda have to search their professor.

I think it is possible to prove the required 10th visit per parity by checking the cases a bit more carefully.

Hypothesis: Once the professor knows that you know how you can find him, he modifies his behaviour.

[ineon]

Apparently the proof for this is too complex for my aforementioned Math professor to bother with.

I believe the correct wording is: "This can be left as an exercise for the reader".

[mike-l]

Essentially this, with 2 checks instead of 1, and obviously more options.

[tomtom2357]

I can prove that at most 16 checks are required
{1,16}
{2,15}
{3,14}
{4,13}
...
{16,1}

[mfb]

We already have a solution with 10, therefore an upper limit of 16 is not really useful.
A lower limit of 10 (which I would expect) or a solution with 9 (which would surprise me) can close the remaining gap between upper and lower limit.

[jonachin]

if the professor is limited to moving linearly, why aren't the students?

[Snark]

if the professor is limited to moving linearly, why aren't the students?

It's a logic puzzle. There is no "why".

[Nitrodon]

I think I have a proof of optimality now.

Spoiler:

Suppose the professor is in an office of known parity, and let N denote the number of offices she could possibly be in with your current knowledge. When you check an office, N will decrease by 1 (and this can be done twice in an hour). Consider what happens when to N when the professor moves.

* If he moves from an even office to an odd office, then she can move to any office immediately left of a current possibility, plus the one immediately right of the rightmost possibility. Thus, N increases by at least 1.
* If he moves from an odd office to and even office, and N<9, then there is at least one odd office she currently can't be in. From any current possibility, she can move in the direction of that office, and there is no overlap here either. Thus, N does not decrease.

Thus, N will increase by 1 at least once in any 2-hour span (after you start eliminating offices). You will first check an office of the appropriate parity at a certain time; call it hour 1. At this time, N is at least 8, so you need to check at least 8 offices. However, N would increase by 1 between hours 1 and 3, and it is impossible to finish checking 8 offices by this point. This gives a lower bound of 9 offices checked, which requires a fifth hour. N increases one more time between hours 3 and 5, so you need to check at least 10 offices of the appropriate parity.

In conclusion, you need to perform 10 checks corresponding to the case where the professor starts in an even office, and 10 more corresponding to the case where she starts in an odd office. That is, you need to check 20 offices in total, which requires 10 hours.

[mfb]

I think I have a proof of optimality now.

I think so, too.

We can decrease N by 2 in hours with even office numbers and by 1 elsewhere. With 19 offices, this requires 6 hours:
(2,4)
(5,7)
(8,10)
(11,13)
(14,16)
(17,19)
(1,3)
(4,6)
(7,9)
(10,12)
(13,15)
(16,18)

It is easy to see that this pattern can be extended to larger office numbers (and that it can handle an even number of checks per parity). It reduces N by 2 with checks of the even numbers and N by 1 with checks of odd numbers. Therefore, it is optimal, and your lower bound can be realized if the total number of offices is odd.

[Danny Uncanny7]

If Albert and Brenda share information, how soon can they expect to find their professor? Give answer in number of hours, plus give your algorithm.

Expected value is different from maximum value. All of these algorithms are minimizing the maximum number of checks, not minimizing the expected number of checks.

[mfb]

sputnik already confirmed that the maximal time to find the professor is important. For the expectation value, we need data about the initial professor distribution and the probability of him moving left/right.
Assuming uniform distribution and 50% left/50% right: As the 10-check solution visits just 20=17+3 offices, it might be optimal for the expectation value, too.