wu :: forums
« wu :: forums - Finding a Princess in a Palace »

Welcome, Guest. Please Login or Register.
Jun 20th, 2018, 4:46am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: ThudnBlunder, Icarus, SMQ, Grimbal, Eigenray, william wu, towr)
   Finding a Princess in a Palace
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Finding a Princess in a Palace  (Read 602 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Finding a Princess in a Palace  
« on: Jan 2nd, 2015, 11:39am »
Quote Quote Modify 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: male
Posts: 13611
Re: Finding a Princess in a Palace  
« Reply #1 on: Jan 2nd, 2015, 12:45pm »
Quote Quote Modify 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? Cheesy
 
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: male
Posts: 2276
Re: Finding a Princess in a Palace  
« Reply #2 on: Jan 3rd, 2015, 11:42am »
Quote Quote Modify Modify

on Jan 2nd, 2015, 12:45pm, towr wrote:
I think there's at least two versions of this puzzle on the forum....
Here's one
Here's a variant

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: male
Posts: 2276
Re: Finding a Princess in a Palace  
« Reply #3 on: Jan 3rd, 2015, 11:46am »
Quote Quote Modify 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: male
Posts: 13611
Re: Finding a Princess in a Palace  
« Reply #4 on: Jan 3rd, 2015, 2:33pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Finding a Princess in a Palace  
« Reply #5 on: Jan 3rd, 2015, 5:36pm »
Quote Quote Modify 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: male
Posts: 13611
Re: Finding a Princess in a Palace  
« Reply #6 on: Jan 3rd, 2015, 8:28pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2814
Re: Finding a Princess in a Palace  
« Reply #7 on: Jan 4th, 2015, 5:12pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board