Monday puzzle: hide and seek with a twist

I came across this fun puzzle over at MathOverflow:

A princess inhabits a flight of 17 rooms in a row. Each room has a door to the outside, and there is a door between adjacent rooms. The princess spends each day in a room that is adjacent to the room she was in the day before.

One day a prince arrives from far away to woo for the princess. The guardian explains the habits of the princess and also the rules to him: Each day he may knock at an outside door of his choice. If the princess is behind it she will open and in the end marry him. If not, nothing happens, and he gets another chance the next day. Unfortunately his return ticket expires after 30 days.

Does he have enough time to conquer the princess?

Give it a thought before reading my suggested strategy below.

Suggested strategy

I believe this answer works because I have tested it in simulation, but I have not figured out a way to formally prove it (I’m so close and yet so far).

So for fun, I will throw it out to you guys.

I have encoded the answer using rot13 (an example of a Caesar cipher) so the casual reader does not accidentally have the answer spoiled.

Paste this text into rot13.com to read my suggested strategy:

Ba gur svefg qnl, xabpx ba qbbe 2. Gura rnpu qnl gel gur arkg uvturfg qbbe, fb lbh xabpx ba qbbe 3, 4, naq fb ba. Xrrc qbvat guvf hagvy lbh ernpu qbbe 16 ba qnl 15. Ba qnl 16, lbh fubhyq ntnva xabpx ba qbbe 16. Gura xrrc xabpxvat ba gur arkg ybjrfg qbbe, fb lbh xabpx ba qbbef 15, 14, naq fb ba. Vs lbh unir abg sbhaq gur cevaprff lrg, gura ba gur ynfg qnl 30 lbh jvyy or xabpxvat ba qbbe 2 naq jvyy svaq ure gurer.

Does this strategy work? Please share your thoughts and answers in the comments. And bonus points to anyone that uses rot13.com to encode their answers to avoid spoilers :)

I should also mention I’m returning from vacation, so please be patient as I approve comments and check email.



Share this post:

| More

Previous post:

