Comments on: HJ. Strange Suitor

By: strauss

strauss — Fri, 17 Feb 2012 16:14:49 +0000

Very cool! (Because of the taping schedule, it will be another week before we mention this on the podcast, but you bet we will!)

By: Ben Anderman

Ben Anderman — Thu, 16 Feb 2012 17:38:22 +0000

My uncle told me about the puzzle in this, and while trying to solve it, I built a little web page to (in)validate my answers... Eventually I gave up and solved it with a javascript function. But I cleaned up the page a bunch, and posted it on my website with an explanation of the puzzle, so other people can try it: http://www.happyspork.com/princess_challenge

By: Blaine

Blaine — Sun, 05 Feb 2012 21:32:19 +0000

Byon, you are right. I thought I had prevented her from getting by with the double-knock, but I was getting confused by where she is vs. where she is going to be. She may very well be in the next room (e.g. #3), but she is just about to pass by and go to #2 as I go and knock on #3. I had thought of the other solution… [spoiler]knocking up on 2, 3, … n-1, then down on n-1, …3, 2, but it seemed harder to explain why it worked and I thought my double-knocking was clearer. Clearer isn’t better if it doesn’t work though. :) [/spoiler]Indeed yours *does* work and my “solution” does not. :(

By: Daniel

Daniel — Fri, 03 Feb 2012 04:56:20 +0000

A bit further explanation of why Byon’s solution works:
[spoiler]
Since the princess has to move to an adjacent room at each turn, she alternates between even and odd numbered rooms each day. If on your upwards pass, she manages to slip through, since you’ve also been alternating even/odd, you know the princess must be in a room with an opposite even/odd parity to the one you’ve picked (she was in an adjacent room on at least two days), so repeating the knock on door n-1 not only finds the princess if she had moved into room n on the previous step, but changes your parity to match that of the princess if she had slipped through and makes it impossible for her to slip through on the reverse pass (since she can never move to an adjacent room to the one you’ve picked).
[/spoiler]

By: strauss

strauss — Fri, 03 Feb 2012 04:01:03 +0000

Yep, but it’s great to wrestle things down! A couple of general comments: If you have something to hide, please use the spoiler tag (Square bracket)spoiler(square bracket) WHATEVER IT IS (square bracket, forward slash)spoiler(square bracket). Also, don’t worry if your comment doesn’t appear for several days–we tend to hold solutions, and attempted solutions, back for a few days. But we sure do enjoy the conversation!

By: Byon

Byon — Fri, 03 Feb 2012 03:53:00 +0000

Blaine: I think you may be wrong. Consider 4 rooms. Your algorithm is knock on door 2 twice, 3 twice, and you think you have her. But what if she was first in room 4, then 3, then 2, then 1. You missed her!

SPOILER:[spoiler] Here is my solution. It takes 2n-4 knocks, where n is the number of doors. So with 17 doors, worst case is 30 knocks. Knock door 2, then 3, 4, etc up to n-1. Then knock n-1 again, then n-2, and continue down to 2, and you should have her.

Here’s the analysis for n=4 doors. Knock door 2. Now we know she is in room 1, 3, or 4. Then knock door 3. She must be in room 2 or 4. Door 3 again, and she must be in room 1, so knock 2 and get her![/spoiler]

Fun puzzle. Looking forward to more.

By: strauss

strauss — Thu, 02 Feb 2012 22:29:06 +0000

That is very cool! This hasn’t happened in nearly 800 years!

By: Tom Semple

Tom Semple — Thu, 02 Feb 2012 22:16:26 +0000

I would note that 2012 is a Dodecahedral Year (20 vertices, 12 faces), or alternatively an Icosahedral year (20 faces, 12 vertices).

By: Blaine

Blaine — Fri, 27 Jan 2012 22:01:12 +0000

Is it okay to discuss the puzzle presented in the podcast here? If anyone wants to continue thinking about the puzzle, please stop reading. SPOILERS to follow.[spoiler] Just like what was suggested, I tried some mental experiments with 3 rooms, 4 rooms and 5 rooms. I think I have a solution that works unless I’ve overlooked something. Part of what makes me think it is correct is that 30 tries is twice 15 middle rooms. Again, if you want to figure this out on your own, consider that hint and stop reading. Okay, enough wasting time, here’s what I think. We (as the suitor) should knock on door #2, twice. If the lady of our desires started in room #2, we’d catch her on the first knock. If she was in room #1, we’d catch her on the second knock. And if we don’t find her, she is now in room #3 or higher. Now repeat the process by knocking on room #3, twice. Again, if she was in room #3 we would catch her (preventing her from slipping by us into room #2). Similarly, the second knock would catch her if she tried to slip by us going from #4 to #3 on the next move). Now we’ve isolated her to room #4 or higher. The process repeats, knocking twice on #4, #5, #6, etc. It seems apparent that when we knock on room #16, we’ll either find her immediately, or if she was in #17, she’ll have no choice but to be caught on our second knock on room #16. In summary, start on door #2 twice, then #3 twice, etc. In the worse case you’ll have to knock twice on door #16, but you’ll be guaranteed of catching her without exceeding 30 knocks. [/spoiler] No doubt she’ll reward us for our ingenuity and logic… or she’ll get a restraining order for stalking. Oh well.