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...
Some time ago I found out that these identities, with a cubic root reducing to a rational number, are just a simple consequence of Cardano's method for solving the cubic equation.
Suppose you look at the equation z3=14-3z, and instead of looking for rational roots, just apply Cardano's method:
Assume that the root can be written as z = a1/3+b1/3
Then, z3 = a + b + 3(ab)1/3z
Comparing the coefficients of this equation with ours, we must have
a + b = 14
ab = -1
a and b are solutions of x2-14x-1=0, which are 7 + sqrt(50) and 7 - sqrt(50)
Therefore, the solution for our equation reads
z = (7+sqrt(50))1/3+(7-sqrt(50))1/3
But from the rational root theorem, we can find that the only real solution is z=2. So,
(7+sqrt(50))1/3+(7-sqrt(50))1/3 = 2
I find this very interesting. Galois' theory tells us that there is always an algorithm for expressing the solution of cubic and quartic equations in terms of radicals. However, simplifying them is another story. The method can give a completely tangled up expression! And we can use it to make interesting math questions!
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.
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.
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.
Well, I'm not really good at these kinds of things, but wouldn't this strategy be higher than 50%:
I'll start. If I see the same number of black and white hats I'll pass, otherwise I'll just randomly guess.
So if I pass, the others will immediately know what color they have and win the game.
Edit: Maybe this kind of strategy can be extended to include the idea of time. For example:
If anyone sees the same number of black and white hats, pass immediately. If nobody passes in the first 10 seconds, [somethingsomething].
Edit2: Actually, the time before a chosen person passes can be used to give information, such as a binary encoding of the hats you see in some order you decided on beforehand. That would make this 100% I think. :P
Edit3: Or even easier, I choose a person and if that person has a white hat, I pass immediately, otherwise I'll wait one minute and pass then!
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Masterjun wrote:
Well, I'm not really good at these kinds of things, but wouldn't this strategy be higher than 50%:
I'll start. If I see the same number of black and white hats I'll pass, otherwise I'll just randomly guess.
So if I pass, the others will immediately know what color they have and win the game.
Edit: Maybe this kind of strategy can be extended to include the idea of time. For example:
If anyone sees the same number of black and white hats, pass immediately. If nobody passes in the first 10 seconds, [somethingsomething].
Edit2: Actually, the time before a chosen person passes can be used to give information, such as a binary encoding of the hats you see in some order you decided on beforehand. That would make this 100% I think. :P
I think this doesn't follow the riddle's rules. ''you make your guesses or passes in separate soundproof rooms''. So the other people won't know if you passed or not.
EDIT: I think I can see a way of getting a better chance than 50%. Working on it.
dang i misread also
Edit: For those who are curious, this was my post before I edited it:
https://pastebin.com/eDFpfsvE
It fails due to the requirement that all guesses be made separately and in a soundproof room.
Edit 2: This solution can still work if the participants are not forced to enter a soundproof room at the same time. If they are able to choose when they enter the room, then you could substitute the information gained from them passing for the information gained from when they choose to enter the room.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
If there were 3 people, there is a strategy to get 75% chance.
If you see 2 hats of different colors, pass.
If you see 2 hats of the same color, guess you have the other color.
For 7 people there is a strategy built with the same idea, but it's more complex. I think I'm getting slightly above 50% chances, but they are surely not optimal.
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.
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.
/edit: there is no communication after the hats are chosen. The riddle says so. Nobody knows what anybody else has (or hasn't) guessed.
No communication is possible during the game — you make your guesses or passes in separate soundproof rooms — but you are allowed to confer beforehand to develop a strategy.
If "randomly" means 50/50 chance for everyone to get either black or white, then the resulting distribution has some patterns that can be exploited.
No single person can do better than 50/50. But the outcome of the contest is not determined by one guess. If you can manipulate it in such a way that you have a high likelyhood of few people guessing correctly (and everyone else passing), and a low likelyhood of everyone making a wrong guess, then the average outcome of each guess is still 50/50, but the chances of winning the contest have improved.
While I was still working out the numbers, BrunoVisnadi has already posted a great hint. With seven people, I can find a simple strategy for ~54.7% chance of winning. With a bit more complexity, I can improve the strategy to ~65.6%.
The riddle doesn't say anything about the friends being arranged in a circle (or otherwise having an order), so I'm out of ideas for further improvements.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
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%
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.
Ok, apparently this isn't spoiler-free any longer. Let's talk business.
Bruno got the same chance as I did, but his rules are a lot more complicated.
My strategy is: if you see exactly 4 or 6 hats of the same color, guess the other color. Otherwise, pass.
This will win on any 1/6 or 3/4 split, but is guaranteed to lose on 0/7 or 2/5. Works out to 84/128 ~ 65.6%, too.
Bobo the King wrote:
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.
That P is 0.5, no matter what you do. That path does not lead to a solution.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Tub wrote:
Ok, apparently this isn't spoiler-free any longer. Let's talk business.
Bruno got the same chance as I did, but his rules are a lot more complicated.
My strategy is: if you see exactly 4 or 6 hats of the same color, guess the other color. Otherwise, pass.
This will win on any 1/6 or 3/4 split, but is guaranteed to lose on 0/7 or 2/5. Works out to 84/128 ~ 65.6%, too.
Bobo the King wrote:
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.
That P is 0.5, no matter what you do. That path does not lead to a solution.
Well, I figured it was ok to spoil a strategy as other people had already done it with their interpretation of the problem.
Your solution is much simpler indeed. For some reason I made mine in a way that only 1 person would guess in each winning scenario, which now I see, is unnecessary. Also, it's interesting to see that the trade off of ''2/7 of the 2-5 scenarios and 1/7 of 1-6 scenarios'' for ''all 1-6 scenarios and no 2-5 scenarios'' was completely even.
I found a slightly better strategy, at 85/128 (~66.4%). Strategy is likewise based solely on number of hats of each color seen (first number is black, second is white):
- 0/6: Guess white (aim for 0/7)
- 1/5: Guess black (aim for 2/5)
- 2/4: Pass
- 3/3: Guess white (aim for 3/4)
- 4/2: Guess black (aim for 5/2)
- 5/1: Pass
- 6/0: Guess white (aim for 6/1)
The strategy wins when the distribution is 0/7, 2/5, 3/4, 5/2, or 6/1, and loses otherwise. The chance of winning is then (1+21+35+21+7)/128 = 85/128.
Can this type of strategy be generalized to n people? Strangely, Riddler's generalization specifically says 2N−1 instead of just n. Since there is nothing we talked about so far that makes 2N−1 special, it makes me wonder whether we missed anything.
Riddler wrote:
then you win a fabulous, all-expenses-paid trip to see the next eclipse
How oddly non-specific this "eclipse" is. I can see the next eclipse just by walking outside at night. :)
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.
Regarding the Riddler, I've seen the problem before; though I didn't immediately remember the optimal solution I was able to reconstruct it surprisingly quickly.
For some general comments, I will point out that the solution described for 3 people implies a lower bound of 75% for 7 people (simply ignore the last four people by making them all pass), which is not optimal. And yes, the value 2N-1 is special for this problem.
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!
I did another attempt using run-lengths. Assuming you can still see your friends (and not just their hats), you assign places in a circle to everyone.
Notation (3, 2, 1, 1) means that along the circle, there are 3 of one color, 2 of the other, 1 of the first, 1 of the other. I'll always list the longest run first (or, in one case, the shortest one last), which usually means that 14 hat-combinations exibit this behaviour (7 through rotation, times two for switching colors).
A) 2x (7)
B) 14x (6, 1)
C) 14x (5, 2)
D) 14x (4, 3)
E) 14x (4, 1, 1, 1)
F) 14x (3, 2, 1, 1)
G) 14x (3, 1, 2, 1)
H) 14x (3, 1, 1, 2)
I) 14x (2, 2, 2, 1)
J) 14x (2, 1, 1, 1, 1, 1)
9*14 + 2 = 128, so we didn't miss anything. What properties can we use?
Most patterns have four runs.
Rule: If your neighbours have the same color, guess in such a way that the number of runs is four. This fails all patterns with 2 or 6 runs, while pattern A gets no guesses
Revised rule: Additionally, if you see 6 of the same color, guess the same color; thus winning pattern A
Result: 72/128 ~ 56.25%
Most of the patterns have exactly one run with length 3 or more; only D has two, and I+J have none.
Rule: If your neighbours have the same color, find the longest run not involving your neighbours. If there is none (i.e. you see 6 of the same color), do not vote. If the longest run has a length of 1 or 2, vote the same color as your neighbours. Winning B,C,E,F,G,H, failing I, J, no guesses on A, D
Result: 84/128 = 65.6%. Again.
Not sure if further improvements are possible with this.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Arcorann wrote:
Regarding the Riddler, I've seen the problem before; though I didn't immediately remember the optimal solution I was able to reconstruct it surprisingly quickly.
For some general comments, I will point out that the solution described for 3 people implies a lower bound of 75% for 7 people (simply ignore the last four people by making them all pass), which is not optimal. And yes, the value 2N-1 is special for this problem.
Thanks for this observation. I could get slightly better than 75%: 25/32, or 78.125%. I'm pretty sure it can be improved further, perhaps to exactly 7 /8.
