Searching for a Monkey in 17 Rooms

Date: 08/25/2004 at 05:20:11
From: Dan
Subject: a monkey in 17 rooms problem

There are seventeen rooms next door to each other, ie: room 1 connects
to room 2, room 2 connects to rooms 1 and 3 and so on.  Rooms 1 and 17
do not connect to each other.
 
There is a monkey in 1 of the 17 rooms.  Every night, the monkey moves 
one room to the right or left.  A person can check 2 rooms in a day.
What is his strategy to find the monkey in the least days possible?

The problem is kind of hard to solve.  I was able to find a solution,
but I'm not sure if it's the optimal one.

My best solution is the following:

 day: rooms
  1 :  1-3
  2 :  1-4
  3 :  2-5
  4 :  3-6
  5 :  4-7
  6 :  5-8
  7 :  6-9
  8 :  7-10
  9 :  8-11
 10 :  9-12
 11 : 10-13
 12 : 11-14
 13 : 12-15
 14 : 13-16
 15 : 14-16

Thanks for looking at my problem.

Date: 08/26/2004 at 12:15:23
From: Doctor Vogler
Subject: Re: a monkey in 17 rooms problem

Hi Dan,

Thanks for writing to Dr Math.  Clever problem!  And nice solution! 
You can improve it by one step by applying the same trick you used at
the end (never looking in room 17) at the beginning, like so:

   1: 2-4 (monkey can be anywhere today)
   2: 2-5 (monkey can't be in 1 or 3 today)
   3: 3-6 (monkey can't be in 1, 2, or 4 today)
   4: 4-7 (monkey can't be in 1, 2, 3, or 5 today)
   5: 5-8
   6: 6-9
   7: 7-10
   8: 8-11
   9: 9-12
  10: 10-13
  11: 11-14 (monkey must be in 11, 13, 14, 15, 16 or 17 today)
  12: 12-15 (monkey must be in 12, 14, 15, 16 or 17 today)
  13: 13-16 (monkey must be in 13, 15, 16 or 17 today)
  14: 14-16 (monkey must be in 14 or 16 today)

Now we might wonder if this is optimal, since it certainly is a pretty
good solution, so the question is how to prove that it cannot be done
in fewer than 14 days.  So I got to thinking hard about this (before
determining that it's not true).

Consider that there are 17 places that the monkey might be found.  Now
you look in two rooms, and suppose that you don't find the monkey
(because otherwise you're done), so you have restricted where the
monkey might be tomorrow.  How much restriction can you give on each
day?  That is, how quickly can you reduce the number of rooms he might
be in?  If you look at your (modified) algorithm, you'll notice (as
I've noted) that each day you take away one more room than the
previous day, except for three times, when you take away two rooms in
one day.  If we can prove that you cannot take away more than one room
at a time except for three times (which we can't prove, as it turns
out - but I didn't know this when I started), then we will have proven
that it takes at least 14 steps.  Since we have an algorithm, we
already know it's possible in 14 steps, so we will be done.

Suppose you know that the monkey might be in any of n different rooms
today.  You look in two of them, so that means that he might move from
any of n-2 different rooms into neighboring rooms tomorrow.  So you
want to know how you can lay out those n-2 rooms so that the
neighboring rooms are as few as possible.  Or, rather, you want to
prove that n-2 rooms must neighbor at least n-1 rooms (restricting no
more than one more room) except in very special circumstances.  Then
you want to show that those special circumstances can't happen more
than three times.  ... Can they?

So you have a set of n-2 different rooms, and you want to know how
many neighboring rooms there are.  Each room has either 1 or 2
neighboring rooms, but some of these might overlap.  Each room except
one (room 17) has a neighboring room to the right, so you know there
will be at least n-3 neighboring rooms.  For example, all 9 odd rooms
have only 8 neighboring rooms, the even ones.  In fact, this is the
*only* way that there will be only n-3 neighboring rooms, since rooms
1 and 17 must both be in your set, and every right neighbor must be
somebody else's left neighbor.  You can use this step that resticts
three rooms at once with a pattern like this:

   1: 8-10 (monkey can be anywhere today)
   2: 7-11 (monkey can't be in 9 today)
   3: 6-12 (monkey can't be in 8 or 10 today)
   4: 5-13 (monkey can't be in 7, 9, or 11 today)
   5: 4-14 (monkey can't be in 6, 8, 10, or 12 today)
   6: 3-15 (monkey can't be in 5, 7, 9, 11, or 13 today)
   7: 2-16 (monkey can't be in any other even room today)
   8: 2-16 (monkey must be in an even room today)
   9: 3-15 (monkey must be in 3, 5, 7, 9, 11, 13, or 15 today)
  10: 4-14 (monkey must be in 4, 6, 8, 10, 12, or 14 today)
  11: 5-13 (monkey must be in 5, 7, 9, 11, or 13 today)
  12: 6-12 (monkey must be in 6, 8, 10, or 12 today)
  13: 7-11 (monkey must be in 7, 9, or 11 today)
  14: 8-10 (monkey must be in 8 or 10 today)

Notice that we get one more room restriction each day, except three on
day 7, and two on day 14.

Now, back to the point:  If room 17 is not in your set, then there
will be at least n-2 neighboring rooms, since every room has a right
neighbor.  Similarly, each room except one has a neighboring room to
the left.  So you know that if room 1 is not in your set, then there
will be at least n-2 neighboring rooms.  Now let's consider all the
ways we might have exactly n-2 neighbors.  If room 1 is in our set but
not 17, and we have n-2 neighbors, then it will be the right neighbors
of all of the rooms, which means that all of the other n-3 (not
counting room 1) left neighbors must be right neighbors of other
rooms.  In other words, we must have the first n-2 odd rooms,

  1, 3, 5, 7, ... 2n-5.

Similarly, if room 17 is in our set but not 1, then we must have the
last n-2 odd rooms,

  23-2n, ... 13, 15, 17.

Next, if both 1 and 17 are in our set, then we have all right
neighbors and one additional left neighbor, or all left neighbors and
one additional right neighbor.  Can you think of what kinds of sets
will satisfy this requirement?  Consider what that one extra left or
right neighbor is, and what does that tell you about the rest of the
rooms?

Finally, in the last case, if n-2 = 0, so our set is empty, then we
certainly have no neighbors, so we can always restrict two rooms at
the last step.

Then I stopped and wondered why I can't alternate odds and evens from
one side to the other, and I came up with this strategy:

  1: 1-3
  2: 4-6
  3: 7-9
  4: 10-12
  5: 13-15
  6: 16-17
  7: 14-16
  8: 11-13
  9: 8-10
  10: 5-7
  11: 2-4

You'll find that I restrict two rooms instead of one on every other
step and the last step.  The ones in between have even numbers, and
that can't be helped; if you get odds on one day, then you'll get
evens on the next.  So I think you can prove that this is optimal, and
I've given you most of the details that you would need to finish up
the proof.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/26/2004 at 12:22:57
From: Dan
Subject: Thank you (a monkey in 17 rooms problem)

Thanks, Dr. Vogler.  It's quite a long and interesting solution!

Date: 10/14/2005 at 10:31:08
From: Chris
Subject: Searching for a Monkey in 17 Rooms problem

Your solution can be improved by one day from 11 days to 10 days using the following moves:

 1:  2   4 
 2:  5   7 
 3:  8  10 
 4: 11  13 
 5: 14  16 
 6:  2   4 
 7:  5   7 
 8:  8  10 
 9: 11  13 
10: 14  16

You claim that yours may be provably optimal.  The idea is, but the
starting point requires that you take one extra day.

Mine is optimal.  I have checked by brute force.  Create a graph with
vertices labeled by where the monkey may be, and edges labeled by
possible moves.  Then compute the shortest path from all rooms unknown
to all rooms known.  This gives my solution.

Thanks :)

Chris

Date: 10/14/2005 at 18:14:40
From: Doctor Vogler
Subject: Re: Searching for a Monkey in 17 Rooms problem

Hi Chris,

Thanks for writing to Dr Math.  Very clever!  You are absolutely correct!

   1:  2   4 (monkey can be anywhere today)
   2:  5   7 (monkey can't be in 1 or 3 today)
   3:  8  10 (monkey can't be in 2, 4, or 6 today)
   4: 11  13 (monkey can't be in 1, 3, 5, 7, or 9 today)
   5: 14  16 (monkey can't be in 2, 4, 6, 8, 10, or 12 today)
   6:  2   4 (monkey can't be in any odd today, must be in an even)
   7:  5   7 (monkey must be in 5, 7, 9, 11, 13, 15, or 17 today)
   8:  8  10 (monkey must be in 8, 10, 12, 14, or 16 today)
   9: 11  13 (monkey must be in 11, 13, 15, or 17 today)
  10: 14  16 (monkey must be in 14, or 16 today)

Obviously I never went through the details of proving that I had an
optimal solution.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/