Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I glanced at this week's riddler puzzles and said, "Those aren't too tough," before getting sidetracked and only got around to solving them now.
I was able to do the Express puzzle without using any calculus, just some vector algebra:
I began by altering the problem statement slightly. I had one line go from coordinates (0,0,0) to (1,1,1) and the other go from (0,0,1) to (0,1,0). It is apparent that the line of shortest distance connecting these two lines will be perpendicular to both-- I can do the rotations mentally to convince myself of this and I'm sure there is a formal proof written in many textbooks. By rotating the cube so that one of the lines is horizontal and the other is vertical, it becomes clear through symmetry that ep1 is at (0,1/2,1/2). All that remains is to find ep2. This is where the vector algebra comes in. The spanning line must be perpendicular to both and so the dot product between (ep2-ep1) and (1,1,1) must be zero. Taking the coordinates of ep2 to be (x,x,x), we quickly find that 3x = 1 and so x=1/3.
I checked my work by computing the lengths of the sides of the triangle defined by the origin, ep1, and ep2. The origin to ep1 has length 1/sqrt(2), the origin to ep2 has length 1/sqrt(3), and ep1 to ep2 has length 1/sqrt(6). This all but confirms the answer because these form a Pythagorean triplet with the origin to ep2 being one of the lines in the problem statement.
All that remains is to transform back into the coordinates of the problem statement. After doing so, we see that ep1 remains at (0, 1/2, 1/2) and ep2 is at (1/3, 2/3, 1/3).
For the Classic puzzle...
I was able to easily set an upper bound of 11 guesses by running through each permutation, guessing twice to return the safe to its starting state...... but this can be improved to just three guesses by going through each cyclic permutation of ABC. No matter the safe's correct combination, each lock will be toggled exactly once.
The problem statement is actually ambiguous (what a surprise...) since it doesn't explicitly state that all three locks begin in the "locked" state.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
fsvgm777 wrote:
feos wrote:
It's physically impossible if you're standing before an unmodified cabinet. But it's digitally possible to send those inputs, and it's possible for the game to process them.
You're missing the point. This is an unmodified arcade cabinet of the game (ignore the condition). On a SNES controller, it is possible with a ton of twiddling to actually input L+R/U+D. On an arcade cabinet, with a joystick, as Spikestuff pointed out, it's literally impossible unless you want to completely break the joystick (and the cabinet) apart. Similarly, you can't input L+R/U+D on an N64 joystick or basically any joystick.
£e Nécroyeur, it would be really nice of you to actually respond to criticism instead of flatly ignoring it, just like you did with your Track & Field submission.
I wouldn't be so quick to accuse feos of missing the point. You both make valid points. The game's coding is perfectly willing and ready to accept an input that includes both left and right or up and down. That's feos's point. Your point is that it's physically impossible to do so with actual hardware. (Well, maybe you could waggle the joystick back and forth quickly enough that it interprets it as left+right, but I'll take a "I'll believe it when I see it" standpoint.)
So the question really comes down to whether we see the physical hardware as an integral component of the game-playing process. If it is, then left+right can't be allowed. If it isn't, then all we care about is the digital input sent to the game. To muddy the waters further, I'll mention that on a home console, we can perhaps purchase controllers that allow us to perform inputs that are effectively impossible on stock controllers. With an arcade game, such as this one, the controller is presumably fixed by the manufacturer. I'm not sure if that is an argument for or against allowing left+right.
Incidentally, I take the left+right question to not apply to the N64. The controller's output should be something like an x-y coordinate pair based on the state of the joystick. Any N64 game should be completely unable to meaningfully interpret a left+right input, even if it were physically possible. Someone with a bit more knowledge of N64 hardware will need to back me up on this.
Edit: By the way, I'm personally indifferent as to what the fate of this run is, but as a general rule, I fall back on entertainment value, since TASes are a form of entertainment at their core. Glancing at the submission text, I notice that allowing impossible joystick inputs opens up multiple interesting tricks, which may significantly increase the entertainment value of the run. I suggest that £e Nécroyeur or someone else could produce a quick run that attempts to show what a run that doesn't use left+right might look like.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
There once was a man from Peru
Whose limericks stopped at line two
There once was a man from Verdun
Along those lines, has anyone heard the limerick about the guy from Nero?
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
Anyway, I jogged my memory by checking out Wikipedia's page on contour integrals. Example 2 there corresponds to your problem statement with t = i*a^2
Example 2 with t = i*a^2 gives the integral of e^(-a^2 z)/(z^2+1).[1] OmnipotentEntity asked for the integral of e^(-a^2 z^2)/(z^2+1).
The method described in Example 2 doesn't seem to work for e^(-a^2 z^2)/(z^2+1), primarily because the arc integral can't be bounded reasonably (values of z near pure imaginary numbers give values far from zero in the negative direction when squared; this gives a very large number for e^(-a^2 z^2)). In fact, WolframAlpha claims (citation) that the answer is not pi*e^(-a^2) (the expected answer being the contour integral around z=i), but actually pi*e^(-a^2)*(1-erf(a)), where erf is the error function. I wouldn't know how to prove this.
[1] Actually, this isn't even valid. In Example 2, t specifically has to be a real number for the argument that the arc integral goes to 0 to hold.
Derp derp derp. Sloppy math on my part yet again...
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
OmnipotentEntity wrote:
Here's a fun integral that I had to solve recently.
Integral -inf to inf exp(-a^2 x^2)/(1 + x^2) dx
Interested to see what approaches you take. (You may assume a is positive.)
Complex analysis is a glaring weakness in my math background. I'm not especially bad at it, I just tend to forget it readily. Frankly, I've never been impressed that the big draw is supposed to be that you can calculate certain integrals over the real line. I really should get into the deeper stuff like conformal mappings and such.
Anyway, I jogged my memory by checking out Wikipedia's page on contour integrals. Example 2 there corresponds to your problem statement with t = i*a^2 (I promise I didn't peek at the answer). I then hopped over to the page on residues for help computing the residue of the pole at z=i. It's apparent from the numerator of the expression that the function goes to zero very quickly as |z| goes to infinity, so I computed the residue with a limit, imagined a contour along the real line and around that pole, and then took the real integral to be equal to the contour integral. My answer agrees with both Wikipedia's and Wolfram Alpha's.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
Riddle 1:
...
the maximum number of unique handshakes per arrangement is n (everyone shakes the hand of the person to their left and to their right, which double-counts the number of handshakes)
The maximum number of unique handshakes per arrangement is far greater than n; a person is permitted to reach across the table to shake the hand of someone not sitting adjacent, provided that arms never cross.
Ah! I didn't realize that members could stretch their arms across the table like Dhalsim from Street Fighter.
But... then wouldn't the number of arrangements needed be just one? Everyone just sits where they are and then continues reaching across the table through as many rounds as necessary? I've peeked at your answer and I can't quite figure out how you're interpreting this problem.
FractalFusion wrote:
Bobo the King wrote:
Riddle 4:
...
It turns out there's one free variable, so you need to use an augmented matrix and put it in reduced row-echelon form.
There are 5 equations and 5 unknowns in this problem, and according to my calculation, there is a unique solution. I don't know where this "free variable" is coming in. Did you mean redundant equation? (But there are only 5 equations.)
You may possibly be correct that the last row is an integer multiple of some other rows/columns (but I haven't worked out the problem to completion yet so I wouldn't know).
See the edit to my previous post. The "free variable" comes from the fact that the value of candy corn is zero. This means we don't need to demand that its coefficient match up in our linear combination of the other equations.Edit: Also, any insight into problem 3?
Edit 2: I think I see now where the handshake problem becomes nontrivial. It's in the second rule: "During each round of handshakes, every member of LINK must be shaking one and only one hand." This means that you can't decide not to shake a hand and this explains why the two sample number of members were both even values. It also means that two people sitting two seats apart (with one person between them) can't possibly shake hands because the person they span will be cut off from all other handshakes.
Incidentally, this means you aren't the only new inductee to LINK. New members are necessarily knighted in pairs (or other multiples of two).
All right, I think I can stumble through it from here.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
New riddles.Riddle 1:
I haven't solved this one, but it's easy to show that with n knights, you need at least (n-1)/2 arrangements to ensure everyone gets a handshake. The total number of handshakes needed is 1/2*n*(n-1) and the maximum number of unique handshakes per arrangement is n (everyone shakes the hand of the person to their left and to their right, which double-counts the number of handshakes). I'll try to see if there's a strategy to obtain this minimum number of arrangements.
Riddle 2:
This needs some careful interpretation. K is inserted somewhere within the integers 0 through 9, shifting some of the integers up. For example, if K = 3, then 0 remains 0, 1 remains 1, 2 remains 2, K takes the place of 3, 3 becomes 4, 4 becomes 5, and so on, up to 9 becoming 10. I solved this by converting one of the equations from a guess for base keleven to base 11, carefully solving them, and then converting the solution back to my guess for base keleven. One of my guesses worked.
Riddle 3:
This is the riddle I'm most interested in and I can't make any headway on it. Someone in the comments pointed out, "For Riddle 3, how does any strategy give a nonzero expected score? Am I missing something?" I'm in complete agreement. If my current score is S and the value of the current question is N, then by guessing, I can change my score to either S+N or S-N. If I skip the question, my score remains at S.
On the other hand, this reminds me a little of the St. Petersburg lottery or maybe a Martingale betting strategy, both of which give unexpected results. Could someone weigh in with either a different interpretation of the problem statement or a correction to my logic? In the meantime, I'll play around with tests that have just 2 or 3 questions, seeing if I can bring the expected value of your score up from 0. I think there would be some interesting math involved if, say, your score could not be less than 0 or you are attempting to outperform some percentage of other students taking the exam.
Riddle 4:
This riddle was straightforward with matrices. My first effort was to guess and check, but I cheated just a little with my calculator to find that the answers aren't integers. Then I cheated entirely to see that the answers are horrendous. I highly recommend setting up the matrix and just solving it computationally. The determinant is a two-digit prime number, the numerators of the variables are two- and three-digit numbers, and the numerators of the values under the question marks are four digit numbers...
... with just one exception. The question mark corresponding to the fifth row is 31. I'm trying to figure out exactly why; it should be some simple linear combination of the other five equations. I gave it one good effort but I think my analysis is off. I'll attempt it again. It turns out there's one free variable, so you need to use an augmented matrix and put it in reduced row-echelon form.
Edit: I found my error in riddle 4. My reduced row-echelon form was correct, I just made a small math error when plugging in values. We have a free parameter because the value of candy corn is zero. Our equations in matrix form are:
(The order of the variables here is acorns, candy corn, apples, leaves, pumpkins.)
The equation corresponding to the fifth row is:
This equation is necessarily a linear combination of the other five equations, which are linearly independent. Our augmented matrix is then:
In reduced row-echelon form, this becomes:
Taking the variables to be A, B, C, D, and E, where E is our free parameter, this tells us:
So notice that A = -B and C=1. Since the right hand side of the equations corresponding to A, B, and C are all 31 and the right hand side of the remaining equations is zero, this proves that the right hand side of equation from the fifth row is 31. And of course this remains true when we demand that the coefficient of candy corn match up.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Flip wrote:
Riddler Express
Since we're dealing with hexagons here, sections form nice equilateral triangles. The shaded area in question is one third of its triangle, where the triangle occupies one sixth of the main hexagon, thus the shaded part has area 1/3 x 1/6 = 1/18.
Riddler Classic
This seems relatively easy, just split it up into a bunch of semicircles.
Thus
A=A1+A2=(a1-a2+a3)+(a4-a5+a6)
=π/2 ( (10+2)2 - (10-2)2 + 22 ) + π/2 ( (5+2)2 - (5-2)2 + 22 )
=π/2 ( 122 - 82 + 22 + 72 - 32 + 22)
= π/2 (144-64+4+49-9+4) = π/2 (128) = 64π
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
To keep my brain sharp, I've revisited an old Riddler challenge. In particular, I was interested in modeling the Riddler Classic challenge here as a Markov chain. I was successful, after a number of hours of work. I'm having trouble understanding the posted solution, though. What do the variables there represent? Since they work toward ABCD = 9, it would seem that they represent an average number of turns to reach state AAAA, but I'm having trouble seeing exactly how the equations reflect that fact. Is there a general name for this procedure?
I began by drawing up the directed, weighted graph corresponding to the Markov process, similar to how it was outlined in the posted solution. I also included a "sink" corresponding to a "game over" state so that values wouldn't accumulate in the state AAAA. This meant that I could calculate the probability directly from powers of the matrix without needing to subtract the previous power. Here's the matrix I came up with:
You can verify that these correspond to the probabilities of going from/to the states ABCD, AABC, AABB, AAAB, AAAA, and the "null/game over" state respectively.
There's a problem. This matrix is not diagonalizable because the eigenvalue 0 has an algebraic multiplicity of 3 but a geometric multiplicity of 2. After staring at this for a long while, I determined that for the specific initial state of ABCD, the probability of finding the balls in state AAAB is always exactly twice the probability of finding them in state AABB. This allows you to combine those variables into one. I also discarded the ABCD row and column to the matrix since it will immediately leave that state. (As we'll see in a minute, that means we have to be a little careful with our powers.) Here's the new matrix:
That's much easier to work with and it is diagonalizable. The average number of turns until the game ends is then:
Where we multiply from the left by [0, 0, 1, 0] because we're interested in the state AAAA and we multiply from the right by [1, 0, 0, 0] because that is the initial state.
Writing a few terms of the sum out explicitly, it becomes apparent that this is a variant of the geometric series. We merely need to take our diagonal matrix of eigenvalues and replace them with x*(2-x)/(1-x)^2, where x represents each eigenvalue. One of our eigenvalues is 1, giving an infinite entry in our diagonal matrix. This entry is later multiplied by zero which apparently nullifies it (since I obtained the correct answer). I'll leave the details of the proof to whoever's following along.
I also tried repeating the proof with a new matrix that doesn't have a "sink" defined in it:
Writing out the average number of turns in terms of this matrix results in something based directly off of the geometric series. The problem then boils down to computing C*(C-1)-1, where 1 is the identity matrix. Unfortunately, C-1 is not invertible, so I stopped my attempt at a proof there. On the other hand, my original proof had an infinity in it and I was able to get around that, so I wonder if the same is possible here.
Anyway, what I'm really curious about is what the Riddler's official solution is trying to say and whether this procedure is general.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Flip wrote:
Riddler Classic
A typical path can be described as 2211221222111 etc. Given n leaps of size 2, this covers total length 2n, thus leaving the remaining 20-2n leaps for size 1, for a total of n+(20-2n)=20-n leaps total. Thus a path with a given amount n of 2-leaps can be ordered in (20-n)Cn ways. Since we can have a maximum total of 10 leaps of size 2, this gives a grant total
T=Sum{n=0,10} (20-n)Cn = 20C0+19C1+18C2+....+10C10
=1+19+153+680+1820+3003+3003+1716+495+55+1
=10946
But for jumping with more than two potential leap sizes, dunno.
I obtained the same value in a slightly different way and I believe I can do other leap strengths as well. There's one way to reach a lily pad one unit away (jump one lily pad forward). There are two ways to reach a lily pad two units away (jump two lily pads forward or jump one lily pad forward twice). For three lily pads, you can enumerate all three directly or you can notice that the frog will first have to reach either the first or second lily pad. It could either jump two units from the first lily pad or jump one unit from the second lily pad. In other words, if we label the number of ways to reach the kth lily pad nk, we have n3 = n1 + n2 = 1 + 2 = 3.
You can probably see where I'm going with this. The frog could reach the 4th lily pad from the 2nd or 3rd lily pad and could reach the 5th lily pad from the 3rd or 4th. It should be quickly apparent that nk = nk-2 + nk-1 where we initially have n1 = 1 and n2 = 2. This defines the Fibonacci sequence (offset by one). Simply add them up to find n20 or use your favorite formula or other tools. In my case, I just looked it up on OEIS. The 21st Fibonacci number corresponds to the 20th lily pad and this value is 10946, in agreement with your answer.
We can quickly generalize this to hops of any length by defining a new recurrence relation. I'll leave that to you, if you're interested.
Riddles were super easy this week.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Warp wrote:
A table tennis ball has a diameter of 40 millimeters, and a mass of 2.7 grams. Two of them are floating in empty space, at rest relative to each other, 10 meters apart, with no other significant forces affecting them.
How long does it take for them to collide, and what's their relative speed when they do so?
This is a classic problem and I'm rather proud of my treatment of it. When I was in graduate school, everyone else in the class just pulled the answer from an online document which had a step that stated, "The above integral can be evaluated as..." Well that's no fun. My solution sidesteps the calculus, which appears in an earlier derivation.
It can be shown using Kepler's laws of motion that the time it takes for two bodies that have a 1/r^2 force dependence to complete one orbit is
where a is the semimajor axis, k is the force coefficient, and mu is the reduced mass:
For gravitational attraction, we have
and so our original equation reduces to
So how is this useful when the objects aren't orbiting and instead are gravitationally attracted directly toward each other? Well, a collision-course is just an elliptical orbit with an eccentricity of 1. Furthermore, the period of the orbit can be split into four different sections that take equal time, assuming the objects can pass through one another: the objects are released, then they "collide" (pass over the same point), then they swap places, then they "collide" again, then they return to their starting point. We're therefore solving for
For the values you supplied (a = 5 m, m_1 = m_2 = 2.7 gm), I calculate 2.93*10^7 seconds or 339 days. Not too shabby-- I was expecting a longer length of time. This is a close approximation to the real answer, which will be slightly less due to the finite radius of the balls. Before we improve the answer, we'll need to calculate the final speed of the balls.
If the balls had zero radius, their speed as they pass through each other would be infinite. Instead, we'll need to conserve energy to find their final velocity:
where m is the mass of either ball, R is their initial separation, d is their diameter, and v is their final velocity. On the left hand side is the change in the gravitational potential energy and on the right hand side is the sum of the kinetic energies of the two balls.
Rearranging this expression, we find
which evaluates to 2.11*10^-6 m/s. Each ball has 20 mm left to traverse until they are directly on top of one another, which at their final rate of travel wold take 0.109 days (2 hours and 37 minutes). (It's actually a bit less than that because the balls would continue to accelerate if they didn't collide.) This is insignificant compared to the 339 days that they had already been traveling.
Finally, I'll suggest that this answer is based on the incorrect assumption that there will be no electromagnetic forces between the two balls. It would not surprise me if celluloid (which is what table tennis balls are made of) is slightly diamagnetic. This would give rise to a slight magnetic repulsive force between the balls that may not be negligible compared with the gravitational force. These kinds of problems-- with two spherical objects exerting a magnetic force on each other that further polarizes them-- are actually quite difficult and an approximation of their solution was only found around the mid-'90s. As a gut feeling, I expect the magnetic force contribution to be negligible, but I'd like to put pen to paper to confirm it.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Oh god, that 100 prisoner problem is going to haunt me for a while.
To take my mind off of it, the horse racing problem is interesting and similar to last week's Riddler Express challenge with the architecture. (Speaking of, I'm annoyed that the official answer indicates you need to confirm the order with Frank at the end, but never mind that.) Ultimately, we have 25 choose 3 = 2,300 possibilities to sift through, since we don't seem to care about the order of the top three finishers. I believe that since each race has 5!=120 ways of being ordered but the finishing position of the last two horses is irrelevant, so each race divides the number of possibilities by no more than 60. Unfortunately, the actual "average reduction in the number of possibilities" must be much lower, since 60 would allow us to answer the question in two races and we know the answer must be at least five since every horse must race at least once. It's a really crappy lower bound.
The optimal solution may be some tangled mess of racing horses that have already raced before in an effort to build order as we go along. I guess I can get things started with the first race. There is one way the result could involve all of the top 3 finishers, 20 ways it could include two of the top 3, 20*19/2=190 ways it could include one of the top 3, and 20*19*18/6=1,140 ways it could include none of the top 3. From there, I'm stuck and I don't know how to use this information to investigate further trials. I suspect Flip is on the right track (at least for the official solution, not the optimal one), but that's all I can come up with.
The Price is Right question seems like it would be easier to thoroughly investigate, although FractalFusion has warned in the past that game theory problems are too difficult for Riddler challenges. I'll look into it.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King 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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
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...
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
creaothceann wrote:
Warp wrote:
Bobo the King wrote:
I'm about 40 episodes into Ranma 1/2. It's mostly met my expectations
It starts very interesting, but in later seasons succumbs more and more into lack of new ideas, and introducing tons and tons of new characters who have little to no relevance (it's almost like they replaced coming up with new, original, interesting ideas with just introducing the thirtieth-or-so new character that has never been seen before.) Still some good episodes in the later seasons, but more rarely.
After the series proper, the OVAs are a good watch.
The author of Ranma, Takahashi Rumiko, also created Kyoukai no Rinne which started airing in 2015. I watched some episodes of it, but ultimately decided to drop it because it just wasn't satisfying. Art was average at best, plot complexity seemed to be aimed at little children, and story progression seemed carefully tied down to allow for as many episodes as possible, with only a few drops of development (like Rinne's backstory).
I only saw one episode on Ranma (the one where Shampoo was introduced), and at least that one episode seemed actually interesting. Unfortunately it's also about 160 episodes, according to MAL.
I'll reiterate my recommendation of the manga, if you haven't read it. Its artwork is delightful and the reader has a lot more control over things like the timing of the jokes, which are sometimes mis-cued in even the better episodes of the anime. I think there are other ways that it surpasses the anime (for example, I know the anime does not have a proper ending), but I can't articulate them at this time.
The full manga can be found here. Be aware, however, that it switches to a fan translation halfway through and the quality of the fan translation fluctuates wildly.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I'm about 40 episodes into Ranma 1/2. It's mostly met my expectations, which is unfortunate, since my expectations were rather low. It has its moments.
The manga was an absolute blast, though. Highly recommended, and I'd argue the anime would be difficult to watch without already being familiar with the manga.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Tub wrote:
*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?
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Tub wrote:
Bobo the King wrote:
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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Patashu wrote:
I don't understand it either, but adding to my confidence that it could be a cosmic ray was that one time I was watching a streamer play Yoshi's Island in the first level (I think it was Trihex?) and they suddenly, with no explanation, teleported straight upwards in the air, which looked extremely like a single bit flip in the y co-ordinate.
That's consistent with a bit flip, but it doesn't offer any evidence as to whether these two apparent bit flips were caused by software or hardware. Based on your additional evidence, am I supposed to believe that these cosmic rays "seek out" y coordinates in the RAM?
This is very fishy to me.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Dredging up old news, it's always bugged me that the "accepted" explanation for the upwarp is a cosmic ray bit flip. In particular, I think about the megabytes upon megabytes of RAM in the game and find it eerily coincidental that the one bit affected controls Mario's z position. If these bit flips happen roughly at random, we would expect many softlocks, strange poses, spawning/despawning enemies, random power-ups, glitched graphics and text, timer skips, and innumerable other strange effects. But no, the one time a bit flip was caught on camera, it happened to affect only Mario's position, which is about as alluring a glitch as we could possibly hope for.
Maybe someone who has a better understanding of computer architecture and the RAM layout of SM64 will weigh in to say that this is not so unexpected. Until then, my money is firmly in the "exploitable software glitch" camp.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Another week, another two Riddler challenges. As with last week, I found the Classic puzzle to be more straightforward than the Express one.
For Classic, I obtained an optimal strategy that was better than 1 in 10. (As usual, I'm keeping this post spoiler-free.) I found eleven strategies that were distinct even through symmetry considerations. Finding those strategies was rather tedious, but testing them took a few minutes in Excel. I would like to know about the extra credit, however. I scaled up my strategy and found a probability of about 1 in 10^29. I suspect this is not optimal, but my reasoning doesn't amount to anything more than a gut feeling.
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.
Riddler Classic This seems relatively easy, just split it up into a bunch of semicircles.
Thus A=A1+A2=(a1-a2+a3)+(a4-a5+a6) =π/2 ( (10+2)2 - (10-2)2 + 22 ) + π/2 ( (5+2)2 - (5-2)2 + 22 ) =π/2 ( 122 - 82 + 22 + 72 - 32 + 22) = π/2 (144-64+4+49-9+4) = π/2 (128) = 64π
