Logic Puzzles

[Swammerdami]

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 2⁹⁶

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% !!!

 

[steve_bank]

Got any more

 

[Swammerdami]

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]

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]

...
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 2⁹⁶

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.

Show

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]

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]

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]

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]

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:

Show

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:

Show

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]

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]

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]

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]

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]

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!]

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.

 

[Gospel]

Granted that the drone and robot aren't locked to the same speed the drone just has to move substantially faster than the robot in the opposite direct. Did I win anything?

 

[steve_bank]

Yea, don't see the big puzzle.

The drone has to go fast enoug to get offshore and takeoff going in ythe opposite rendition from the center of the pond.

On land it becomes a pursuit and evasion problem, a car chase.

In the air it is aerial combat in 3 dimensions. There is a show that reinacts fanous digfights from WWI thru the Gulf wars.

 

[Bomb#20]

Granted that the drone and robot aren't locked to the same speed the drone just has to move substantially faster than the robot in the opposite direct. Did I win anything?

The robot has further to go, and it has to take a curved path while the drone is allowed to go straight if it chooses, so the drone can go slower than the robot and still win. If the drone could go faster there'd be no contest -- it'd be like giving Usain Bolt a head start. The puzzle is, given that the drone can go slower and still win, how much slower?

 

[Gospel]

Ohhh. So the answer must be the lowest speed the drone can travel below the speed of the robot and still get away? Hmm. The drone should take the same path I would take If some dumb bot was chasing me around a car and there were no obstacles but the car. I'd constantly keep the car between me and the dumb bot by matching the movement of the bot while moving away. Meaning the drone should always face away from the robot while moving towards the edge. Yawl mathematicians can do the work. I'll just soak in the glory.

Edit: Infinitely slower I guess.

 

[steve_bank]

I expect the work into autonomous combat robots is working out strategies. Same with autonomous jet fighters. One conceptt is a swarm of autonomous jet fighters. The scifi future is arriving.

There is probably info online about dog fighting straegies. What to do when you are the slower less capable jet being pursued.