wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Finding a Princess in a Palace
        
(Message started by: Barukh on Jan 2^nd, 2015, 11:39am)

Title: Finding a Princess in a Palace
Post by Barukh on Jan 2^nd, 2015, 11:39am

[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.

Title: Re: Finding a Princess in a Palace
Post by towr on Jan 2^nd, 2015, 12:45pm

on 01/02/15 at 11:39:51, Barukh wrote:

Devise a strategy that allows prince and princess becoming a happy couple.

Don't play mindgames and communicate honestly? :D

I think there's at least two versions of this puzzle on the forum....
Here's one (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1131519823)
Here's a variant (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1132524701)
[edit]Another variant (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1377651469)[/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)

Title: Re: Finding a Princess in a Palace
Post by Barukh on Jan 3^rd, 2015, 11:42am

on 01/02/15 at 12:45:13, towr wrote:

I think there's at least two versions of this puzzle on the forum....
Here's one (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=11315198230)
Here's a variant (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1132524701)

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 (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1131519823)

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.

Title: Re: Finding a Princess in a Palace
Post by Barukh on Jan 3^rd, 2015, 11:46am

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?

Title: Re: Finding a Princess in a Palace
Post by towr on Jan 3^rd, 2015, 2:33pm

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?

Title: Re: Finding a Princess in a Palace
Post by Barukh on Jan 3^rd, 2015, 5:36pm

on 01/03/15 at 14:33:22, 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.

Title: Re: Finding a Princess in a Palace
Post by towr on Jan 3^rd, 2015, 8:28pm

[hide]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:=2^N)[/hide]

[edit][hide]NB, obviously there's not really a need to have two phases each iteration.
Just running through 3^k to 1 for incremental k would suffice.
(Not that "3" is special, or exponentiation is required. But it's concise and simple.)[/hide][/edit]

Title: Re: Finding a Princess in a Palace
Post by rmsgrey on Jan 4^th, 2015, 5:12pm

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++;
}
}