For Express, however, there are too many distinct ways of arranging these fences. I tested just three symmetrical configurations with three fences meeting at a central point. I also tested another simple strategy with two fences. Without going into too much detail, the best strategy I found used a hair under 1.633 miles of fencing. Can anyone beat this? Testing all possible fencing configurations without the assumption of symmetry would require way too much calculus for my brain to handle at the moment.
Also, for practical considerations, the difference between the best and worst strategies I tested (disregarding two parallel, vertical lines, 2 miles of fencing) was about 573 feet of fencing. The difference between the two best strategies I tested was just 9 feet. Even if I'm incorrect, assuming that the best strategy is not much better than what I've already found, I doubt it would be worth the price of the additional fence to go through the trouble of calculating it.
I don't know the strategy you have yet, but the fences don't have to be straight lines from the common joint to the edges, right? In that case, I think the optimal curves to the edges would be circular arcs (if not a perpendicular line to the edge). This problem reminds me of some variants of the Isoperimetric Problem.
I might try to work it out later.
I hadn't considered paths that aren't a straight line. I drew some inspiration from bubbles, which tend to maximize volume for a given surface area and are often straight lines. Of course, in retrospect, there are plenty of situations where a bubble follows a curved path...
Let me work out a variant on my best path that uses arcs...
Nope, it gives a total length of 2.05 miles, even worse than the naive "three rectangles" partition. That was just a quick check of one possible partition, not an exhaustive search of all partitions with curved fences.
For Classic, I obtained an optimal strategy that was better than 1 in 10.
My first guess resulted in something "better than 1 in 10". As the riddler did not ask for optimality, that'll do.
This could be improved to 1 in 3 if you decide that the rules don't explicitely prevent you from swapping the contents of the two boxes you opened ;)
Bobo the King wrote:
Without going into too much detail, the best strategy I found used a hair under 1.633 miles of fencing.
There is a simple strategy with 1.666 miles of fencing, so I suspected that 1.633 is not optimal. I tried one variation, wrote a function determining fence length based on a certain angle, then used wolframalpha to determine the global minimum, arriving at a pretty odd number: ~1.533 miles. Not sure if that's optimal, but it's enough to send you back to the drawing board :p
/edit: or maybe yours was a typo and you got 1.533 too?
Bobo the King wrote:
I drew some inspiration from bubbles, which tend to maximize volume for a given surface area and are often straight lines. Of course, in retrospect, there are plenty of situations where a bubble follows a curved path...
AFAIK bubbles are only round on the outside. Boundaries between touching bubbles always end up straight (at least those I've observed).
My solution has just straight lines, and I don't believe that curving any of them would yield further improvements.
For Classic, I obtained an optimal strategy that was better than 1 in 10.
My first guess resulted in something "better than 1 in 10". As the riddler did not ask for optimality, that'll do.
This could be improved to 1 in 3 if you decide that the rules don't explicitely prevent you from swapping the contents of the two boxes you opened ;)
Bobo the King wrote:
Without going into too much detail, the best strategy I found used a hair under 1.633 miles of fencing.
There is a simple strategy with 1.666 miles of fencing, so I suspected that 1.633 is not optimal. I tried one variation, wrote a function determining fence length based on a certain angle, then used wolframalpha to determine the global minimum, arriving at a pretty odd number: ~1.533 miles. Not sure if that's optimal, but it's enough to send you back to the drawing board :p
/edit: or maybe yours was a typo and you got 1.533 too?
Bobo the King wrote:
I drew some inspiration from bubbles, which tend to maximize volume for a given surface area and are often straight lines. Of course, in retrospect, there are plenty of situations where a bubble follows a curved path...
AFAIK bubbles are only round on the outside. Boundaries between touching bubbles always end up straight (at least those I've observed).
My solution has just straight lines, and I don't believe that curving any of them would yield further improvements.
My strategy that led to 1.633 miles of fencing was just two parallel diagonal fences that make 45 degree angles with the sides of the square. This beat three other strategies with three fences meeting at a central node.
My strategy that led to 1.633 miles of fencing was just two parallel diagonal fences that make 45 degree angles with the sides of the square. This beat three other strategies with three fences meeting at a central node.
Two parallel diagonal fences that make 45 degree angles with the sides of the square? That seems to give 4/sqrt(3), or about 2.31, not 1.633.
Did you calculate the leg lengths of the 45-45-90 triangles bound by the diagonals as sqrt(1/3) instead of sqrt(2/3)? If I did my math right, it should be sqrt(2/3).
My strategy that led to 1.633 miles of fencing was just two parallel diagonal fences that make 45 degree angles with the sides of the square. This beat three other strategies with three fences meeting at a central node.
Two parallel diagonal fences that make 45 degree angles with the sides of the square? That seems to give 4/sqrt(3), or about 2.31, not 1.633.
Did you calculate the leg lengths of the 45-45-90 triangles bound by the diagonals as sqrt(1/3) instead of sqrt(2/3)? If I did my math right, it should be sqrt(2/3).
Derp. Forgot the factor of sqrt(2).
Okay, my shortest path is 1.635 miles and involves three fences meeting at a central point. I'm annoyed with myself that I once again screwed up a math challenge over a simple mistake, but since Tub got 1.533 miles, it sounds like I wouldn't have gotten it anyway.
Okay, my shortest path is 1.635 miles and involves three fences meeting at a central point. I'm annoyed with myself that I once again screwed up a math challenge over a simple mistake, but since Tub got 1.533 miles, it sounds like I wouldn't have gotten it anyway.
I've found two different strategies that result in 1.7524, and have been unable to find anything better than that, so don't be too hard on yourself.
You have a fixed area (3x 1/3), and for f miles of fencing, the sum of all three circumferences is 4+2*f.
Minimizing the sum of circumferences means that you want all three areas to be roughly circle-like. Cutting two circle-like areas from the corner seems useful, until you realize that the remaining third area is way too inefficient.
Same with curves. They seem efficient because they optimize one side of the fence, but they'll turn the other side of the fence into a concave mess.
Intuitively, the only strategies where all three areas remain roughly circle-like and convex are those with a point somewhere in the middle and three straight fences to the property border. My solution with ~1.533 is one of those, but I cannot prove whether it's optimal.
Intuitively, the only strategies where all three areas remain roughly circle-like and convex are those with a point somewhere in the middle and three straight fences to the property border. My solution with ~1.533 is one of those, but I cannot prove whether it's optimal.
So are mine, I just haven't been able to get them any lower.
So what I did was broadly similar - I'm certainly assuming the optimal solution is a point somewhere in the middle with three straight lines coming out of it.
I also assumed that the correct solution has reflectional symmetry across one of the square's midlines. Using these constraints I was able to get the problem down to single degree of freedom which I could then optimise with calculus - but I must have got the calculus wrong as I could only get the number down to 1.641 (to three decimal places).
Optimality proofs will be through some calculus-of-variations methods similar to those that solved the isoperimetric problem - but I left university a while ago and can't really remember anything about the calculus of variations.
*sigh* if multiple people smarter than me fail to match my solution, then obviously my solution is wrong.
After I finally found my mistake, my solution actually matches bobo's ~1.635. thatguy's post reads like he should also arrive at the same value.
*sigh* if multiple people smarter than me fail to match my solution, then obviously my solution is wrong.
After I finally found my mistake, my solution actually matches bobo's ~1.635. thatguy's post reads like he should also arrive at the same value.
Well damn. That means I could have submitted my solution this week and been eligible but instead I went with a solution that omitted a factor of sqrt(2).
For anyone reading who's curious, my solution has one fence leading straight up from the bottom side and two other fences from the adjacent sides. The solution is symmetric about a vertical symmetry axis. The two other solutions I tried had one fence in the corner and two from the opposite sides and one fence from the bottom and two from the top.
Has anyone come up with anything else for the game show puzzle where 100 people try to find their names in 100 boxes? My strategy scaled up the 4 person version and had 50 people choose the first 50 boxes and the 50 remaining people choose the latter 50 boxes. This strikes me as suboptimal, but I can't quite articulate why. It seems like it would be better to have some overlap. Before solving the 4 person version, I suspected that the optimal strategy would be to have each person share one box with exactly one other player. That is, I'd have player 1 open boxes A and B, player 2 open B and C, player 3 open C and D, and player 4 open D and A. That turns out to give a lower probability than having two players pick A and B and two pick C and D, but I'm skeptical that it scales up. Can anyone (dis)prove this?
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I also found 1.635 for the optimizaition problem, but I'm not convinced it's impossible to improve it. Would it be possible to proof such a solution is optimal, without heavy computational power reliance?
Ah, I've spotted the mistake I made!
I set up the problem in terms of two variables, a and b. But when it came to the calculus, I failed to remember that a and b are not independent of each other, so I have to express a in terms of b before proceeding. Instead I just ignored a when differentiating with respect to b.
When I do that, I do indeed get to 1.635. Are we all agreed on this probably being the best number?
I got 1.6266 by replacing the slant lines (the straight fences that don't meet the edge of the square at a right angle) with circular arcs that divide the areas equivalently.
Any straight fence that does not meet the edge of the square at a right angle can be replaced with a circular arc to lower its length.
Bobo the King wrote:
Has anyone come up with anything else for the game show puzzle where 100 people try to find their names in 100 boxes?
I came across another person's approach to this problem: Each player can progressively open boxes depending on which boxes they opened previously. They are not limited to choosing 50 boxes and opening them all at the same time.
This, in my opinion, is a much better interpretation of the problem.
I got 1.6266 by replacing the slant lines (the straight fences that don't meet the edge of the square at a right angle) with circular arcs that divide the areas equivalently.
Any straight fence that does not meet the edge of the square at a right angle can be replaced with a circular arc to lower its length.
Bobo the King wrote:
Has anyone come up with anything else for the game show puzzle where 100 people try to find their names in 100 boxes?
I came across another person's approach to this problem: Each player can progressively open boxes depending on which boxes they opened previously. They are not limited to choosing 50 boxes and opening them all at the same time.
This, in my opinion, is a much better interpretation of the problem.
How would a player's strategy change if the boxes they open depend on previously opened boxes? If they don't find their own name in a box, does it offer any information about where their name is?
Also, I just noticed that the official answer for last week's coin flipping puzzle is 143, not 134, although I also see that The Riddler did not take into account the possibility that both coins turn up heads the same number of times. Does this suggest that the probability of both coins turning up heads the same number of times is 7 in 143?
Anyway, I'm miffed that this is yet another, "Interpret this puzzle as I see it," type of problem.
How would a player's strategy change if the boxes they open depend on previously opened boxes? If they don't find their own name in a box, does it offer any information about where their name is?
The additional information is the knowledge of the names in the box, combined with the knowledge that a previous player has not yet failed the game while employing a certain strategy based on names.
For example, let player 1 open box A and read the name. If it says "player 2", open box B, otherwise open anything but box B.
Let player 2 open box B and read the name. If it says "player 1", and player 1 has not failed the game, then the name "player 2" must have been in box A. There's your additional knowledge; reading either "player 1" or "player 2" is a guaranteed win, while anything else would still allow random guesswork.
I've formalized a simple strategy and done the math on a 4-player game. Unless I've miscalculated again, that'd yield roughly twice the winning chance of the unmodified game.
The strategy can be generalized to the n-player game, but I haven't done the math on that. I'm sure the formula is somewhere in some combinatorics textbook.
/edit: alright, I've found this gread combinatorics textbook called "wikipedia", which not only has the formula, it also links to the name of the problem. It yields ~30% for the 50 of 100 case, and the name is a bit less game-show-like, the 100 prisoners problem. Since the ridder's deadline is over, I've linked it, but it's fun to try to figure out before reading.
I got a fence layout of total length 2/3+sqrt(3)/4+pi/6 (~1.6232781). I think this is the best I can do, as I am unwilling to do further calculations.
See the diagram below. I am assuming that the fences satisfy a horizontal symmetry. The common point of the fences lies halfway between the left and right edges. One fence goes vertically down from this point to the bottom edge, and the other two are circular arcs from the common point to the left and right edges, intersecting the edges at right angles. (The isoperimetric problem can be used to show that these circular arcs are optimal.)
From the diagram, r is the radius of curvature of the arc, θ is the angle subtended by the arc, and b is the height of the vertical fence. θ ranges between 0 and pi/2. Some calculation gives r = 0.5/sin(θ), and b = 2/3 - r2(θ-0.5sin(2θ)), and the total length of the fencing is b+2rθ. Plugging in b and r, and minimizing gives the minimum as 2/3+sqrt(3)/4+pi/6 (~1.6232781) at θ=pi/6, and r=1 and b=2/3+sqrt(3)/4-pi/6 (~0.5760806).
The only way to beat this (if possible) is to use something that doesn't have horizontal or vertical symmetry.
Bobo the King wrote:
Anyway, I'm miffed that this is yet another, "Interpret this puzzle as I see it," type of problem.
Actually, the Riddler had a similar problem with a similar solution last year, and I had no trouble arriving at the cycle-following solution there, but I missed it here because of the wrong interpretation. (Seeing as how the other interpretation is an actual problem, I'll just call the earlier interpretation "wrong" from now on.)
The problem here was given for a very small (2 out of 4) number of boxes, didn't mention anything about choosing boxes in any order, gave no hint to the actual answer (5/12 for 2 out of 4, decreasing as the number of boxes increases but never less than 30.68%) and had a stated goal up front that was laughably easy ("Concoct a strategy that beats the naive strategy"), which further suggested the wrong interpretation. I know the 100 prisoners problem is supposed to be tricky, but it isn't supposed to be tricky in this manner. The fact that this puzzle comes only 5 weeks after another game show problem that is indeed solved using a predetermined strategy didn't help matters.
Bobo the King wrote:
Also, I just noticed that the official answer for last week's coin flipping puzzle is 143, not 134, although I also see that The Riddler did not take into account the possibility that both coins turn up heads the same number of times.
Based on the economics paper linked in the Riddler, I don't think the problem was ever intended to be mathematically precise, but only to "illustrate the common tendency to over-weight past data in forecasting the future", as the abstract puts it.
I'll post the exact wording of the problem (as posed by the Riddler) again:
On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?
By not being precise, the problem opened itself up to a few different interpretations:
@ "What is the smallest n such that if you flip both coins n times, observe the result, and guess which coin is doctored, your guess is correct at least 95% of the time?" (us) (answer: 134)
@ "What is the smallest n such that if you flip both coins n times, the doctored coin turns up more heads than the fair coin at least 95% of the time?" (paper, Riddler, Hector Pefo) (answer: 143)
@ "What is the expected number of flips required to first observe a result that determines the doctored coin with at least 95% certainty (posterior probability)?". (Laurent Lessard) (answer: about 73)
This week's Riddler challenges are fairly easy, I thought. Express is a variant of Mastermind, which I haven't yet worked out but I should be able to solve in a couple of hours. The Classic puzzle is one I heard on Car Talk years ago. I'm quite certain of my answer for the overall strategy, but the average number of trips is much more interesting. I'll try to dance around the answer without giving it away. The last two digits of my answer (rounding up) are 39. Notably, this is not divisible by 100. Does anyone else get the same answer?
Edit: On further thought, I strongly suspect that my answer is an overestimate. Nevertheless, I also suspect that the naive answer of 100 times the expected number of times the designated counter enters room 0 is an underestimate. The true answer should be somewhere in between. I'll think about it some more...
My attempt at Express...failed. Just do a cyclic shuffle of your current solution, and take note of how many you get right each time. 4 blocks gives 4!/4=6 unique cyclic orders. Assuming correct order 1234, here are 6 columns for the potential guesses, with the amount of correct blocks noted after.
1234..4.......1243..2.......1324..2
2341..0.......2431..1.......3241..1
3412..0.......4312..0.......2413..0
4123..0.......3124..1.......4132..1
1342..1.......1423..1.......1432..2
3421..0.......4231..2.......4321..0
4213..1.......2314..1.......3214..2
2134..2.......3142..0.......4132..1
If you get order {4000} you win, if you get the unique cyclic order {2021} then you've identified which order you have, and since the cyclic order does not repeat itself then you can also identify which specific setup you must have, thus guaranteeing the solution with at most 4 wrong guesses.
For the other 4 sadly, the cyclic orders {2101} are not unique, which means we still need further moves to tell these 3 sequences apart. Right now, there isn't any easy move to identify which of the 4 sequences you have in only one move, it'll probably be doable in two, requiring 6 failed moves thus 7 total.
Edit: Failure realised.
This week's Riddler challenges are fairly easy, I thought.
You must be smarter than me, because both questions are difficult in my opinion.
Classic puzzle:
Finding the overall strategy is tricky. The solutions are given on this site. I was only able to get the strategy for the case where the initial positions of the levers are known, but I failed to find the strategy when the initial positions are unknown and I had to look it up.
To summarize, the strategy is as follows: Call the levers A and B. Prisoners 2 through 100 each do the following:
- If lever A has not been flipped by the prisoner twice yet, and lever A is down, flip lever A to up. Otherwise, if lever A has been flipped twice, or if lever A is already up, flip lever B.
Prisoner 1 does the following:
- The first time Prisoner 1 goes to the lever room, if lever A is up, flip it to down; otherwise flip lever B. From this point on, Prisoner 1 keeps a running count, starting at 0. For the second and subsequent visits, if lever A is up, flip it to down and add one to the count; otherwise flip lever B and don't add anything to the count. When the count reaches 197, Prisoner 1 declares to the warden that all of the prisoners have been to the room.
For the average number of visits to the lever room made in total by the prisoners (assuming the prisoners are chosen uniformly at random, and assuming random initial lever positions), I calculated it as about 20476.663 using computer software. Bobo the King, how did you get your answer? Whatever it is, it isn't the same as mine.
Express puzzle:
Bobo the King, could you explain how to interpret the problem? I have read the statement of the problem over and over but I do not know what the Riddler exactly wants. Specifically, the part where it says "How many times should you have to consult the oracle, in the worst case, <footnote>Assuming you learn from each iteration and don’t keep trying the same wrong answers.</footnote> to assemble the tower correctly?" Does it want the worst case of the best strategy to minimize the expected number of consultations? The worst case of the best strategy to minimize the worst-case (maximum) number of consultations? The maximum number of consultations possible without any regard to strategy (bound by the rule that "you learn from each iteration")?
Edit:
Flip wrote:
This week's Riddler challenges are fairly easy, I thought.
You must be smarter than me, because both questions are difficult in my opinion.
I know that's not true. You're a freakin' genius.
FractalFusion wrote:
When the count reaches 197, Prisoner 1 declares to the warden that all of the prisoners have been to the room.
Oops. I thought it was 199, but I included the counter in my reasoning. This is why I never win the Riddler challenge.
FractalFusion wrote:
For the average number of visits to the lever room made in total by the prisoners (assuming the prisoners are chosen uniformly at random, and assuming random initial lever positions), I calculated it as about 20476.663 using computer software. Bobo the King, how did you get your answer? Whatever it is, it isn't the same as mine.
The naive answer is that it will be 19,700 visits to room 0 because it's the total count times the average frequency we expect the counter to enter the room. We know that can't be the right answer and is instead a lower bound because sometimes our counter will enter room 0 and not see the tally lever flipped up, especially as the tally nears 197. Begin by assuming that the tally is at 196 and just one or two prisoners remain who still have to pull the lever. We want to know how many times we can expect the counter to enter the room before seeing the lever flipped up. I modeled this as a negative binomial distribution and said that if one prisoner remains, the counter will enter room 0 twice before seeing it flipped up. If two prisoners are left, the counter will enter room 0 on average 1.5 times before seeing it flipped up. The probability that there is one prisoner left is 0.995 and the probability that two prisoners are left is 0.005 (which is the probability that the counter was picked first and they saw the lever up). These 2 and 1.5 visits by the counter correspond to 200 and 150 total visits. Continue backwards and you can calculate the total number of visits.
But most of the above analysis is wrong. Heck, I'm not even sure about the negative binomial distribution, which I've always had trouble interpreting. Assuming I haven't made a mistake there, I know I've screwed up in the step where I multiply the result of the negative binomial distribution by 100. I've incorrectly assumed that the probability that the counter enters room 0 is independent of whether he finds the tally lever up. If the counter finds the tally lever down on consecutive visits, it is far more likely (especially at low tallies) that he's simply entered the room consecutively. For example, if on his third visit to the room he finds the tally lever down, which is more probable: that the same prisoner flipped the lever up twice before and was the only intervening prisoner between the counter's second and third visits or that the counter merely entered the room twice consecutively? My method is probably an okay approximation toward the end of the tally, but wildly overestimates the number of visits early on.
Because my previous answer was 199, I had to recalculate the answer on the fly (possibly with yet more errors). I obtained 20,138, rounding up. Should you be interested, my formula is
100*sum(0.005/x + 0.995/(x+1) + 1, x, 2, 198)
which is bogus for the reasons I outlined above. Notably, my answer is a fair bit under yours and I already characterized my answer as an overestimate. It's possible that I'm completely misapplying the negative binomial distribution, but barring that, I would strongly expect the answer to be between 19,700 and 20,138. Then again, if your answer was obtained through computer simulations and you have a decent bound on the uncertainty, I can't really argue with that.
FractalFusion wrote:
Bobo the King, could you explain how to interpret the problem? I have read the statement of the problem over and over but I do not know what the Riddler exactly wants. Specifically, the part where it says "How many times should you have to consult the oracle, in the worst case, <footnote>Assuming you learn from each iteration and don’t keep trying the same wrong answers.</footnote> to assemble the tower correctly?" Does it want the worst case of the best strategy to minimize the expected number of consultations? The worst case of the best strategy to minimize the worst-case (maximum) number of consultations? The maximum number of consultations possible without any regard to strategy (bound by the rule that "you learn from each iteration")?
I interpreted the problem statement as your own second interpretation, that your strategy minimizes the maximum number of consultations. As it turns out, I don't think there's much difference between the first and second interpretations because the worst-case is a mere four consultations and I rather doubt that you could improve the average while doing worse in the worst-case.
I began by determining a lower bound of three on the number of consultations. Frank can give one of four answers, so the absolute best you could hope for is that Frank's answer will divide the set of possible permutations cleanly into four subsets. You'll guess once, consult Frank, and the best you could hope for is that the subsets corresponding to each possible answer all contain six elements. You'll guess again and the best you can hope for now is that the largest subset has two elements (6/4 = 1.5 = 2 when rounding up). This requires one more guess and one more consultation.
Of course, you know that Frank's answers can't divide the set of possible permutations evenly because if Frank says "four", there is exactly one permutation, corresponding to your guess. This suggests that four or more consultations will be necessary, although you still arrive at a lower bound of three if you assume the set is evenly divided into subsets if Frank's answers are "zero", "one", or "two". The only way forward is to do a fairly exhaustive search, aided by symmetry arguments.
Start with a guess of ABCD (I'm using letters to represent the permutations and saving numbers for other purposes, although my own notes use numbers everywhere). We have no information about the permutation, so any old guess will suffice and you could use this guess to fix the identities of A, B, C, and D. Frank will respond with "zero", "one", "two", or "four".
I'll digress here to discuss your strategies moving forward. In general, you'd like your subsequent guesses to subdivide the possible answers into subsets of even size and then to check that these subsets can be solved in just one guess, bringing your total number of guesses to three. It seems as if there are as many as 23 possible second guesses, but since Frank's response offers no hint about which pieces are in the right place, you can cut them down quite a bit with symmetry. I used cycle notation on the 24 different permutations and found that there are just four possible strategies for your second guess: a 4-cycle, a double-transposition, a 3-cycle, and a transposition (2-cycle). Respective examples of these four guesses include DABC, BADC, ADBC, and ABDC. You could use any permutation you want (except ABCD), but it will be strategically equivalent to one of these four.
Suppose Frank says "zero". This corresponds to one of nine derangements of ABCD. The most promising second guess is the 4-cycle (DACB), which subdivides these nine derangments into three possibilities where, upon a second consultation with Frank, Frank says "zero", three possibilities where Frank says "one", two possibilities where Frank says "two", and one possibility where Frank says "four". (Also promising is the 3-cycle, but I didn't thoroughly investigate it.) All that needs to be checked is that the three possibilities where Frank says "zero" or "one" can each be subdivided into sets of size 1 with your third consultation. I showed that this is possible by guessing any of the three possibilities.
Regarding the above deleted paragraph, I miscounted for the 4-cycle. Instead, the 3-cycle gives the best partition: three ways Frank could say "zero", three ways Frank could say "one", and three ways Frank could say "two". I've stared at these possibilities for a good while now and I'm fairly certain that they cannot be deduced in just one guess. If anyone would like to help out, see if there's just one guess you can take to Frank to distinguish between DCBA, CDAB, and BADC. I've amended my answer below to still work with the 4-cycle, which I believe remains the fastest way to the solution, at least on average.
I'll skip ahead to the instance where Frank says "two" in his first consultation. There are just six ways (four choose two) to obtain this response. As it turns out, your best strategy for a second guess is the transposition, ABDC. This corresponds to two ways Frank could respond with "zero", three ways he might say "one", and one way that he says "four". Again, the strategy for the case where he says "zero" is trivial, so all we need to do is check that we can distinguish between the three possibilities where he says "one" in just one guess. This also can be done by guessing any of the three remaining permutations.
Now the hard one, where Frank says "one" after the first guess. At first it seems promising because there are just eight possibilities, one fewer than we had to work with when Frank said "zero". Unfortunately, none of the four strategies produces a particularly good partition. The "least bad" strategy is the 3-cycle, ADBC, which partitions the set of possibilities into three where Frank says "zero", four where Frank says "one", and one where Frank says "four". It's looking grim if Frank says "one", but not quite hopeless because we might be able to uniquely determine which element we're looking at with just one more guess. By listing the possible permutations, however, you'll see that no two of them have any piece in the same place as any other, i.e., they are all derangements of one another. This means any guess we offer up where Frank could say "four" also results in three other possibilities where he says "zero". Boo. The best we can do is divide the list into two with this guess, then finish it off with one more guess and consultation, bringing the total to four. Two of the other strategies, the 4-cycle and the 2-cycle also result in subsets of four and I checked that these also cannot be done in three total guesses.
So in summary, begin by guessing ABCD and consulting Frank.
"zero" --> DABC --> "zero" --> CDAB --> "zero" --> BCDA
"zero" --> DABC --> "zero" --> CDAB --> "four" --> CDAB
"zero" --> DABC --> "one" --> DCBA --> "zero" --> CADB --> "zero" --> BDAC
"zero" --> DABC --> "one" --> DCAB --> "zero" --> CADB --> "four" --> CADB
"zero" --> DABC --> "one" --> DCAB --> "two" --> DCAB --> "zero" --> CDBA
"zero" --> DABC --> "one" --> DCAB --> "two" --> DCAB --> "four" --> DCAB
"zero" --> DABC --> "two" --> DCBA --> "zero" --> BADC
"zero" --> DABC --> "two" --> DCBA --> "four" --> DCBA
"zero" --> DABC --> "four" --> DABC
"one" --> ADBC --> "zero" --> BCDA --> "zero" --> DACB
"one" --> ADBC --> "zero" --> BCDA --> "one" --> CBDA
"one" --> ADBC --> "zero" --> BCDA --> "two" --> BCAD
"one" --> ADBC --> "one" --> DBCA --> "zero" --> CABD --> "zero" --> ACDB
"one" --> ADBC --> "one" --> DBCA --> "zero" --> CABD --> "four" --> CABD
"one" --> ADBC --> "one" --> DBCA --> "one" --> DBAC --> "zero" --> BDCA
"one" --> ADBC --> "one" --> DBCA --> "one" --> DBAC --> "four" --> DBAC
"one" --> ADBC --> "four" --> ADBC
"two" --> ABDC --> "zero" --> DBCA --> "one" --> BACD
"two" --> ABDC --> "zero" --> DBCA --> "four" --> DBCA
"two" --> ABDC --> "one" --> CBAD --> "zero" --> ADCB
"two" --> ABDC --> "one" --> CBAD --> "one" --> ACBD
"two" --> ABDC --> "one" --> CBAD --> "four" --> CBAD
"two" --> ABDC --> "four" --> ABDC
"four" --> ABCD
By my count, that's 24 possibilities, but you may want to check that they're all distinct, consistent with Frank's answers, and that no other permutations result in the same answers.
Edit: There's an error in the above reasoning, related to the possibility that Frank says "zero" after your first consultation. It may not be possible in this case to identify the permutation in three guesses after all. I'll leave my work as-is until I can fix it.
Edit 2: Removed spoiler tags, since the deadline has passed and I'd like to make this more readable. Also, I fixed the error I had and the strategy should now be sound.
I'll explain how I got 20476.663 (I didn't use simulation, just calculation of expected values which requires a computer).
First, if p is the chance of success, the expected number of trials required to get the first success is 1/p. I assume that everyone understands this (this is a special case of the negative binomial distribution). For example, at any given point, the expected number of visits required to get Prisoner 1 to visit the room is 1/(1/100)=100.
Now define:
● n: the number of prisoners who still need to flip up the tally lever once or twice.
● k: the number of prisoners who still need to flip up the tally lever twice.
● (n,k): the current tally lever state of Prisoners 2-100, n and k defined above.
● E(n,k): the expected number of visits required to go from state (n,k)→(0,0), where the tally lever starts and ends in the down position (Prisoner 1 must witness the tally lever in the up position and flip it down for the final time).
Now E(0,0)=0. We calculate a recurrence relation for E(n,k) as follows: there are n prisoners who still need to flip the tally lever; k who need to flip it twice and n-k who need to flip it once. The expected number of visits until one of these n prisoners is selected is 100/n. Then Prisoner 1 has to be selected (expected number of visits 100). Finally, the next state is
● (n,k)→(n,k-1), if a prisoner was selected who needed to flip it twice, with probability k/n, or
● (n,k)→(n-1,k), if a prisoner was selected who needed to flip it once, with probability (n-k)/n = 1-k/n.
So the recurrence equations for n>0 are:
● E(n,0) = 100/n + 100 + E(n-1,k).
● E(n,k) = 100/n + 100 + (k/n)E(n,k-1) + (1-k/n)E(n-1,k).
● E(n,n) = 100/n + 100 + E(n,k-1).
Using this, we calculate the important values
● E(1,0) = 200,
● E(99,98) ≈ 20426.653,
● E(99,99) ≈ 20527.663.
Finally, we consider the start. If the tally lever starts up, then Prisoner 1 has to be selected (expected number of visits 100), in order to flip it to the down position first. Thereafter, we need the expected number of visits required to go from (99,99)→(1,0) (remember that a count of 197 is sufficient to determine that all of Prisoners 2-100 have visited the room). So:
● Exp(start up) = 100 + E(99,99) - E(1,0) ≈ 20427.663.
If the tally lever starts down, then it depends on the first prisoner to visit the room. There are two cases:
Prisoner 1 is selected: The tally lever remains down. As above we need the expected number of visits required to go from (99,99)→(1,0). So:
● Exp(start down, P1) = E(99,99) - E(1,0) ≈ 20327.663.
Prisoner 2-100 is selected: That prisoner flips up the tally lever. Then Prisoner 1 has to be selected (expected number of visits 100), but that flip up of the tally lever is not counted. To get a count of 197, we need the expected number of visits required to go from (99,98)→(0,0). So:
● Exp(start down, P2-100) = 100 + E(99,98) ≈ 20526.653.
So:
● Exp(start down) = 1 + (1/100)Exp(start down, P1) + (99/100)Exp(start down, P2-100)) ≈ 20525.663.
Finally:
● Exp(visits) = (1/2)Exp(start up) + (1/2)Exp(start down) ≈ 20476.663.
Bobo the King wrote:
ABDC would not return "zero" in this case; it would return "one" instead.
I noticed because the starting case ABCD --> "two" was the case which I used to convince myself that five consultations (four to identify the correct permutation) was required in the worst case regardless of which permutations you use for the second and later consultations.
I believe the rest of your reasoning is correct. (By the way, I think that how you interpreted it is the most reasonable interpretation of the problem. If that is what the Riddler intended, then the footnote was not only pointless but misleading as well.)
Suddenly I started thinking: Are there any convex polyhedra with an odd number of faces, where each face is an n-gon, for a given fixed n? (In other words, every face is a triangle, or every face is a 4-gon, for example. Obviously they don't all need to be the same shape, only to have the same number of sides.)
If we remove the requirement for convexity, then there are examples (can you think of one?), but I couldn't think of a convex example.
Riddler Express. First, race 5 packs of 5, take note of the top 3 places. Thus
abcde...............cde
fghij................hij
klmno..............mno
pqrst...............rst
uvwxy.............wxy
That'll be 5 races. The first two columns are discarded since we now know at least 3 horses are faster than them. So next, race the winners.
ejoty............oty
That identifies y as the overall winner, but we still need positions 2/3. We can discard cde/hij, since we know both e and j are lower than 3rd, and so cd/hi must be too. Likewise t is at most second, so anything it beat can be at most 3rd. O can be at most 3rd, so anything before cannot be in top 3. Thus this narrows down the selection from our initial winners down to
...
...
..o
.st
wx.
Which conveniently is 5 remaining, so we can just race 'em.
ostwx..........twx
Which gives you the 2nd/3rd place in 7 races, deriving the top three: wxy
From the diagram, r is the radius of curvature of the arc, θ is the angle subtended by the arc, and b is the height of the vertical fence. θ ranges between 0 and pi/2. Some calculation gives r = 0.5/sin(θ), and b = 2/3 - r2(θ-0.5sin(2θ)), and the total length of the fencing is b+2rθ. Plugging in b and r, and minimizing gives the minimum as 2/3+sqrt(3)/4+pi/6 (~1.6232781) at θ=pi/6, and r=1 and b=2/3+sqrt(3)/4-pi/6 (~0.5760806).
The only way to beat this (if possible) is to use something that doesn't have horizontal or vertical symmetry.
