Author 
Topic: Finding a Princess in a Palace (Read 1013 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Finding a Princess in a Palace
« on: Jan 2^{nd}, 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 3^{rd}, 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 2^{nd}, 2015, 12:45pm » 
Quote Modify

on Jan 2^{nd}, 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 3^{rd}, 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 3^{rd}, 2015, 11:42am » 
Quote Modify

on Jan 2^{nd}, 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 3^{rd}, 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 3^{rd}, 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 counterstrategy, 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 3^{rd}, 2015, 5:36pm » 
Quote Modify

on Jan 3^{rd}, 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 counterstrategy, 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 3^{rd}, 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:=2^{N}) [edit]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.)[/edit]

« Last Edit: Jan 3^{rd}, 2015, 9:47pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2872


Re: Finding a Princess in a Palace
« Reply #7 on: Jan 4^{th}, 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 headstart  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 notyeteliminated starting position (taking account of the cumulative headstart)  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 followup 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 upperbound 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 



