# Logic Puzzles

#### Swammerdami

Staff member
Although the details are quite different, the 100 Prisoners Puzzle shares a property with a puzzle I posted 2½months ago. (Click to review the puzzle; here I'm just interested in the "paradoxical" property.)

. . .
This is a WONDERFUL puzzle which should appeal to fans of combinatorics and information theory. Even very smart people usually give up and think 50% is the best that can be achieved.
. . . Three can get to 75% chance of marriage/silver easily:

In that puzzle, 50% chance of success is the best any (non-abstaining) guesser can hope for. And. like the 100 Prisoner's Puzzle, ALL guessers must succeed to win. Yet a 75% chance is attainable, as shown by Bomb#20!

As an approximation I'd say the probability is close to zero of the prisoners surviving.

The first guesser has exactly a 50% chance no matter how he plays. Perhaps they agree in advance that he will pick Boxes #1 - #50. If he succeeds, the 2nd prisoner picks #51 - #100 and wins 50/99 of the time. We're down to 25.25% and still have 98 prisoners to go.

With this brutish approach, the chance that 100 prisoners succeed is 0.00000000000000000000000000099%, worse than 1 in 296

Is there some clever idea that will let the prisoners do better than this pathetic chance of 1 in 100 trillion quadrillion?
Yes, they can actually achieve a bit better than 31% !!!

Got any more

#### Swammerdami

Staff member
Among the most famous math puzzles are two for which sub-optimal solutions are often presented.
(A), phrased much differently, shows up if you search for "Microsoft Interview Puzzles" IIRC.
(B) is almost always presented as a problem for 12 pennies. But 13 is doable, or even 14 as implied below.

(A) A drone is floating at the center of a large circular lake. It must get to land before it can take off, but can operate as a powered boat to traverse the lake and get to land. Roaming on land along the perimeter is a robot, which will kill the drone if it gets within a foot or so. (Assume fuel exhaustion etc. are not issues.)

Calling the robot's speed c, how fast must the drone be on water to escape the robot and fly away?

(B) You have a supply of good pennies, but also a bag of FOURTEEN pennies one of which is counterfeit.
You are given a balance scale which reports Heavy, Balanced or Light. You can weigh one penny against one; 2 against 2; 3 3; 4 4; and so on. Thirteen of the 14 coins are genuine and balance against each other. The counterfeit coin is either lighter than a genuine, or heavier; but you don't know (or care) which.

You are allowed three weighings. Can you always identify the counterfeit?

#### steve_bank

##### Diabetic retinopathy and poor eyesight. Typos ...
I posted h a problem on another thread in a different coonext. I think yiouhave to define a position of the ribot on the crndefce at a given time.

It involves calculating Vdrone*time on water versus Vrobot*time traveling a circular path.

A flaw in my problem as I presented it caught by two others. In this problem there are an infinite number of solutions. Depending on how fast the robot is going, how fast the drone is going, the direction of the drone, and when the drone starts relative to where the robot is on the circumference.

I'll work on the second problem.

#### Bomb#20

##### Contributor
...
The first guesser has exactly a 50% chance no matter how he plays. Perhaps they agree in advance that he will pick Boxes #1 - #50. If he succeeds, the 2nd prisoner picks #51 - #100 and wins 50/99 of the time. We're down to 25.25% and still have 98 prisoners to go.

With this brutish approach, the chance that 100 prisoners succeed is 0.00000000000000000000000000099%, worse than 1 in 296

Is there some clever idea that will let the prisoners do better than this pathetic chance of 1 in 100 trillion quadrillion?
Yes, they can actually achieve a bit better than 31% !!!
There's a simple strategy that obviously gets a ton better odds than the brutish approach. I don't know how to calculate the probability other than Monte Carlo simulation, but I'm guessing it matches your greyed-out percentage.

Everybody picks his own number's box. If it has his number, great! Otherwise, read the number in the box, open the box with that number, and repeat. Everybody lives provided the random permutation doesn't have a subcycle longer than 50, which will happen pretty often.

#### Swammerdami

Staff member
Mr. Bomb is correct of course.

Tell us: Had you heard of the problem before or did you solve it just now, just like that?

If the latter I remain VERY impressed.

#### Jarhyn

##### Wizard
The problem should state that the prisoner opens the boxes one at a time and gets to see the number on each card the reveals before choosing the next box.
Drat! I should have stated the problem more carefully.

Interestingly, the Wikipedia article says that each prisoner has a 50% chance of success if they choose 50 drawers at random, but this does not account for the fact that they will not choose the same drawer/box twice. The odds of finding their number after 50 random guesses should be (1/100 + 1/99 + ... + 1/51), which is about 69 (nice) percent.
I beg to differ. Your 2nd pick has a 1/99 chance of success only if the first pick failed. So that 1/99 needs to be multiplied by the chance of 1st-pick failure, i.e. 99/100. 1/99*99/100 = 1/100. And so on. 50% IS the chance of success opening 50 bins at random. AND the chance of success for 1st prisoner to pick no matter how he plays.
A question here: how fast does reset happen?

#### Bomb#20

##### Contributor
Mr. Bomb is correct of course.

Tell us: Had you heard of the problem before or did you solve it just now, just like that?

If the latter I remain VERY impressed.
I'm actually not sure. I'm old, my memory is going, I've seen a lot of permutation problems that all run together in my head, and the decomposition I used is a standard approach for those. So it's entirely possible I saw it before at some point.

#### Bomb#20

##### Contributor
Among the most famous math puzzles are two for which sub-optimal solutions are often presented.
(A), phrased much differently, shows up if you search for "Microsoft Interview Puzzles" IIRC.
(B) is almost always presented as a problem for 12 pennies. But 13 is doable, or even 14 as implied below.

(A) A drone is floating at the center of a large circular lake. It must get to land before it can take off, but can operate as a powered boat to traverse the lake and get to land. Roaming on land along the perimeter is a robot, which will kill the drone if it gets within a foot or so. (Assume fuel exhaustion etc. are not issues.)

Calling the robot's speed c, how fast must the drone be on water to escape the robot and fly away?
Are we supposed to assume the robot and the drone can always see each other and that the robot will always move toward the point on the periphery closest to the drone?

(B) You have a supply of good pennies, but also a bag of FOURTEEN pennies one of which is counterfeit.
You are given a balance scale which reports Heavy, Balanced or Light. You can weigh one penny against one; 2 against 2; 3 3; 4 4; and so on. Thirteen of the 14 coins are genuine and balance against each other. The counterfeit coin is either lighter than a genuine, or heavier; but you don't know (or care) which.

You are allowed three weighings. Can you always identify the counterfeit?
Yes. I didn't find any simple rule for what to do, just an ugly case-by-case procedure.
Hint:

There are 28 possibilities but you can distinguish only 27 possibilities using three 3-outcome weighings. So there are bound to be two possibilities you can't distinguish. The trick is therefore to make sure that the two possibilities you can't distinguish are the same coin, so you just don't know if it's too heavy or too light.

Solution:

Code:
Call the suspect pennies ABCDEFGHIJKLMN, and you supply a known good penny X.
If ABCDE = FGHIX, the fake is in JKLMN
If JK = LX
If M = X, N is heavy or light, but you can't tell which
else if M > X, M is heavy
else M is light
else if JK > LX
If J = K, L is light
else if J > K, J is heavy
else K is heavy
else if JK < LX
similarly
else if ABCDE > FGHIX, ABCDE are heavy or FGHI are light
if ABF = CDG, it's in EHI
if H = I, E is heavy
else if H > I, I is light
else H is light
else if ABF > CDG, it's in ABG
if A = B, G is light
else if A > B, A is heavy
else B is heavy
else if ABF < CDG, it's in CDF
similarly
else if ABCDE < FGHIX, ABCDE are light or FGHI are heavy
similarly

#### Swammerdami

Staff member
Among the most famous math puzzles are two for which sub-optimal solutions are often presented.
(A), phrased much differently, shows up if you search for "Microsoft Interview Puzzles" IIRC.
(B) is almost always presented as a problem for 12 pennies. But 13 is doable, or even 14 as implied below.

(A) A drone is floating at the center of a large circular lake. It must get to land before it can take off, but can operate as a powered boat to traverse the lake and get to land. Roaming on land along the perimeter is a robot, which will kill the drone if it gets within a foot or so. (Assume fuel exhaustion etc. are not issues.)

Calling the robot's speed c, how fast must the drone be on water to escape the robot and fly away?
Are we supposed to assume the robot and the drone can always see each other
Yes.

and that the robot will always move toward the point on the periphery closest to the drone?
That surely appears to be robot's best strategy.
(B) You have a supply of good pennies, but also a bag of FOURTEEN pennies one of which is counterfeit.
You are given a balance scale which reports Heavy, Balanced or Light. You can weigh one penny against one; 2 against 2; 3 3; 4 4; and so on. Thirteen of the 14 coins are genuine and balance against each other. The counterfeit coin is either lighter than a genuine, or heavier; but you don't know (or care) which.

You are allowed three weighings. Can you always identify the counterfeit?
Yes. I didn't find any simple rule for what to do, just an ugly case-by-case procedure.

"Ugly"?
Why "Ugly"? Why not Elegant? With reasoning as in your hint you can quickly find the ONLY possible solution; an elegant perfect fit, just like when your girlfriend with her 37-26-39 figure squeezes into her bathing suit.

Congratulations, Bomb#20 !

#### Bomb#20

##### Contributor
Among the most famous math puzzles are two for which sub-optimal solutions are often presented.
...
(A) A drone is floating at the center of a large circular lake. It must get to land before it can take off, but can operate as a powered boat to traverse the lake and get to land. Roaming on land along the perimeter is a robot, which will kill the drone if it gets within a foot or so. (Assume fuel exhaustion etc. are not issues.)

Calling the robot's speed c, how fast must the drone be on water to escape the robot and fly away?
Are we supposed to assume the robot and the drone can always see each other
Yes.

and that the robot will always move toward the point on the periphery closest to the drone?
That surely appears to be robot's best strategy.
The obvious suboptimal solution is C/pi, if the drone just heads directly away from the robot's starting location. A better solution is for the drone to spiral outward to radius / (pi + 1), so although the robot tries to get ahead and cut off escape, the drone stays directly opposite it. Then the drone can dash for the side at C/(pi +1). That's still suboptimal, though. If it aims for a point offset away from the drone, it can go a little slower. But where to aim for and how much slower looks like a painful numerical nonlinear optimization problem. If there's an analytical solution I'm not seeing it.

#### Swammerdami

Staff member
The drone and robot problem is usually presented as duck and fox. I changed to avoid debate about wherther ducks can take off from water!

Are we supposed to assume the robot and the drone can always see each other
Yes.

and that the robot will always move toward the point on the periphery closest to the drone?
That surely appears to be robot's best strategy.
The obvious suboptimal solution is C/pi, if the drone just heads directly away from the robot's starting location. A better solution is for the drone to spiral outward to radius / (pi + 1), so although the robot tries to get ahead and cut off escape, the drone stays directly opposite it. Then the drone can dash for the side at C/(pi +1).

The side directly opposite robot? That solution MIGHT get you a job at Microsoft!

That's still suboptimal, though.

Yes. I AM surprised Microsoft doesn't seem to know this.
. . . Or more likely Microsoft IS clever: they are happy that the suboptimal solution is widely available on the 'Net and want to check if interviewee KNOWS it's sub-optimal.
If it aims for a point offset away from the drone, it can go a little slower. But where to aim for and how much slower looks like a painful numerical nonlinear optimization problem. If there's an analytical solution I'm not seeing it.

There IS an "obvious" and simple route for the drone to take. A bout of common sense and/or trigonometry demonstrates it to be optimal among straight-line paths.

But is that "obvious" route optimal? Might there be some spiraling strategy that improves on it??

Once upon a time I occasionally had brief flashes of mathematical intuition. During such a flash I once thought I had an elegant proof that the "obvious" route was optimal. But my brain is in decline and I won't attempt to reproduce or vouch for the argument.

ETA: I have posed this problem on a Board with several Members with good mathematical skill. I have NEVER seen anyone come up with the so-called "obvious" solution, let alone a proof. Maybe the blatantly sub-optimal solution IS good enough for the Microsoft job after all.

#### Bomb#20

##### Contributor
If it aims for a point offset away from the drone, it can go a little slower. But where to aim for and how much slower looks like a painful numerical nonlinear optimization problem. If there's an analytical solution I'm not seeing it.

There IS an "obvious" and simple route for the drone to take. A bout of common sense and/or trigonometry demonstrates it to be optimal among straight-line paths.
If you mean a path tangent to a circle of the radius where the drone switches from a spiral to a straight line, yes, that's obvious and simple, but I haven't got enough common sense and/or trigonometry to demonstrate it to be optimal among straight-line paths. The argument that proves the previous answer suboptimal relies on infinitessimals and breaks down once you get away from the previous answer's target point. (Besides which, I don't even see how to calculate the radius of the transition point and thus the drone's speed without numerical nonlinear optimization.)

But is that "obvious" route optimal? Might there be some spiraling strategy that improves on it??

Once upon a time I occasionally had brief flashes of mathematical intuition. During such a flash I once thought I had an elegant proof that the "obvious" route was optimal. But my brain is in decline and I won't attempt to reproduce or vouch for the argument.
According to my also-declining brain's intuition, a curved path can't beat the best straight path because as long as the drone is further from the center than the strategy transition radius, the robot is necessarily gaining on the drone, so wherever the drone ends up on the perimeter, it could have gotten there faster if it had gone straight.

ETA: I have posed this problem on a Board with several Members with good mathematical skill. I have NEVER seen anyone come up with the so-called "obvious" solution, let alone a proof. Maybe the blatantly sub-optimal solution IS good enough for the Microsoft job after all.
Really? The actually "obvious" solution is the one in my last post: give up and throw the problem to a computer. If the solution you have in mind really is optimal, my solution will find it.

#### Swammerdami

Staff member
There IS an "obvious" and simple route for the drone to take. A bout of common sense and/or trigonometry demonstrates it to be optimal among straight-line paths.
If you mean a path tangent to a circle of the radius where the drone switches from a spiral to a straight line, yes, that's obvious and simple, ...
According to my also-declining brain's intuition, a curved path can't beat the best straight path because as long as the drone is further from the center than the strategy transition radius, the robot is necessarily gaining on the drone, so wherever the drone ends up on the perimeter, it could have gotten there faster if it had gone straight.
Yes, make a 90-degree turn (left or right depending as robot moves to your right or left) when you are at the critical circle. The problem is if you turn MORE than 90 degrees, you will re-enter the critical circle; robot can reverse course; you're back to the initial state.

Can you set a spiral course, never re-entering the critical circle, keeping the robot almost 180-degrees away and doing slightly better than the 90-degree straight line?

I don't think so; and I think your argument is essentially correct. I just don't remember how to rule out the possibility of a spiraling course.

#### Tigers!

##### Veteran Member
A light aircraft crashed into a cemetery outside Dublin. So far, the Garda have recovered four hundred bodies, and expect the death toll to rise further...
An oldie but still good.