HJ. Strange Suitor
We’ll have some pursuit puzzles over the next couple of weeks; this segment’s puzzle has a simple and elegant solution, but it might take a while to work it out!
In the meanwhile, here’s a little discussion about the glass of water problem.
Each time we add or subtract 50%, we are multiplying the quantity of water by 1/2 or 3/2. If we began with 1 glass’ worth, at each stage, we’ll have a quantity of the form 3m/2n with m,n>0 Of course that can never equal 1, but we can get very close if m/n is very close to log3 2 = 0.63092975357145743710…
Unfortunately, there’s a serious problem: m/n has to hit the mark pretty closely in order for 3m/2n to get really close to 1, and to get within “one molecule”s worth, m and n have to be huge indeed.
How huge? Well, let’s see: an 8 oz. glass of water contains about 1025 molecules; to get within 1/1025 of 1, we need m=31150961018190238869556, n=49373105075258054570781 !! One immediate problem is that if you make a switch about 100,000 times a second, this takes about as long as the universe is old!
But there’s a more serious issue.
In a glass of water, there’s a real, specific number of molecules. Each time we add or subtract 50%, we are knocking out a factor of 2 from this number. Once we’re out of factors of 2, we can’t truly play the game any more, because we’d have to be taking fractions of water molecules. (For example, if we begin with, say, 100 molecules, after just two steps we’d be out of 2’s since 100=2*2*some other stuff.
But even though there are a huge number of water molecules in a glass of water, even if we arrange it so that there are as many 2’s as possible in that number, there just can’t be that many: 283 is about as good as we can do (of course, we won’t have precisely 8 ounces any more, but still.)
If we are only allowed 83 or so steps, the best we can do is only m= 53, n = 84 (Let’s just make the glass twice as big to accommodate that), and, as Byon noted, 3^53/2^84 is about 1.0021– not that close, really!
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Blaine said,
January 27, 2012 at 5:01 pm
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.
Tom Semple said,
February 2, 2012 at 5:16 pm
I would note that 2012 is a Dodecahedral Year (20 vertices, 12 faces), or alternatively an Icosahedral year (20 faces, 12 vertices).
strauss said,
February 2, 2012 at 5:29 pm
That is very cool! This hasn’t happened in nearly 800 years!
Byon said,
February 2, 2012 at 10:53 pm
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.
strauss said,
February 2, 2012 at 11:01 pm
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!
Daniel said,
February 2, 2012 at 11:56 pm
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]
Blaine said,
February 5, 2012 at 4:32 pm
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. :(
Ben Anderman said,
February 16, 2012 at 12:38 pm
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
strauss said,
February 17, 2012 at 11:14 am
Very cool! (Because of the taping schedule, it will be another week before we mention this on the podcast, but you bet we will!)