Next post:



  • Anon

    The answer is correct. The proof is as follows:

    First assume that she hides in the even numbered rooms. Thus, knock on #2. If wrong, she can only be in even rooms from #4~16. Thus, next day she will be in odd rooms from #3~17 (you can only get to #1 from #2). So knock on #3 the next day. If wrong, then she is in an odd room from #5~17. So the next day she can be in even rooms from #4~16. So on….. til you knock on door #16.

    If you still fail, ah, the first assumption is wrong. She was in an odd room on the first day! Never fear, repeat the same method.

  • http://www.politicomix.net Roberto

    It works.

    In one scenario, the princess is in a higher numbered room than 2, and moves up the numbers as the prince does the same. Eventually, the princess is at 17 and must return on the next day to 16. By repeating 16, the prince catches her there.

    In the other extreme scenario, the princess is in room 1 on the first day when the prince knocks at #2. She moves up the numbers with him, or simply alternates between room 1 and 2 for 30 days. But because she starts in 1 and the number of days is even (30), she must finish in room 2. Where the prince will be knocking on day 30.

    Unless she commits suicide before then, anguished over having been married off by her guardian (presumably a wicked stepmother) in such a mathematically diabolical manner.

  • Scott

    The problem is see is that the prince and princess can swap rooms.

    Take your first scenario @Roberto, with the princess being one room ahead of the prince and moves up with the prince. You reason that she gets to 17 when the prince is at 16 and the princess MUST move to 16 the next day, and the prince will catch here when he knocks on 16 again.

    However, let’s say that, when the princess is at 16 and the prince is at 15, instead of moving to 17 the princess moves to 15 while the prince moves to 16. Now the princess is behind the prince. She can perform the same swap when the prince moves the other direction. In this sense, it seems that that princess can always avoid the prince.

  • Scott

    My modification:

    Xabpx ba ebbzf 2 guebhtu 16, ohg xabpx ba rnpu ebbz gjvpr orsber zbivat ba. Vs gur cevaprff vf va 1, lbh’yy pngpu ure ba qnl gjb. Vs fur vf nurnq bs gur cevapr, gur cevapr jvyy pngpu ure vs fur gevrf gb fjnc ba uvf frpbaq xabpx sbe gung ebbz. Vs fur fgnlf nurnq bs gur cevapr, fur’yy raq hc va ebbz 17 naq gur cevapr jvyy pngpu ure ba gur frpbaq xabpx ba ebbz 16, ba qnl 30.

    http://www.rot13.com/index.php

    P.S. Presh: I think you should recommend this site to anyone who wishes to comment on answers to your puzzles! Great idea!

  • Scott

    Ah, I didn’t factor in knocking on 16 twice. The princess can only swap if she can be adjacent to the prince, meaning she is odd while the prince is even (and vice versa). By knocking on 16 (or any door) twice, then you change whether or not the princess is in sync with the prince. If even/odd-ness of the doors is the same, then the prince can catch the princess and the princess cannot swap.

    So it looks like that strategy will work. I think mine does too, or at least I can’t see how it would fail. So how would they compare?

  • Scott

    Nevermind. In doing some Monte Carlo simulations, there are situations where my strategy doesn’t work.

    In any event, with Presh’s strategy, the Min and Max are 1 and 30, respectively and obviously. For 1,000,000 runs, I got an average of 15.5 days.

  • Michael

    Gur cevaprff jvyy or va rira-ahzorerq ebbzf ba rira-ahzorerq qnlf, naq bqq-ahzorerq ebbzf ba bqq-ahzorerq qnlf. Ohg gur cevapr qbrf abg xabj jung qnlf ner rira be bqq ahzorerq.

    Vs gur cevapr fgnegf ng gur svefg qbbe ba uvf svefg qnl, naq zbirf hc bar qbbe ng n gvzr bar bs gjb fgngrf jvyy or gehr: gur cevaprff jvyy or va na bqq-ahzorerq ebbz ba gur cevapr’f svefg qnl, be gur cevaprff jvyy or va na rira-ahzorerq ebbz ba gur cevapr’f svefg qnl. Vs gur ynggre vf gehr, gur cevapr jvyy nyjnlf ernpu qbbe 17 jvgubhg zrrgvat gur cevaprff, orpnhfr gurl jvyy or bhg bs cunfr: rvgure ur jvyy xabpx ba na bqq-ahzorerq qbbe jura fur vf oruvaq na rira-ahzorerq qbbe, be ur jvyy xabpx ba na rira-ahzorerq qbbe jura fur oruvaq na bqq-ahzorerq qbbe.

    Ohg vs vg vf gur sbezre, gur cevapr zhfg riraghnyyl zrrg gur cevaprff ol qbbe 16, juvpu pna or cebirq ol vaqhpgvba. Vs gur cevapr gevrf qbbe 1 juvyr gur cevaprff vf va qbbe 3, gura vs fur zbirq gb qbbe 2 gur arkg qnl ur jbhyq zrrg ure, juvyr vs fur zbirq gb 4 gura gur fvghngvba jbhyq or ercrngrq jvgu nyy qbbef ng +1 hagvy riraghnyyl ur zrrgf ure rira vs vg vf orpnhfr ur zbirq sebz 15 gb 16 naq fur zbirq sebz 17 gb 16.

    Vs gur cevaprf qbrf abg zrrg gur cevapr ol qbbe 16, gura ur xabjf ur vf bhg bs cunfr fb gevrf qbbe 16 ntnva gur arkg qnl vafgrnq bs gelvat qbbe 17. Vs gur cevaprff jnf oruvaq qbbe 17 gura ur jvyy zrrg ure vzzrqvngryl. Vs fur jnf va qbbe 15 ur jvyy rvgure zrrg ure be fur jvyy zbir gb oruvaq qbbe 14, ng juvpu cbvag ur ortvaf pbhagvat qbja naq ntnva ol vaqhpgvba ur zhfg zrrg ure ol gur gvzr ur ernpurf qbbe 2, fvapr gurl ner abj va cunfr.

    Fb gur znkvzhz ahzore bs qbbef ur pna gel vf 16+1+15-1=31. Hasbeghangryl guvf zrnaf gung gur cevapr qbrf abg unir rabhtu gvzr hfvat guvf fgengrtl.

    Gur cebcbfrq fgengrtl bs fgnegvat ng qbbe 2 bayl gnxrf 16-1+1+15-1=30 qnlf. Ohg qbrf vg jbex? Lrf. Gur ernfba vf gung gur cevapr jvyy bayl zrrg gur cevaprff qhevat gur pbhag hc fgntr vs gur qbbe fur fgnegf bhg oruvaq unf gur fnzr bqq/riraarff nf gur cevapr’f vavgvny qbbe. Vs gur cevapr fgnegf ng qbbe 2, gura vs gur cevaprff jnf oruvaq qbbe 1 fur vf bqq ohg ur vf rira naq gurl pnaabg zrrg ba gur jnl hc naljnl, fb ur vf orggre bss fxvccvat gung qbbe gb tnva gur rkgen qnl.

  • http://boolesrings.org/krautzberger Peter

    Would you consider tagging this post “PlanetMO” so that it can appear at http://www.mathblogging.org/planetmo?

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the solutions–I see now why the strategy works.

    Peter: Thanks for the suggestion. I have tagged the post.

  • http://anttila.ca/michael Michael

    This was a fun problem. I found it helpful to play around with possible solutions in a two dimensional grid with white pieces representing possible positions for the princess, and black pieces representing which room the prince knocks on each day.

    SPOILER ALERT: This image shows the solution for 11 rooms, which takes at most 18 moves. You can easily see how it can be extended to 17 rooms/30 moves.

    http://i.imgur.com/sPrVM.jpg

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks Michael–that is a very clever way to view the problem geometrically!

  • http://boolesrings.org/krautzberger Peter

    Thanks Presh!

  • http://fairmaidenintrouble.blogspot.com/ Dsouza Arnold

     @bee7719851ce5718a2045ea85f3dd5b7:disqus – In fact in your method it’s possible for the princess to slip past you and remain uncaught. For example:
    Night 1: Prince = 2, Princess = 4
    Night 2: Prince = 2, Princess = 3
    Night 3: Prince = 3, Princess = 2
    Night 4: Prince = 3, Princess = 1
    Night 4: Prince = 4, Princess = 2
    Night 4: Prince = 4, Princess = 1
    Night 4: Prince = 5, Princess = 2
    .
    .
    .

    So you see after slipping past you on nights 2-3, she alternates between doors 1 and 2 and you’ll head off in the other direction until your last night 30 when you’re at 16 and you haven’t caught her.

  • Dsouza Arnold

     Correction: In my sequence above it should be night 5, night 6, night 7 etc. Copy-paste error there.

  • Gb Arivazhagan

    First, I too, thought of the same strategy, But have one doubt, Suppose, if she’s in 5 room, and we start by knocking 2nd door first, then, on 12th day he will be knocking 14th door and the princess will be in the 17th room and the next day, he will be knocking 15th door and the princess is on 16th room, and when he knocks 16th door, she will be on 15th room and hence, she misses out? Is it right!! and also will the below strategy work, Know the odd numbered rooms 1,3,5,7… likewise and after you reach 17 knock back reverse like 15,13,11,… If this is possible, then he can find the princess within 18 days…. Am I right??

Previous post:

Next post:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress