Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
If you take the harmonic series and remove only the terms that contain a 9 will the series converge or diverge? Prove it.
The series converges. Proof: Among all the positive integers that don't have the digit 9, there are 8 1-digit numbers, 8*9 2-digit numbers, 8*9*9 3-digit numbers, ... , 8*9k-1 k-digit numbers, and so on. Therefore the series is bounded above by
8(1)+8*9(1/10)+8*9*9(1/100)+...+8*9k-1(1/10k-1)+...
= 8(1+9/10+(9/10)2+...+(9/10)k-1+...)
= 8(1/(1-9/10)) = 8*10 = 80,
and the summation terms are all positive and go to 0. Therefore it converges.
Same argument if you exclude terms with the digit j, j something other than 9. (For j=0, the 8's in the proof above become 9's.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Actually I prefer watching at 0.5x speed. (This TAS really is super fast.)
Unfortunately for you, I have played this game to death as well as speedran it on "fast speed max" many years ago. So I have a lot of comments.
DrD2k9 wrote:
This is basically an interactive prologue to the game, but there are necessary items that must be collected from the lockers in the airlock to complete the game.
The items in the locker are not necessary to complete the game. There are alternate solutions for the Labion Terror Beast and the platform guard on the next screen. It is unknown which strategy is faster.
- Getting the keycard: You don't need to get the keycard off the dead guard at the crashed hovercraft. I think it is faster to get the keycard from the platform guard if you stone him, especially in your TAS where he falls right in front of the door (if you lure him down, you don't even need a keycard).
DrD2k9 wrote:
Side Note: I was absolutely floored that I was able to navigate the root maze at 'fastest' game speed without dying or having to change speeds
You do not need to do the root maze or get the berries at all. By taking advantage of a glitch, you can enter the deep part of the swamp before the monster gets you, then "hold breath" to escape. (To do this, enter the screen from the bottom, going to the right, then go up-right when you are about 1/4 of the way across, before the monster gets you. Going diagonally makes it harder for the monster to get you.)
DrD2k9 wrote:
This is the insanely long portion of this TAS! It's roughly three and a half minutes of watching Roger sit in one place. He takes the shuttle off the planet and tries to escape but has the shuttle controls overridden by Vohal which brings Roger to the asteroid. It's a really boring portion to watch
If it is strictly timed based on the system clock with no way to speed it up, then I think there are fun things you could have done during this sequence, without slowing down the TAS.
DrD2k9 wrote:
He also briefly stumbles into a unisex bathroom
About that, since you came from the right side of the screen, you could have entered the right door and exited the left, instead of entering and exiting the left door.
- About stopping the salesman launch: IIRC, it is possible to make it to the end of the game before the salesman launch timer runs out. (On Version 2.0F anyway; I recall that different versions had different timer amounts.) The game at the end simply says something like "Unfortunately, you failed to stop the launch of the clones dooming Xenon to the most horrible of fates! Way to go, %s1.", then continues with the ending. It is not a death.
- About the oxygen mask and the tube glass cracking sequence: If the game is on a fast enough speed like "fastest", I think it is possible to make it to the door after the cracking occurs but before the game kills you off. I could be wrong; the timing of some events seems a little different in JPC-rr (as opposed to DOSBox), so it could simply not be possible on JPC-rr.
DrD2k9 wrote:
Unable to both open a pod and enter before being caught, Roger must flee the robot.
This is why lower speeds exist. It should be possible to "press button" then quickly "go pod" in time, without having to flee the robot. If not possible on "fastest", it should be done on "fast".
Speaking of "fastest" being hard to control, I'm not sure why the input fps is set so low. On PC, you should be capable of an input fps of 1000 at least. IIRC the last time I used JPC-rr, I think there was a way to change the input fps.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Great that there was a surprisingly easy way to fix the emulation errors. This TAS is looking good now.
c-square wrote:
Doing this requires three extra slot pulls and six 'Y-enter' rng skips. It takes 8 frames for a losing slot pull, 10 frames for a winning slot pull and 7 frames to do a 'Y-enter' skip. In the end, this route costs 70 frames in RNG manipulation:
Assuming I understand how the random() calls work, I found a strategy that costs only 32 frames:
(first number is index but is different from yours; mine has 0 at index 0)
By the way, how many frames does it cost to exit and re-enter the machine? How about saving and restoring?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.
The number of possible handshakes per arrangement is not important to this problem though. The problem asks for the number of unique seating arrangements required to get everyone to shake hands, and the answer is ceil(log2(n)), ceil(x) being the least integer that is greater than or equal to x.
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).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
The emulation is this messed up in JPC-RR? RIP AGI TASes.
Regarding this game: It's too bad the slot machine can't be manipulated very well. I was hoping that it would have been possible to manipulate easily; it's the one thing that would have made this TAS impressive from a technical standpoint. (Is it possible to type and enter something that could manipulate RNG as well?)
About adventure games done fast: Even though I love these adventure games, I am not a fan of adventure games run at incomprehensible speeds. I would much prefer if there was enough time between "key actions" for the viewer to at least have an idea what is going on. Even I can barely keep up, despite having played this game many times before.
Anyway, I would normally have liked a TAS of this game to be published, but, if the emulation problems cannot be fixed, I think it would be better not to publish.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
But if $$a$$ is not a real number then bringing $$\mathrm{e}^{a t}$$ into the $$\Re$$ isn't allowed. But we get the same answer. So if we try to compute the integral in this way it's an abuse of notation.
Instead of using Re(eiωx) for cos(ωx), use (1/2)(eiωx+e-iωx) instead. (This follows from Euler's formula.) Then it will work out to be the same answer. This way, we do not need to worry about abuse of notation; it works when a is complex. In fact, it now works even if ω is complex. (Euler's formula holds for complex values as well.)
By the way, the image you uploaded isn't visible in imgur without going into expand mode. It may be because the background color is regarded as transparent, even though it should be white. Edit: The image is directly linked now, which solves the problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Bobo the King wrote:
What do the variables there represent?
The variables are expected values.
More specifically, EABCD, EAABC, EAABB, and EAAAB are the expected number of turns required to go from state ABCD, AABC, AABB, AAAB (respectively) to state AAAA. The following relations apply to these values:
EABCD=1+EAABC,
EAABC=1+(6/12)EAABC+(4/12)EAAAB+(2/12)EAABB,
EAABB=1+(4/12)EAABB+(8/12)EAAAB,
EAAAB=1+(6/12)EAAAB+(3/12)EAABB+(3/12)(0).
Then one can solve this to get EAAAB=5.5, EAABB=7, EAABC=8, EABCD=9. The expected number of turns to go from ABCD to AAAA is 9.
That's what the Riddler is trying to say.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
OmnipotentEntity wrote:
And the answer is yes. Because we know that lim(x->0) -x / x3 = -infinity. So we just need to set g(x) to -x and we set 1/ln(f(x)) = x3 which gives f(x) = exp(x-3)
That seems to indeed work.
The function f(x) given above does not have a (two-sided) limit as x->0.
The one I came up with was f(x)=exp(-x-4), g(x)=x2, and a=0. In this case, f(x), g(x) and f(x)g(x) all have the (two-sided) limit 0 as x->0.
Bobo the King wrote:
Riddles were super easy this week.
Sure was. This was the easiest since a very long time ago, if ever.
Both Riddler problems are pretty much known to every math enthusiast (the first is Nim, the second is one of the characterizations of the Fibonacci sequence). As if that wasn't enough, Riddler Express ended up linking to the Nim Wikipedia page which tells you exactly how to solve it.
The Riddler Classic generalization is a little more interesting (the frog can jump up to n steps, instead of just 2), but anyone can just write a computer program (or even just use an Excel spreadsheet) to figure it out. The most interesting thing I found out was concerning the growth rate of each sequence depending on n.
For n=2, the growth rate is exponential with a base of (1+sqrt(5))/2 (the golden ratio); this is a known property of the Fibonacci sequence. As n grows larger, the base grows; however, the limit of the bases is 2 as n goes to infinity (if you sum all past terms, you get the powers of 2). The base is just the largest real root of xn-xn-1-xn-2-...-x-1, or in other words the largest real solution to (x-2)xn=-1. From this equation, it is clear that x must be less than 2. Approximate bases are as follows:
n=2: 1.61803
n=3: 1.83929
n=4: 1.92756
n=5: 1.96595
n=6: 1.98358
n=7: 1.99196
n=8: 1.99603
n=9: 1.99803
n=10: 1.99902
Edit: Changed "exponent" to "base". I still say stupid stuff sometimes.
Edit 2: Fixed f(x).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Bobo the King wrote:
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.
The game theory problems I was referring to as difficult are mostly games that involve payoff matrices; those games involve players making their choices at the same time. Since the decision to spin the wheel on the Price is Right is sequential (P1 chooses first, then P2 uses prior information to choose, then P3), this problem is easier to understand conceptually than those involving payoff matrices. It's just a matter of working backwards (find P3's strategy, then P2's, then P1's).
The optimal strategy for spinning the wheel has already been discussed on many sites so you can just look it up if you want to see what it is.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
The prisoner and levers problem lives on, even a week later! Steve Schaefer, a commenter for this page, posted a better strategy in the comment section. I'm not sure if anyone else found this out, because neither us, nor Hector Pefo, nor Riddler, nor Car Talk arrived at this strategy. The strategy gives a way for the 99 non-counting prisoners to flip the tally lever only once, while ensuring the counter does not overcount because of some random starting configuration. It is as follows:
Call the levers A and B (A is the tally lever, B the dummy lever). Prisoners 2 through 100 each do the following:
- If lever A has not been flipped by the prisoner yet, and the prisoner saw lever A in the up position any time previously, and lever A is down, flip lever A up. Otherwise, flip lever B.
Prisoner 1 does the following:
- Keep a count starting from 0. If lever A is down, flip lever A up. If lever A is up and Prisoner 1 flipped lever A down on the previous (one before) visit, flip lever A down and add one to the count. Otherwise, flip lever A down and don't add anything. When the count reaches 99, declare that all of the prisoners have been to the room.
I ran the expected value calculation and it comes out to be 11096.054 visits, a 45.8% improvement over the other strategy's value of 20476.663.
It may even be possible to improve with a different Prisoner 1 strategy of flipping the tally lever (but always flipping the tally lever already seems quite reasonable).
Flip wrote:
...
...
..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
The result of racing ostwx isn't necessarily twx; it could be wtx, stx, ost, xot, ...
(This would of course decide the second and third places.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.
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:
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
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).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
OmnipotentEntity wrote:
Playing around with it, for x negative, it seems like any C will do, if you allow complex values in intermediate steps. In fact, if you allow complex values, any C will do for any value of x and you'll get back your (1 + sqrt(4x + 1))/2. Except of course for the special case where x = 0 and C = 0.
It's best to think of this as a fixed-point iteration problem on the function f(y)=sqrt(y+X), that is, as I described above already:
a0=C, ai=sqrt(ai-1+X), limit as i goes to infinity.
Also, to avoid confusion, I will only deal with real numbers.
Graphically, on the yz-plane the we draw both the line z=y and the curve z=sqrt(y+X). Fixed-point iteration works as thus:
@ Start from some point (C,C) on the line z=y.
@ If the curve z=sqrt(y+X) lies above this point, go up to the curve, then right to the line z=y to get the next point.
@ If the curve z=sqrt(y+X) lies below this point, go down to the curve, then left to the line z=y to get the next point.
@ Repeat this over and over and see where it converges (if it does).
If it does converge, it does so at a fixed point (that is, a point where f(y)=y).
Case 1: X>0
There is one fixed point at y=(1+sqrt(4X+1))/2.
From the graph, every value of C>(1+sqrt(4X+1))/2 decreases until it converges to (1+sqrt(4X+1))/2 and every value of -X<=C<(1+sqrt(4X+1))/2 increases until it converges to (1+sqrt(4X+1))/2.
Case 2: -1/4 <= X <= 0
There are two fixed points, one at y=(1+sqrt(4X+1))/2 and one at y=(1-sqrt(4X+1))/2 (unless X=-1/4, in which case they are the same y=1/2).
From the graph, every value of C>(1+sqrt(4X+1))/2 decreases until it converges to (1+sqrt(4X+1))/2 and every value of (1-sqrt(4X+1))/2<C<(1+sqrt(4X+1))/2 increases until it converges to (1+sqrt(4X+1))/2. If C=(1-sqrt(4X+1))/2, then it just remains (1-sqrt(4X+1))/2. Finally, if C<(1-sqrt(4X+1))/2, then it decreases until it is less than -X, in which case it is no longer defined.
Case 3: X<-1/4
There are no fixed points, and every value of C decreases until it is less than -X, in which case it is no longer defined.
----
By the way, for the case X=0, C=0 does converge, it just converges to 0 rather than 1. It is positive C that converges to 1, and negative C isn't even defined when you take the square root.
Bobo the King wrote:
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 2n people I got 1 in C(2n,n), which for n=50 matches your guess for 100 people. Since I cannot come up with a reason why anything else is clearly better, I'll just assume that this method is optimal.
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.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Warp wrote:
OmnipotentEntity wrote:
You get a similar oxymoron if you substitute x = 0: 1 = sqrt(0 + sqrt(0 + ...)).
Does this mean that you can only say
sqrt(x+sqrt(x+sqrt(x+sqrt(...)))) = (1 + sqrt(4x + 1)) / 2 , x > 0
In other words, the equality does not hold for x <= 0?
If yes, at which point of the proof does one have to assert that x>0?
What does sqrt(x+sqrt(x+sqrt(x+sqrt(...)))) mean exactly? If you mean
a0=C, ai=sqrt(x+ai-1), limit as i goes to infinity,
then there are values of C for which ai converges to (1 + sqrt(4x + 1)) / 2 for any x>=-1/4.
Masterjun wrote:
FractalFusion wrote:
Note that the strategies above are optimal but it may be possible that they aren't unique, though my guess is that they are unique.
A quick question:
Does optimal strategy in this context mean that there are no other strategies against it with an expected win rate of over 50%? Or am I misinterpreting this?
An optimal strategy is one that ensures the highest reward assuming that the opponent knows exactly what your strategy is.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I'll talk about how I arrived at the values in my solution.
1-1:
As Bobo the King already mentioned, choosing double scissors dominates choosing scissors when a player already has one win. So we can remove scissors. This leaves standard rock-paper-scissors (with double scissors in place of scissors). So both players play rock/paper/double scissors each with 1/3 chance, and both players have a 1/2 chance of winning the match.
1-0:
We call the player with one win "P1" and the other player "P2". Let σ be the chance that P1 wins the match and δ the chance that P2 wins the match. Note that σ+δ=1, and that 1/4<δ<1/2 and 1/2<σ<3/4. I explain the core theory below:
The expected reward (read: probability of winning the match) for P1 for each strategy is shown in the table below:
(R=rock, P=paper, S=scissors, DS=double scissors)
P2
d e f g
R P S DS
---------------
P1 a R | σ 0.5 1 1
b P | 1 σ 0 0.5
c DS| 0.5 1 1 σ
(Remember that for P1, choosing double scissors dominates choosing scissors, so we don't need a row for scissors.)
To simplify things for later, we switch the table to the expected reward for P2 (transpose and subtract from 1) for each strategy:
P1
a b c
R P DS
-----------
P2 d R | δ 0 0.5
e P | 0.5 δ 0
f S | 0 1 0
g DS| 0 0.5 δ
Now a,b,c are the probabilities for each P1 choice and d,e,f,g the probabilities for each P2 choice. Together, the expected reward for P2 is:
(δa+0.5c)d + (0.5a+δb)e + bf + (0.5b+δc)g.
P1's strategy:
P1's goal is to minimax this value; that is, find:
min(abc)max(defg) (δa+0.5c)d + (0.5a+δb)e + bf + (0.5b+δc)g.
Note: I use "min(abc)" to mean: Minimize over all reals a,b,c from 0 to 1 satisfying a+b+c=1. Similarly with "max(defg)".
P2 maxes this quantity by setting equal to 1 the variable d,e,f,g whose coefficient is the largest. So we want to minimize the maximum of δa+0.5c, 0.5a+δb, b, 0.5b+δc. To make things short, let's exclude the coefficient of g (0.5b+δc) and minimize max{δa+0.5c, 0.5a+δb, b}. You can check that the minimum occurs when δa+0.5c = 0.5a+δb = b with a+b+c=1. Solving gives a minimum of b=1/(4δ2-6δ+5).
However, the minimax is actually P2's probability of winning the match. So the minimum should also be b=δ. Therefore δ=1/(4δ2-6δ+5) → 4δ3-6δ2+5δ-1=0. There is only one real solution, and that is (in WolframAlpha's plaintext)
δ = 1/2 + 1/2 ((1/2 (sqrt(177) - 9))^(1/3)/3^(2/3) - 2 (2/(3 (sqrt(177) - 9)))^(1/3))
or about 0.2733. This gives a=2δ-2δ2 (~0.3972), b=δ (~0.2733), c=2δ-4δ2+4δ3 (~0.3295).
Note I excluded g earlier, so we have to account for the extra 0.5b+δc. But from above, it is clear that the minimax is at least δ. Plugging in a,b,c from above gives 0.5b+δc = δ(0.5+c) < δ, and so it follows that the minimax is indeed δ.
P2's strategy:
We can rewrite the expected reward for P2 as:
(δd+0.5e)a + (δe+f+0.5g)b + (0.5d+δg)c.
P2's goal is to maximin this value; that is, find:
max(defg)min(abc) (δd+0.5e)a + (δe+f+0.5g)b + (0.5d+δg)c.
But since the maximin is equal to the minimax, we know that there is some value of d,e,f,g that satisfies δd+0.5e = δe+f+0.5g = 0.5d+δg = δ. You can check that d=2δ (~0.5466), e=2δ-4δ2 (~0.2478), f=δ-2δ2+4δ3 (~0.2056), g=0 does the trick.
0-0:
Clearly from symmetry, both players have a 1/2 chance of winning the match. We still need to find the strategies. Call the players P1 and P2 again and consider the expected reward for P1:
P2
e f g h
R P S DS
---------------
P1 a R | 0.5 δ σ σ
b P | σ 0.5 0 δ
c S | δ 1 0.5 δ
d DS| δ σ σ 0.5
For P1's strategy, we want to find
max(abcd)min(efgh) (0.5a+σb+δc+δd)e + (δa+0.5b+c+σd)f + (σa+0.5c+σd)g + (σa+δb+δc+0.5d)h.
But since we know that the maximin has to be 1/2, just check that a=1/(3-4δ) (~0.5244), b=c=(1-2δ)/(3-4δ) (~0.2378), d=0 satisfies this. By symmetry, P2 has the same strategy.
----------
I verified using http://math.ucla.edu/~tom/gamesolve (a solver for these types of problems) that the values I have here are correct. Note that the strategies above are optimal but it may be possible that they aren't unique, though my guess is that they are unique.
Bobo the King wrote:
These values are (almost) stable in my Excel spreadsheet, although it appears that they creep away from the saddle point, even with a very low step size. Either my gradient search algorithm is inherently unstable or I've entered it incorrectly somehow.
I'm not sure how you are trying to determine whether they are stable. In any case, you can't use derivatives because minimax is a linear optimization problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Bobo the King wrote:
It always frustrates me when I have more trouble with the Riddler Express puzzle than the Riddler Classic puzzle. Yet that's where I am this week. In about 30 minutes' work in Excel, I found that the number of times needed to flip the coins to correctly identify which one has been doctored is between 130 and 140 (I have the exact number, but I'll keep this post spoiler-free).
The Riddler Classic problem is a straightforward computational question. I got 134.
The Riddler Express problem is game theory, which really doesn't belong in Riddler Express unless it is a baby question. So I don't blame anyone for thinking that Riddler Express is harder than Riddler Classic this week. As a sample of how complicated game theory can get, see the solution to this Riddler problem.
This one isn't nearly as hard because it has far fewer variables. But it still doesn't belong in Riddler Express. I managed to work out the strategies. Let δ be the real solution to 4x3-6x2+5x-1=0. (δ~0.2733)
1-1:
Each player: 1/3 rock, 1/3 paper, 1/3 double scissors → 1/2 chance of winning the match.
1-0:
Player with one win: 2δ-2δ2 (~0.3972) rock, δ (~0.2733) paper, 2δ-4δ2+4δ3 (~0.3295) double scissors → 1-δ (~0.7267) chance of winning the match.
Player with no wins: 2δ (~0.5466) rock, 2δ-4δ2 (~0.2478) paper, δ-2δ2+4δ3 (~0.2056) scissors → δ (~0.2733) chance of winning the match.
0-0:
Each player: 1/(3-4δ) (~0.5244) rock, (1-2δ)/(3-4δ) (~0.2378) paper, (1-2δ)/(3-4δ) (~0.2378) scissors → 1/2 chance of winning the match.
The strategies for 1-0 and 0-0 are all based on minimaxing the expected reward matrix, which takes too much time for me to cover right now. I might write up details on how to find these values later.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
r57shell wrote:
FractalFusion wrote:
and the integer-valued functions f(x)=floor(n/x) and g(x)=floor(x+n/x).
Just wanna confirm that they are both Z->Z (integer -> integer),
Yeah, that's what I meant. Apparently I forgot that "S-valued function" does not mean "function from S to S".
r57shell wrote:
FractalFusion wrote:
Let C=min(g(x)). The minimum d such that g(d)<g(d+1) occurs at ceil(α)-1, where α is the larger real solution to x+n/x=C+1.
This is out of space. This is where rigorous proof ends.
If here would be also proof, that it is indeed occurs at ceil(a) -> it will be truly rigorous.
Proof: gr(x)=x+n/x goes to infinity as x→∞. Since C+1=min(g(x)+1)≥min(gr(x)), there exists at least one solution to gr(x)=C+1. There are two solutions for x; one in (0,sqrt(n)) and one in (sqrt(n),∞) so we α to be the one in (sqrt(n),∞) (the larger one).
Since gr(α)=C+1 and gr(x)=x+n/x is increasing on ［sqrt(n),∞), it follows that gr(ceil(α))≥C+1, so g(ceil(α))≥C+1. If ceil(α)-1≥sqrt(n), then gr(ceil(α)-1)<C+1, and so g(ceil(α)-1)=C. (If not, then ceil(α)-1=floor(sqrt(n)), and it must follow that g(ceil(α)-1)=C; otherwise min(g(x))=C+1, contradicting that the minimum is C.) Therefore the minimum d such that g(d)<g(d+1) is d=ceil(α)-1.
OmnipotentEntity: Yes, that is true (if g were to have a domain of ℝ). However, there are a couple reasons I would like g to have a domain of ℤ in the proof: (1) If n=k(k+1), min(g(x))=min(floor(x+n/x)) would not have the same value if it were defined with a domain of ℝ as it would with a domain of ℤ. (2) I don't have to say something like "min over ℤ" every time.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
(Reposting an updated version.)
I've got a formula for a(n).
Note that floor(x) is the greatest integer less than or equal to x, ceil(x) is the least integer greater than or equal to x.
Let k=floor(sqrt(n)). If k2 ≤ n < k(k+1), then:
a(n) = ceil( ［2k+1+sqrt((2k+1)2-4n)］/2 ) - 1. (*)
If k(k+1) ≤ n < (k+1)2, then:
a(n) = ceil( ［2k+2+sqrt((2k+2)2-4n)］/2 ) - 1. (**)
-------------
By plugging in n=k(k+1)-1, n=k2 into (*) and n=(k+1)2-1, n=k(k+1) into (**), we get the following bounds:
For (*): k ≤ a(n) ≤ ceil( ［2k+1+sqrt(4k+1)］/2 ) - 1 = ceil( k+0.5+sqrt(k+0.25) ) - 1.
For (**): k+1 ≤ a(n) ≤ ceil( ［2k+2+sqrt(4k+4)］/2 ) - 1 = ceil( k+1+sqrt(k+1) ) - 1.
Since k=floor(sqrt(n)), this confirms that the lower bound grows as sqrt(n) and the upper bound grows as sqrt(n)+sqrt(sqrt(n)). OmnipotentEntity has the right guess for the upper bound.
-------------
@r57shell: Since you wanted a rigorous proof, I will try to provide one. Can't guarantee that you will be satisfied though.
Fix integer n>0. I will use the real-valued functions fr(x)=n/x and gr(x)=x+n/x, and the integer-valued functions f(x)=floor(n/x) and g(x)=floor(x+n/x).
We want to find minimum d such that f(d)=f(d+1). I claim that this is the minimum d such that g(d)<g(d+1). Indeed, g(x)=x+f(x), and so g(d+1)-g(d)=1+f(d+1)-f(d). Note that, since fr(x)=n/x is a decreasing function on (0,∞), f(x) is a weakly decreasing (non-increasing) function ; that is, f(d+1)-f(d)≤0. So g(d+1)-g(d)≤1.
This gives: g(d)<g(d+1) ⇔ g(d+1)-g(d)=1 ⇔ f(d+1)-f(d)=0 ⇔ f(d)=f(d+1). This proves the claim.
Now let k=floor(sqrt(x)), so that k2≤x<(k+1)2. I claim that the minimum of g(x) occurs at x=k or x=k+1 (not necessarily exclusively). This is because gr(x)=x+n/x is decreasing on (0,sqrt(n)］ and increasing on ［sqrt(n),∞) (by calculus), which mean g(x) is weakly decreasing up to x=k and weakly increasing from x=k+1 onward. So the claim holds.
Let C=min(g(x)). The minimum d such that g(d)<g(d+1) occurs at ceil(α)-1, where α is the larger real solution to x+n/x=C+1.
Two cases:
Case 1: k2≤x<k(k+1).
C=g(k)=g(k+1)=2k. Solving x+n/x=2k+1 gives α=［2k+1+sqrt((2k+1)2-4n)］/2, and so the minimum d occurs at ceil(［2k+1+sqrt((2k+1)2-4n)］/2)-1, which proves (*).
Case 2: k(k+1)≤x<(k+1)2.
g(k+1)=2k+1 and g(k)≥2k+1, so C=2k+1. Solving x+n/x=2k+2 gives α=［2k+2+sqrt((2k+2)2-4n)］/2, and so the minimum d occurs at ceil(［2k+2+sqrt((2k+2)2-4n)］/2)-1, which proves (**).
QED
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.
There is one fixed point at y=(1+sqrt(4X+1))/2.
From the graph, every value of C>(1+sqrt(4X+1))/2 decreases until it converges to (1+sqrt(4X+1))/2 and every value of -X<=C<(1+sqrt(4X+1))/2 increases until it converges to (1+sqrt(4X+1))/2.
Case 2: -1/4 <= X <= 0
There are two fixed points, one at y=(1+sqrt(4X+1))/2 and one at y=(1-sqrt(4X+1))/2 (unless X=-1/4, in which case they are the same y=1/2).
From the graph, every value of C>(1+sqrt(4X+1))/2 decreases until it converges to (1+sqrt(4X+1))/2 and every value of (1-sqrt(4X+1))/2<C<(1+sqrt(4X+1))/2 increases until it converges to (1+sqrt(4X+1))/2. If C=(1-sqrt(4X+1))/2, then it just remains (1-sqrt(4X+1))/2. Finally, if C<(1-sqrt(4X+1))/2, then it decreases until it is less than -X, in which case it is no longer defined.
Case 3: X<-1/4
There are no fixed points, and every value of C decreases until it is less than -X, in which case it is no longer defined.
----
By the way, for the case X=0, C=0 does converge, it just converges to 0 rather than 1. It is positive C that converges to 1, and negative C isn't even defined when you take the square root.
