Author |
Topic: Hotel Door Knocking (Read 3437 times) |
|
FiBsTeR
Senior Riddler
Gender: 
Posts: 581
|
 |
Hotel Door Knocking
« on: Jul 31st, 2012, 12:46am » |
 Quote  Modify
|
I'm staying in a hotel with 17 rooms laid out in a line. You are trying to find me: every day, you pick a door and knock on it. If I'm there, I come out and you win. Otherwise, I move to an adjacent room. Given that I don't want to be found, how many days do you need to find me?
|
|
 IP Logged |
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Hotel Door Knocking
« Reply #1 on: Jul 31st, 2012, 4:23am » |
Quote Modify
|
on Jul 31st, 2012, 12:46am, FiBsTeR wrote:| Otherwise, I move to an adjacent room. |
|
Adjacent with respect to your current position, right?
If it were adjacent to where I knocked last, then this would be trivial, so I will assume that you move next to where you were.
|
| « Last Edit: Jul 31st, 2012, 4:41am by peoplepower » |
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Hotel Door Knocking
« Reply #2 on: Jul 31st, 2012, 4:57am » |
Quote Modify
|
Yep, adjacent to where I was.
|
|
IP Logged |
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Hotel Door Knocking
« Reply #3 on: Jul 31st, 2012, 5:22am » |
Quote Modify
|
Looking at a smaller case, here's how I thought one might accomplish the objective with 5 doors; I just list which door to knock on for each day:
2,2,3,4,4,3,2,2
The reasoning is this:
You must begin in rooms #3-#5 in order to not be caught in the first two knocks.
If you begin in #3 or #5, then you will be in #3 or #5 after the first two knocks; #3 is not safe, so you are in #5, and after two more knocks you are caught.
The other case is when you begin in #4. You will either be in #4 or #2 after the first two knocks. After the third knock, you will be in #1,#3, or #5. Notice how this is symmetric with the starting positions considered above.
Edit: If that works, it appears the obvious extension will work in general giving an answer of 2*(2*7+7)+2=44 with no claim of optimality.
|
| « Last Edit: Jul 31st, 2012, 5:32am by peoplepower » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hotel Door Knocking
« Reply #4 on: Jul 31st, 2012, 10:43am » |
Quote Modify
|
2 N should be more than sufficient, I think; but not optimal for all N
If I start by assuming your in an odd numbered room, I can eliminate that hypothesis by knocking on rooms 1-17 on consecutive days; then just repeat because if you started in an even numbered room then after 17 days you'd be in an odd numbered room.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Hotel Door Knocking
« Reply #5 on: Aug 2nd, 2012, 4:40am » |
Quote Modify
|
on Jul 31st, 2012, 10:43am, towr wrote:2 N should be more than sufficient, I think; but not optimal for all N
If I start by assuming your in an odd numbered room, I can eliminate that hypothesis by knocking on rooms 1-17 on consecutive days; then just repeat because if you started in an even numbered room then after 17 days you'd be in an odd numbered room. |
|
You can save four by starting with even rather than odd
|
|
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Hotel Door Knocking
« Reply #6 on: Aug 2nd, 2012, 8:23am » |
Quote Modify
|
2 N - 4 is what I have as well... unfortunately, I've been struggling for quite a while trying to prove optimality, with no luck.  Any ideas?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Hotel Door Knocking
« Reply #7 on: Aug 3rd, 2012, 5:42am » |
Quote Modify
|
on Aug 2nd, 2012, 8:23am, FiBsTeR wrote:| 2 N - 4 is what I have as well... unfortunately, I've been struggling for quite a while trying to prove optimality, with no luck. Any ideas? |
|
I like to think of it as a cross between battleships and draughts - if you extend an n-wide chessboard infinitely in one direction, start with a pawn on an unknown square of the first row, then repeatedly: you try to guess which square it's on, then it moves diagonally forward one square. If you do that, then that game is (mathematically) equivalent to this one.
Note that the checkerboard pattern of alternating black and white squares highlights the parity invariant for the pawn - if it starts on a white square, it will always be on a white square, and similarly for black. This means you can solve the problem for white squares and then for black, or vice versa, but switching between playing on white squares and playing on black squares is never going to be better than sticking to one colour then switching to the other.
Taking just the white squares, in some arbitrary row, after the appropriate number of moves, there will be some pattern of squares the pawn could be in. That pattern will be made up of a number of runs of adjacent white squares. Each end that isn't against an edge of the board, will grow by half a square; ends against the edges will shrink by half a square, and your next move should remove one square. Any run that loses half a square to the edge will regain it the following round, so any run you don't play against for two consecutive rounds will grow unless both ends are against the edges. Any run you are playing against the same end of each turn will move sideways until it reaches the edge, then shrink by one every second turn. Playing in the middle of a run does, essentially, nothing - the two children of the square you play will be filled in anyway by the neighbouring squares.
Since your aim is to bring the total number of squares in the pattern down to 0, and the only move that reduces the number of squares in the pattern (and that only sometimes) is playing to the end of a run, you will need to play against the end of a run at least n-2 times (you need to eliminate n/2 squares, which would be n moves, but the first and last moves can be skipped due to edge-effects). Since you need to eliminate all squares in two patterns, you need to do at least 2n-4 moves in total...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print