Author |
Topic: Finding a Princess in a Palace (Read 1048 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Finding a Princess in a Palace
« on: Jan 2nd, 2015, 11:39am » |
 Quote  Modify
|
[I apologize if this puzzle appeared here at a different name/phrasing]
A princess has set a visiting prince the following challenge. She will spend each day in one of the 17 rooms of her palace (arranged in a row), and each night she will move into an adjacent room. The prince may, at noon each day, demand admittance to one room. If, within 30 days, he finds the princess, she will agree to marry him. Otherwise, he must leave disappointed.
Devise a strategy that allows prince marry the princess.
|
| « Last Edit: Jan 3rd, 2015, 11:43am by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding a Princess in a Palace
« Reply #1 on: Jan 2nd, 2015, 12:45pm » |
Quote Modify
|
on Jan 2nd, 2015, 11:39am, Barukh wrote:| Devise a strategy that allows prince and princess becoming a happy couple. |
|
Don't play mindgames and communicate honestly? 
I think there's at least two versions of this puzzle on the forum....
Here's one
Here's a variant
[edit]Another variant[/edit]
Though this setup does suggest that, if they're to be a happy couple, surely they should both want to find each other and cooperate. Maybe there's some way to tweak the puzzle such that cooperative play is interesting (as opposed to here where cooperative play would just mean princess swaps back and fro between, say, the two leftmost rooms)
|
| « Last Edit: Jan 3rd, 2015, 8:16pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Princess in a Palace
« Reply #2 on: Jan 3rd, 2015, 11:42am » |
Quote Modify
|
on Jan 2nd, 2015, 12:45pm, towr wrote:
Thanks, towr, for pointing this out. Then, I will proceed directly to generalization.
BTW, it seems that the first link is broken; the correct one is this
Quote:| Though this setup does suggest that, if they're to be a happy couple, surely they should both want to find each other and cooperate. |
|
No cooperation is assumed; it's simply my careless phrasing - I will fix it.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Princess in a Palace
« Reply #3 on: Jan 3rd, 2015, 11:46am » |
Quote Modify
|
Consider now the following generalization:
This time, the palace has an infinite number of rooms, extending in one direction (that is, there is the first room, but not the last).
The prince is now not bounded by any specific time to find the princess; the only thing is that he is required to do so in a finite time.
Is it possible?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding a Princess in a Palace
« Reply #4 on: Jan 3rd, 2015, 2:33pm » |
Quote Modify
|
Is the rooms the princess can start in limited?
Is the princess doing a random walk, and would a probabilistic answer suffice, or is she running an optimal counter-strategy, and do we need leave chance out of it?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Princess in a Palace
« Reply #5 on: Jan 3rd, 2015, 5:36pm » |
Quote Modify
|
on Jan 3rd, 2015, 2:33pm, towr wrote:| Is the rooms the princess can start in limited? |
|
It is not limited. But, of course, it is finite.
Quote:| Is the princess doing a random walk, and would a probabilistic answer suffice, or is she running an optimal counter-strategy, and do we need leave chance out of it? |
|
Nothing should be assumed about princess's strategy. Prince's strategy, if it exists, should be deterministic.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding a Princess in a Palace
« Reply #6 on: Jan 3rd, 2015, 8:28pm » |
Quote Modify
|
Pick some odd upper limit, say 2N+1
Visit rooms 2N+1 down to 1
If the princess was in an odd numbered room smaller or equal to 2N+1, she'll be caught.
If she was in an even numbered room smaller than 2N+1, she may now be in an odd room anywhere up to 4N+1 now.
So visit 4N+1 down to 1.
If she wasn't caught be now, increase N sufficiently to account for the original upper limit being wrong and time having passed (or just increase it to a ridiculous degree because this is math and we weren't asked for the most efficient algorithm, let's say N:=2N)
[edit]NB, obviously there's not really a need to have two phases each iteration.
Just running through 3k to 1 for incremental k would suffice.
(Not that "3" is special, or exponentiation is required. But it's concise and simple.)[/edit]
|
| « Last Edit: Jan 3rd, 2015, 9:47pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Finding a Princess in a Palace
« Reply #7 on: Jan 4th, 2015, 5:12pm » |
Quote Modify
|
The key to any solution is that it's possible for the prince, in finite time, to find the princess if her starting position is below a known upper bound.
From that, and the fact the princess can only move a finite distance in a finite time, it follows that the prince can still catch her in finite time if he gives her a known head-start - after the headstart, the princess's new "start" position is at most the upper bound of her original start plus the maximum distance she could have moved.
The general strategy is for the prince to pick a potential starting position, and eliminate it and every lower starting position of the same parity, then repeat with some not-yet-eliminated starting position (taking account of the cumulative head-start) - provided the tail of his list of starting positions to eliminate next always has both odd and even positions in, he will find the princess in finite time provided she starts at a finite location.
Obvious follow-up question:
Assuming the prince's strategy is of the following form, what parameters will minimise the asymptotic time to find the princess as a function of her starting position, n?
Generic strategy:
Given a sequence, a(i) of upper-bound starting positions, comprised of two distinct, strictly increasing subsequences, one of odd numbers; the other of even numbers, and numbering the rooms from 0:
t=0;
for (i=0; true; i++)
{
for (j=t+a(i); j>0; j--)
{
check_room(j); //throws exception when princess found
t++;
}
}
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print