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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.