Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
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.
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.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
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).
Meanwhile, I'm making little headway into the Riddler Express puzzle. My first finding was that when the match is tied at 1-1, there is no incentive to play scissors since double-scissors are objectively more powerful. Also, based on the symmetry of the game, the probability of winning a match at 1-1 is obviously 1/2.
But then I had to extrapolate backwards to an uneven match at 0-1 (or 1-0, depending on your perspective). I wrote the probability of winning the entire match as a bunch of terms based on the relative probabilities for each player using rock, paper, scissors, or double-scissors. There are 7 variables (recall that the player up in the match 1-0 has no incentive to choose scissors) and since the probabilities of playing something must sum to 1 for each player, there are 5 degrees of freedom.
So I wrote out the probability that the player down 0-1 wins the match. I'll let someone else write it symbolically, but this is 1/2 times the probability that they win with paper, rock, or double-scissors (1/2 because they still have to win the final round) plus the probability that they win with scissors (instant win), all divided by the same terms plus the probability that their opponent wins. I called the terms in the numerator W (for "win") and the added terms in the denominator L (for "lose").
Next, I took some derivatives to indicate whether the probability of winning is helped or hurt by throwing more of a particular hand. Again, I'll avoid writing this explicitly, but for example, the derivative of the probability of winning with respect to the rate at which the player throws paper is proportional 1/2 times the rate at which their opponent throws rock times L minus the rate at which their opponent throws double-scissors times W. You can extrapolate this pattern outward to obtain similar expressions for all other variables. These aren't quite derivatives (they omit the denominator squared in the quotient rule) but they must all be zero when an optimum strategy is obtained. I called these values "pressures" since they indicate whether a variable should increase or decrease.
Basically, I took my original values, then added to them some small constant times the pressures I calculated minus the average pressure. I iterated this process, hoping to home in on optimal strategies for both players.
It didn't work. For every initial condition I plug in, I end up with negative probabilities or probabilities that escape to infinity. I also tried a search based on fitting a paraboloid to the probability function, then finding the minimum of this paraboloid. This method is similar to Newton's method for finding the zeroes of a function, except it's a multivariable version. That took a long time to set up and was a complete mess.
So I'm stuck.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
OmnipotentEntity wrote:
The upper bound of [sqrt(n) +ln(n)] does not hold.
Sure it does! Just for n>3. Bounds like this are constructed all the time, such as in Goldbach's conjecture: every even number greater than 2 can be written as the sum of two prime numbers.
I wouldn't put too much stock into a minor violation early on when it looks like sqrt(n) + ln(n) does a fantastic job of not only providing an upper bound, but apparently a pretty good supremum as well.
Edit: I forgot Goldbach's conjecture. I really have to remember to check Wikipedia, then post...
Edit 2: Concerning this part of your post...
OmnipotentEntity wrote:
The upper bound of ln(x) does not hold.
What's being graphed here? Is the blue area x(n) while the green line is sqrt(n) + ln(n)? If so, then I misinterpreted this graph and sqrt(n) + ln(n) is, in fact, not an upper bound.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
r57shell wrote:
Maybe someone of you can solve it:
floor(n/x) == floor(n/(x+1))
for fixed positive n, find minimum positive x. in whole integers. (both n and x)
I don't have an answer.
I'm interested only in rigorous proof.
Numerical solution is easy.
I didn't understand this question until OmnipotentEntity's post, which included a link to the relevant OEIS sequence. Allow me to clarify the question through a few examples.
We'll start with n=1:
x = 1: ⌊1/1⌋ = 1
x = 2: ⌊1/2⌋ = 0
x = 3: ⌊1/3⌋ = 0
and so we conclude that x=2 is the minimum integer we seek, since ⌊1/2⌋ = ⌊1/3⌋.
Here's n=2:
x = 1: ⌊2/1⌋ = 2
x = 2: ⌊2/2⌋ = 1
x = 3: ⌊2/3⌋ = 0
x = 4: ⌊2/4⌋ = 0
So for n = 2, x = 3.
Now n=3:
x = 1: ⌊3/1⌋ = 3
x = 2: ⌊3/2⌋ = 1
x = 3: ⌊3/3⌋ = 1
and therefore, when n = 3, x = 2.
One more time with a larger n. I notice the sequence has an interesting jump when n=90, so let's do that:
...
x = 10: ⌊90/10⌋ = 9
x = 11: ⌊90/11⌋ = 8
x = 12: ⌊90/12⌋ = 7
x = 13: ⌊90/13⌋ = 6
x = 14: ⌊90/14⌋ = 6
so for n = 90, x = 13.
I hope that helps others bite into this problem.
Edit: Typo. When n=2, x=3, not 4.
Edit 2: By the way, for those who haven't noticed or bothered to look, OEIS produces graphs of its sequences. Here's the graph for this sequence. I'm pretty sure the graph is closely approximated by sqrt(n) (which, in just 30 seconds of thought, kind of makes "intuitive sense" to me). I'd begin my investigation by plotting x(n) - sqrt(n) versus n; i.e., I'd plot the residuals and look for patterns. At the very least, I'm confident we can put lower- and upper-bounds on x(n).
I've seen that table before. If you look carefully, there are terms of "I" sprinkled throughout. Is this the imaginary unit or is it some other constant? If it is the imaginary unit, there must be some wonderful cancellation in here.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Warp wrote:
sin(18°) is famous in that its precise value can be calculated geometrically. If somebody hasn't seen or done it before, perhaps they could give a try.
Okay, I gave it a shot, though I did it trigonometrically instead of geometrically. I could perhaps try to finagle this into a geometric argument.
In any case, here's my proof, which is sloppy, uses inconsistent notation, and I haven't checked its accuracy:
e^(i*18) = cos(18) + i*sin(18)
e^(i*18)^5 = e^(i*18*5) = e^(i*90) = i = (cos(18) + i*sin(18))^5
i = c^5 + 5*i*c^4*s - 10*c^3*s^2 - 10i*c^2*s^3 + 5*c*s^4 + i*s^5
c^5 - 10*c^3*s^2 + 5*c*s^4 = 0
5*c^4*s - 10*c^2*s^3 + s^5 = 1
(1-s^2)^2 - 10*(1-s^2)*s^2 + 5*s^4 = 0
1 - 2s^2 + s^4 - 10s^2 + 10s^4 + 5s^4 = 0
16s^4 - 12s^2 + 1 = 0
s^2 = (6 +/- sqrt(36 - 16))/16 = (3 +/- sqrt(5))/8
sin(18) = sqrt(3 - sqrt(5)/8)
It's late here.
Edit: I'm right!
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
BrunoVisnadi wrote:
Bobo the King wrote:
Okay, to be explicit about what has been pointed out above, the players are not allowed to communicate during the guessing phase except through their choice of guess/pass. This is suddenly more interesting.
I don't think this kind of communication is allowed. And it is still interesting, because it is possible to get higher chances without it:
First, lets name the friends: 1, 2, 3, 4, 5, 6 and 7.
Strategy:
1) If you see exactly 3 hats of each color, pass.
2) If you see exactly 2 hats of a specific color, and your number is bigger than the number of these 2 people, guess you have this color. If your number is smaller, pass.
This guarantees we will win every 3/4 scenario - which has (35)/(2^6), or more than 54% chance of happening!
In a 2/5 scenario, we will certainly lose if person 7 is on the 'team' with 5 hats, due to rule 2). But we can win otherwise. Consider this rule:
3) If you see exactly one hat of a specific color, and you aren't number 7, pass. If you are number 7, guess you have that color.
Now we won every 2/5 situation in which person 7 is in the 'team' with 2 hats.
Lastly, in a 1/6 scenario, we will lose if 7 is in the team with 6 hats. But if he isn't, we will win, because whoever is in this team will pass, and we can have this rule:
4) If you only see hats of one color, guess you have the other color.
In a 0/7 scenario, we always lose.
So this gives us the following winning chance:
(35)/(2^6) + (3)/(2^5) + 1/(2^6) = 21/2^5 or 65.625%
Yeah, I'm starting to see it now! I've just been torn between trying to further my own understanding of the problem, clarifying the rules, and finding an error in ShadowWraith's method. My thought process was undirected.
Maybe we can come up with a Bayesian analysis of this problem along the lines of P(my hat is white|I see six black hats) etc.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
ShadowWraith wrote:
Then my solution works 100% of the time. ^^
Not if person 7 passes. Person 7 should always guess, giving you a 1/2^7 chance of losing. I'm still trying to wrap my head around this, though. One thing that is unclear from the problem statement is whether everyone is asked their hat color in a specific order. That is, does person 1 know they'll go first and person 2 will go second and so on?
Edit: I think it's actually 1/2^7, based on this being the number of ways to administer the hats and exactly one of them resulting in a failure.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Okay, to be explicit about what has been pointed out above, the players are not allowed to communicate during the guessing phase except through their choice of guess/pass. This is suddenly more interesting.
Edit: ... Or is it? Now I'm not sure again. Isn't the first guess guaranteed to be a 50/50 chance? Subsequent guesses should only reduce the probability of winning. I'm struggling to come up with a way to communicate hat colors using only passes. It's got to be related to how many people pass before the first guess.
This suddenly reminds me of the sultan's dowry problem.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Can I request a hint on this week's Riddler challenge? The Classic Challenge seems really simple and stupid to me. Because the hat colors are assigned randomly, viewing your friends' hats offers you no information and there is no incentive to have more than one person guess. Therefore, my strategy would be to tell my friends, "Everyone say 'pass' except me and I'll guess randomly," for a 50 percent chance at winning the vacation.
I've read through the problem statement four or five times and feel like I must be missing something. This is too easy, especially compared to last week's sphere packing problem.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
In an attempt to inject some positivity into this thread, let's all take a moment to acknowledge what an outstanding run this is (as usual) by HappyLee. I don't think anyone in this thread has said that this run is sloppy or unentertaining on its own. It really is a fantastic piece by itself, even if it's not worthy of publication.
I especially like this run for the way it forces us to examine our publication rules. I wrote in my Beetle Mania submission text, "I want this run to make people think about-- but not challenge-- the submission criteria. Make sense?" Ever since the creation of the Vault, I haven't had much reason to do any botting because runs with high optimization and terrible entertainment are easily sequestered there. HappyLee's run has opened up extensive discussion about what runs should and shouldn't be published and that is a feat in and of itself! Everyone loves the flashy runs of popular games and most of the time we all come to a pretty quick consensus about whether a movie is worthy of publication, but I have a sneaking admiration for submissions that push our judging criteria to their limits. Such movies are rare, they're good for the site, and they are destined for infamy, regardless of whether they're published. Maybe my runs contributed in small part to the creation of the Vault and maybe HappyLee's run will eventually grow the site in some other way.
I also think Nach deserves some appreciation. As others have said, this was not an easy decision and Nach was left in an unenviable position. I hope that no one believes he made his decision without putting a lot of thought into it. True, many here think that the thought was misplaced, but no one should think that he just quickly looked over the run once or twice, said, "Screw it!" and rejected it.
My own concern regarding the run is that it most differentiates itself from the NTSC run with the "fall into the floor" glitch. This glitch is used in 8-2 and only saves about 0.4 seconds by Nach's calculation, which isn't even where most of the improvement comes from. I won't say that the run didn't deserve publication because of that, but it definitely makes one wonder whether there's really enough new here to warrant side-by-side publication with a run that's nearly identical in content and timing.
But I digress. Great job by both HappyLee and Nach! This has been very entertaining on all fronts!
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
I believe your error lies where you say, "So the true proportion of 2s in the new sequence is x*(1/3) + (1-x)*(1/4)." Because the strings 3332 and 332 are not of equal length, you can't just average the ratios together to find the the combined ratio. At least I think that's correct.
You're right. I used wrong logic to declare that I can just average the ratios together.
Actually, there is an even more fundamental problem in that I never bothered to find out if it converges at all. Even if the strings were of equal length, it would be flawed to assume that the ratio converges. For example, the ratio of 0s to 1s in 01010011000011110000000011111111... doesn't converge, even though if you looked only up to the 2nd, 4th, 8th, 16th, ... , the ratio is always 1:1.
But, assuming that the ratio of 2s to 3s in the sequence 333233323332332... does converge, we can calculate the ratio. If, at some point of the sequence, there are x 2s and y 3s, then the current ratio is x:y. After replacing 2→332 and 3→3332, the new ratio is x+y:2x+3y. Since we assumed that the ratio converges, then we can take as the limit x:y = x+y:2x+3y. Letting y=1 and x=α, we get:
α:1 = α+1:2α+3
α(2α+3) = α+1
2α2+2α-1 = 0
α = (-1+sqrt(3))/2.
So, assuming that it converges, the ratio of 2s to 3s is (-1+sqrt(3))/2:1 = -1+sqrt(3):2 ≈ 0.366:1, so the ratio of 3s to 2s is 2:-1+sqrt(3) = 1+sqrt(3):1 ≈ 2.732:1. (The proportion of 2s is 2-sqrt(3) ≈ 0.268; the proportion of 3s is sqrt(3)-1 ≈ 0.732).
Proving that it does converge is harder (and judging from past Riddler posts, I don't think Riddler cares). It would go something like this (won't go into the details):
1) If there are x 2s up to the nth symbol, then by replacing 2→332 and 3→3332, there are n 2s up to the (4n-x)th symbol.
2) The ratio n/(4n-x) approximates β=2-sqrt(3) better than x/n does. The key is that (x-βn)*(x-(2+sqrt(3))n) = x2-4xn+n2 is a fixed number (it gives the same value if you replace x→n and n→4n-x).
3) So repeatedly doing the replacement 2→332 and 3→3332 causes x/n to converge to β, for all starting n.
4) Only the numbers n such that the nth symbol is 2 can be targeted directly by 2→332 and 3→3332, but every n is within 3 of such a number.
5) Limits then show that the error between x/n and β goes to 0 as n goes to infinity.
As an aside, x is exactly the integer part of βn (that is, floor(βn)) for all n, and the nth symbol is 2 if and only if the integer part of βn is one more than the integer part of β(n-1).
Edit: Fixed another thing where I switched the roles of 2s and 3s.
Correct! Below is the write-up I had on the problem, which is a similar outline of the proof:
Consider an arbitrary string of length N somewhere within the sequence. Let p be the fraction of 3s in the string and q be the fraction of 2s in the string. (Note for convenience, p rhymes with 3 and q rhymes with 2!)
For example, we might have the string
3332
which has N = 4, p = 3/4, and q = 1/4. Much later in the sequence, this will necessarily produce the string
333233323332332
which has N' = N*p*4 + N*q*3 = 15, p' = (p*3 + q*2)/(p*4 + q*3) = 11/15, and q' = 1/(p*4 + q*3) = 4/15. Note that because the original string is "oversaturated" with 3s, p' < p, driving the long-term ratio p downward (and q upward, correspondingly). A similar trial can be done with the initial string 332, which shows that p' > p, driving the long-term ratio p upward. I'll omit that trial, but the result is that if we can find a unique fixed point for p between p = 2/3 and p = 3/4, the ratio for any string will converge to this fixed point.
The fixed point satisfies p' = p and q' = q, giving us two equations in two variables:
p = (p*3 + q*2)/(p*4 + q*3)
q = 1/(p*4 + q*3)
Many lines of algebra reduces this to a cubic equation in p:
-2p^3 - 3p^2 + 6p - 2 = 0
This has a root of 2p-1, which corresponds to p=1/2. This lies outside the range we're looking for (2/3 < p < 3/4), so factoring it out produces a quadratic equation:
-p^2 - 2p + 2 = 0
This has roots of p = -1 +/- sqrt(3), but again, we omit the root p = -1 - sqrt(3) because p is necessarily positive, leaving p = sqrt(3) - 1 and correspondingly q = 2 - sqrt(3) (easily derived from p + q = 1). Numerically, our values are p = 0.73205 and q = 0.26795. As required, 2/3 < p < 3/4, so all strings must converge to this value of p in the long term.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
r57shell wrote:
FractalFusion wrote:
We see that 2 is a root of z3+3z-14, and it factors as (z-2)(z2+2z+7).
Solved same way. But it's not obvisous that root is 2 unless you know that answer should be simple.
It's not so bad with the rational root theorem. With the theorem, you know you only need to test +1, +2, +7, and +14, then follow up with some polynomial division. I bring this up because I happened to use a very similar process at a crucial step in the Riddler puzzle I mentioned above...
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
Did anyone else get it? I'm looking at you, FractalFusion.
How the sequence is defined (borrowing from Riddler):
The sequence has the property that, if you replace every 3 with 3332 and 2 with 332, the resulting sequence will be the same.
Let x be the long-term proportion of 2s in the sequence. Replace every 3 with 3332 and 2 with 332. If we look at only the 2s being replaced with 332, the proportion of 2s in the new sequence is 1/3, whereas if we look at only the 3s being replaced with 3332, the proportion of 2s in the new sequence is 1/4. So the true proportion of 2s in the new sequence is x*(1/3) + (1-x)*(1/4). Since this replacement does not change the sequence:
x = x*(1/3) + (1-x)*(1/4)
x = (1/12)*x + 1/4
(11/12)*x = 1/4
x = 3/11
So the proportion of 2s in the sequence is 3/11, and the proportion of 3s in the sequence is 8/11. The ratio of 3s to 2s is 8/11 : 3/11, or 8:3.
I got something different. Let me see if I can find a flaw in your reasoning...
We'll construct a sequence with the porportion of 2s you derived:
33323332332
That's eleven digits, three of which are 2s. Much later in the sequence, we'll find:
33323332333233233323332333233233323332332
That's 41 digits, 11 of which are 2s, a slightly lower proportion of 2s. This suggests that the ratio you derived is not a fixed point.
I believe your error lies where you say, "So the true proportion of 2s in the new sequence is x*(1/3) + (1-x)*(1/4)." Because the strings 3332 and 332 are not of equal length, you can't just average the ratios together to find the the combined ratio. At least I think that's correct.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I was previously familiar with this week's Riddler express puzzle, making it especially easy. If you haven't seen it before, you can find the answer by plugging it into the OEIS, but you wouldn't cheat, right?
Anyway, the second riddle is, as expected, tougher. Oddly enough, the question is even a little bit of a hint for the first riddle. I was able to get it in maybe 90 minutes of work, most of which was spent on algebra. I'm confident in my answer, which I'll post sometime around Sunday evening. Did anyone else get it? I'm looking at you, FractalFusion.
Edit: Mixed up express and classic. I was familiar with the Riddler Express puzzle, not with the classic puzzle.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Bobo the King wrote:
Oooh, so sorry! The correct answer is 1/29. The initial holder of the potato has zero probability of winning. :P
Based on the statement of the question, I'm getting 1/30, if I'm understanding this right.
Riddler Express wrote:
A class of 30 children is playing a game where they all stand in a circle along with their teacher. The teacher is holding two things: a coin and a potato. The game progresses like this: The teacher tosses the coin. Whoever holds the potato passes it to the left if the coin comes up heads and to the right if the coin comes up tails. The game ends when every child except one has held the potato, and the one who hasn’t is declared the winner.
By my understanding, the circle is 31 people large, and none of the 30 children start with the potato, because the teacher does.
Huh. Well, that's annoying. I could have sworn that an earlier version of the problem statement included the sentence, "The teacher begins by giving the potato to a random student," in which case the only nontrivial way to interpret the challenge is the 29 remaining students' probabilities based on their positions relative to the initial potato-holder. I can't find that sentence anymore, so either I dreamed it up or the page was edited.
I just checked out a cached version from August 4th and... no mention of passing the potato to a random student initially. Damn it, looks like I wasted a submission.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
FractalFusion wrote:
Riddler Express: It's one of those questions where either you get it or you don't.
Every child has the same chance (1/30) of winning. At some point, the potato is first held by either of the two people beside you; let's call them A and B, and without loss of generality, A has the potato; thus B never had it. To win, the potato must be passed from A to B the long way around (i.e. not through you). This applies to every child regardless of how the potato was passed previously; therefore every child has the same chance of winning.
Oooh, so sorry! The correct answer is 1/29. The initial holder of the potato has zero probability of winning. :P
Kidding aside, that was the same logic I used to solve the problem and I'm glad to see someone smarter than me agrees.
FractalFusion wrote:
Riddler Classic: I assume likewise as Bobo the King did: whoever attempts to use the washroom leaves immediately if the bathroom is occupied (i.e. the only person modifying the door sign is the current user of the bathroom).
First, in the long run, the state of the door sign when vacant tends to probability 1/2 for both "occupied" and "vacant" (this is because only 2/3 of the users affect the sign: half of them set it to "occupied" and half of them set it to "vacant").
Given that, we can calculate the probability of cases. I call user behavior T1 if they ignore the sign, T2 if they set it to "occupied" but not "vacant" at the end, and T3 if they set it to "occupied", then "vacant" at the end. Each behavior occurs with equal probability (1/3).
occupied, user is T1, sign="occupied": 1/2 * 1/3 * 1/2 = 1/12 (because of the long run probability for the sign)
occupied, user is T2, sign="occupied": 1/2 * 1/3 * 1 = 1/6
occupied, user is T3, sign="occupied": 1/2 * 1/3 * 1 = 1/6
occupied, sign="occupied": 5/12
occupied, sign="vacant": 1/2 - 5/12 = 1/12
vacant, last user was T1, sign="occupied": 1/2 * 1/3 * 1/2 = 1/12 (because of the long run probability for the sign)
vacant, last user was T2, sign="occupied": 1/2 * 1/3 * 1 = 1/6
vacant, last user was T3, sign="occupied": 1/2 * 1/3 * 0 = 0
vacant, sign="occupied": 1/4
vacant, sign="vacant": 1/2 - 1/4 = 1/4
sign="occupied": 5/12 + 1/4 = 2/3
sign="vacant": 1/3
occupied given sign="occupied": (5/12) / (2/3) = 5/8
vacant given sign="vacant": (1/4) / (1/3) = 3/4
I'm not sure if your work here matches what you did on paper, but I opted to model the problem explicitly as a Markov chain. I drew up a directed graph showing the likelihoods of transitioning from/to each of the six allowed states. What's especially nifty is that a symmetry is apparent, reducing the effective number of variables by half. Draw the graph and you'll find that:
P(sign="vacant" & occupant=full forgetful) = P(sign="occupied" & occupant=full forgetful)
P(sign="occupied" & occupant =half forgetful) = P(sign="occupied" & occupant=conscientious)
P(sign="vacant" & occupant=null) = P(sign="occupied" & occupant=null)
So I used that graph to draw up a 6x6 sparse matrix. It can be shown that the matrix corresponding to a Markov chain has eigenvalue 1, so I just plugged in that eigenvalue and went to work solving for the three distinct probabilities. My answers agree with yours.
If the behavior of the employees is dependent on the state of the sign, it's fairly easy to modify the graph and corresponding matrix. The only bad thing about it is that it would likely break the symmetry of the problem as I outlined it.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Mitjitsu wrote:
The key is not to go if you or someone else is prone to gambling more than they can afford to lose. The only time I ever enter a casino is strictly to play poker. That way they can never make money off me.
It's all too easy to fall into the "personal responsibility trap". I would love to think that we're all in control of our own destinies and only idiots would gamble away their life savings.
As it turns out, some drugs used to treat Parkinson's disease can turn people into compulsive gamblers. (The relevant segment begins around 7:35 of the audio.) If medication can cause this, it's not such a leap to imagine that there are some people who are born without certain inhibitions. Should we say "tough luck, some people have to draw the short straw"? Maybe. I know some will. But I at least say we should frame the discussion around the uncomfortable fact that we all perhaps have less free will than we'd like to imagine.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I'm not usually all that good at FiveThirtyEight's The Riddler puzzles since I usually give up before working out an answer. This week, however, I think I got both of the answers right. The "Riddler Express" puzzle, a game of hot potato, took longer for me to solve than the "Riddler Classic" puzzle, determining whether a bathroom is occupied. I should note that the bathroom puzzle has a somewhat ambiguous problem statement. Nothing is said about whether or how the employees' behavior is influenced by the status of the sign. I assumed that all employees, regardless of their habits, knock or attempt to open the door, then leave to find another bathroom if it is occupied. Basically, I assumed that the bathroom always returned to a vacant state before anyone even attempts to open the door again. It is also plausible that people might wait to enter if the sign says "occupied" or semi-forgetful and conscientious employees would switch the sign to "occupied" if it says vacant while the bathroom is occupied. While I didn't perform any analysis beyond what I assumed of the problem statement, my method generalizes pretty easily to other employee behaviors.
So keeping in mind that there are about 14 hours until the submission deadline (might want to wait before replying), what results did you get?
It is nice seeing this sort of TAS around. Getting at all the individual character times rolled into a pair of movies is certainly a nice treat.
Thanks for this! Can we get a comparison with RTA times as well?
Edit: I realized it's silly of me to make this request when I have access to the same information that everyone else does. I have no idea how up-to-date these times are or what verification process they underwent. Here's a table of times, which I won't bother mashing together with the above table into a single compendium of TAS vs. RTA times-- I'll leave that piece to someone else.
As I entered the Break the Targets records, I observed that they were usually within about half a second of the TAS record, in case anyone is interested.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I think the overall level of discourse on socialism is extremely poor. I agree with andypanther in that "socialism" is a sort of catch-all term for a whole spectrum of political theories that are, in essence, anti-capitalist. Just as capitalism can have dire consequences if it is poorly implemented, so can socialist ideas.
I also strongly agree with Patashu that we are nearing a point where we will need to figure out what to do about the millions of jobs consumed by automation. I've noticed in America (and I suspect there's similar trends abroad) an emerging "bureaucratic economy", where jobs are increasingly about shuffling meaningless paperwork around. For example, while I'm generally supportive of Common Core standards, they've been implemented bureaucratically at the state and district levels, forcing instructors to document how every single problem supports the Common Core curriculum. I see more and more jobs about generating paperwork, then jobs about validating that paperwork, then jobs about filing that paperwork... I won't say that those jobs are actually making life worse, but it's hard to justify paying someone $40,000+ a year to do them, especially when it already might as well be automated. So many people aren't really doing anything.
Patashu is absolutely right that, like it or not, we pretty much need a universal basic income. Despite right-wing fantasies, we can't let the poor languish and die in the streets-- they'll eventually rebel and follow down Venezuela's path, capitalist and socialist economies alike. I'm ultimately hopeful that we'll work our way through it, but these are nonetheless scary times.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
andypanther wrote:
The PAL publications of Blaster Master, Rygar and Mario Bros. certainly didn't make the site worse. What is the difference in this case?
Glancing over those publications, we have Blaster Master runs at 4 minutes, 25 minutes, and 43 minutes; three categories of Rygar runs (the difference in system appears to be secondary); and Nach said regarding publication of the NTSC Mario Bros. run:
Nach wrote:
Compared to its counter part, there's some engine differences, a tiny enemy difference, and more importantly, a different set of enemy waves. Contrasting to other games where the differences between regional ports consist of a miniscule percentage of their play, seeing as how little this game offers, I find the differences here significant enough to differentiate between the regional ports and give each their own TAS.
and on top of that, there was plenty of discussion there suggesting that the NTSC version should obsolete the PAL version.
Furthermore, I never asserted that publication of this run would make the site worse, I merely offered my own perspective on the question.
And above all else, I just find the whole damn discussion entertaining. I have no horse in this race.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
I have almost nothing to contribute to this discussion so you can... uh... ignore this post if you want. Primarily, I want to say that I'm enjoying reading the discussion. This run practically exists to create controversy and I know a thing or twoabout that.
To me, the choice to publish a movie always boils down to one basic question: Will this run make the site better or worse? Publishing this movie alongside the NTSC branch would clutter the site with a mostly redundant run and potentially set a bad precedent. Obsoleting the NTSC branch would nullify the version of the game that most of this site's users first played. And rejecting this run would disregard the effort that went into it and the nontrivial new tricks that are included. The controversy is compounded by the run's enthusiastic response from viewers and the author's own viewpoint on what should be done here, as well as his status as the author of the NTSC run.
So really what I'm saying is that regardless of what ends up happening, I don't for one second envy this run's judge, but I'm eating plenty of popcorn watching the discussion roll out.
Experienced Forum User, Published Author, Player
(79)
Joined: 8/5/2007
Posts: 865
Derp. I just realized that the primes less than n don't form a partition of n (unless n=2). I think the function we're actually looking for is something like the inverse of this sequence. I dunno, I'm kind of tapped out on this problem.
The sequence has the property that, if you replace every 3 with 3332 and 2 with 332, the resulting sequence will be the same. Let x be the long-term proportion of 2s in the sequence. Replace every 3 with 3332 and 2 with 332. If we look at only the 2s being replaced with 332, the proportion of 2s in the new sequence is 1/3, whereas if we look at only the 3s being replaced with 3332, the proportion of 2s in the new sequence is 1/4. So the true proportion of 2s in the new sequence is x*(1/3) + (1-x)*(1/4). Since this replacement does not change the sequence: x = x*(1/3) + (1-x)*(1/4) x = (1/12)*x + 1/4 (11/12)*x = 1/4 x = 3/11 So the proportion of 2s in the sequence is 3/11, and the proportion of 3s in the sequence is 8/11. The ratio of 3s to 2s is 8/11 : 3/11, or 8:3.
