OK, I finally understand the problem and why exactly the Riddler said 2N−1. BrunoVisnadi had the right idea; each person is allowed to see both the other hats that the friends are wearing as well as the friends who wear them. This means that the group of friends can set up rules for guessing or passing (based on who they see wears what) to maximize their chances of winning. Remember that they cannot communicate during the game, so effectively, everyone makes their choice at the same time. To win, at least one person needs to guess right, and nobody else is permitted to guess wrong.
There is indeed something special about a group of 3, 7, 15, 31, ... that requires the generalization to be 2N−1. Well, it could be generalized to any n, but if it is not in the form 2N−1, the question becomes far more difficult and requires computer search; in the form 2N−1 it is still difficult but at least there is some theory out there that may be helpful. 7 can be done by hand in any case.
I actually like the hat-only version of the problem (where you can't see your friends so you can only base your choice on the number of hats of each color). The strategy I mentioned above can be generalized to all n; the win probability in this version approaches 2/3 as n approaches infinity. (The strategy sums two of every three binomial coefficients. Using complex numbers, you can show that summing every third binomial coefficient gives one of the two integers nearest 2n/3.)
Warp wrote:
Bobo the King wrote:
sin(18) = sqrt(3 - sqrt(5))/8
That doesn't seem to be correct. Note that sin(18°) is approximately 0.309, while your result is approximately 0.109.
What Bobo the King clearly meant was sqrt((3 - sqrt(5))/8).
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
Warp wrote:
Bobo the King wrote:
sin(18) = sqrt(3 - sqrt(5))/8
That doesn't seem to be correct. Note that sin(18°) is approximately 0.309, while your result is approximately 0.109.
What Bobo the King clearly meant was sqrt((3 - sqrt(5))/8).
When I get as the result of a problem a square root inside a square root, I always try to get a equivalent, cleaner expression.
sqrt((3 - sqrt(5))/8) squared gives us, obviously, (3 - sqrt(5))/8. So what else gives this number when squared?
(a*sqrt(b) + c*sqrt(d))^2 = a²b + c²d + 2ac(sqrt(bd)). So let b = 1 and d = 5
a² + 5c² + 2ac*sqrt(5) = (3 - sqrt(5))/8
a² + 5c² = 3/8 and 2ac = 1/8. If we write c as 1/16a in the first expression, we find:
a² + 5/(256a²) = 3/8. This is expected to have 4 solutions for a. And they are +- 1/4 and +- sqrt(5)/4. If a = 1/4 in 2ac = 1/8, then c = 1/4.
That is, we can write sin(18º) as (1 + sqrt(5))/4, as this number squared also gives us (3 - sqrt(5))/8
EDIT: I messed it up, as Warp pointed out. We must have a = -1/4, which gives us sin(18º) = (sqrt(5) - 1)/4
It's also possible to calculate the sin(9°) through a similar technique to the one used by blackpenredpen to calculate sin(18°).
Why not give it a shot Warp. ;D
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
To finish the Riddler question, BrunoVisnadi indeed guessed correctly on a previous post that the strategy is improvable to 7/8. This is actually a coding theory problem in disguise:
Let 0=white, 1=black and assign an order to the 7 friends. Map each of the 27=128 possible hat distributions to a binary sequence of 0's and 1's of length 7, e.g. 0110101. This problem then becomes: can at least 1 of the 7 friends correctly guess the sequence given that each one sees every symbol (0 or 1) except their own?
Consider a particular sequence (say 0110101). Say we take a chance and assume that 0110101 is not the sequence. If 0110101 is the actual sequence, then we lose. However, if 0110101 is not the sequence, but 1110101 is, then we can win; friend 1 sees ?110101 and so correctly guesses that it is 1110101. Likewise, we can correctly guess 0010101, 0100101, ..., 0110100, that is, any of the 7 sequences that are one symbol away from 0110101. So for 1 losing sequence, we can generate up to 7 winners (maximum winning rate is thus 7/8).
The strategy is thus: Choose a subset S of the 128 binary sequences, such that the number of sequences that are not in S and are one away from an element of S (and thus sure winners) is maximized. It turns out for n=7 that there is such an S (of size 128/8=16) that exactly achieves the maximum; that is, every element not in S is one away from exactly one element in S. For example:
S={0000000,1101000,0110100,0011010,0001101,1000110,0100011,1010001, 1111111,0010111,1001011,1100101,1110010,0111001,1011100,0101110}
(I.e. all 0's and 1101000 and all its cycles, and then all their complements.)
The strategy: For each friend, if one of the two possibilities is an element of S, guess the one which is not in S; otherwise pass. The strategy wins if the sequence is not in S and loses if the sequence is in S. Win rate: 7/8.
S is what is known as a Hamming code of 7 bits. The Hamming codes are the "optimal" solutions for the S in the strategy above; they occur whenever n=2N-1 and the win rate is (2N-1)/2N. E.g. for n=3, S={000,111}; this is the "guess the other color if you see two hats of the same color and pass otherwise" strategy already described in one of the previous posts and has a win rate of 3/4.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
To finish the Riddler question, BrunoVisnadi indeed guessed correctly on a previous post that the strategy is improvable to 7/8. This is actually a coding theory problem in disguise:
Let 0=white, 1=black and assign an order to the 7 friends. Map each of the 27=128 possible hat distributions to a binary sequence of 0's and 1's of length 7, e.g. 0110101. This problem then becomes: can at least 1 of the 7 friends correctly guess the sequence given that each one sees every symbol (0 or 1) except their own?
Consider a particular sequence (say 0110101). Say we take a chance and assume that 0110101 is not the sequence. If 0110101 is the actual sequence, then we lose. However, if 0110101 is not the sequence, but 1110101 is, then we can win; friend 1 sees ?110101 and so correctly guesses that it is 1110101. Likewise, we can correctly guess 0010101, 0100101, ..., 0110100, that is, any of the 7 sequences that are one symbol away from 0110101. So for 1 losing sequence, we can generate up to 7 winners (maximum winning rate is thus 7/8).
The strategy is thus: Choose a subset S of the 128 binary sequences, such that the number of sequences that are not in S and are one away from an element of S (and thus sure winners) is maximized. It turns out for n=7 that there is such an S (of size 128/8=16) that exactly achieves the maximum; that is, every element not in S is one away from exactly one element in S. For example:
S={0000000,1101000,0110100,0011010,0001101,1000110,0100011,1010001, 1111111,0010111,1001011,1100101,1110010,0111001,1011100,0101110}
(I.e. all 0's and 1101000 and all its cycles, and then all their complements.)
The strategy: For each friend, if one of the two possibilities is an element of S, guess the one which is not in S; otherwise pass. The strategy wins if the sequence is not in S and loses if the sequence is in S. Win rate: 7/8.
S is what is known as a Hamming code of 7 bits. The Hamming codes are the "optimal" solutions for the S in the strategy above; they occur whenever n=2N-1 and the win rate is (2N-1)/2N. E.g. for n=3, S={000,111}; this is the "guess the other color if you see two hats of the same color and pass otherwise" strategy already described in one of the previous posts and has a win rate of 3/4.
This answer reminded some of my attempts to solve the problem 1 in this Quora reply: https://www.quora.com/What-is-a-brain-teaser-that-is-very-short-and-extremely-hard-for-adults/answer/Nikhil-Bhavar-1
I didn't read its answer yet, but I believe there will be some similarity. I remember trying to find a function so that, for each 64 digits long binary numbers, each number that differs in 1 from that number gets mapped to a different natural between 1 and 64. It's not the same thing you did with 7 digits binary numbers, though.
Also, is there an algorithm to find the 2^(2^N - N - 1) numbers that cover every binary number with 2^N - 1 digits, for higher values of N?
It's also possible to calculate the sin(9°) through a similar technique to the one used by blackpenredpen to calculate sin(18°).
Why not give it a shot Warp. ;D
It's also possible to calculate the sin(9°) through a similar technique to the one used by blackpenredpen to calculate sin(18°).
Why not give it a shot Warp. ;D
I tried it, I couldn't figure anything out.
Hint, if you follow the same procedure as rpbp you get a 18-72-90 right triangle. But the problem is you need the side that represents the cosine of 18°. 🤔
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Hint, if you follow the same procedure as rpbp you get a 18-72-90 right triangle. But the problem is you need the side that represents the cosine of 18°. 🤔
I tried with a triangle with angles 18°, 81° and 81°, and trying to find similar triangles within it, but I couldn't figure anything out. There was always one side too many with an unknown length. I might have missed something obvious, though.
I didn't try with a 18°, 72° and 90° triangle.
The hypotenuse has length 1. The shorter cathetus has a length of sin(18°), which exact value we know from the previous problem. The longer cathetus can be calculated using Pythagoras.
But then what? One idea would be to halve the 18° angle, getting a new triangle. However, while we know the length of the longer cathetus (ie. it's the same as above), we don't know the length of the hypotenuse nor the shorter cathetus (I don't think it's just sin(18°)/2, even though one's tempted to think so). I can't think of any similar triangles that could be formed either, which would give us any more information...
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.
Let ABCDE be a regular pentagon with side = 1.
By playing a little bit, we can get those angles quite easily.
Let d = AC, x = GC, y = BF, h = CF.
ΔGBC ≅ ΔBCA --> AC/AB = CB/CG --> d/1 = d = 1/x (I)
ΔABG is isosceles. Therefore AG = AB = 1.
AC = AG + GC --> d = 1 + x (II)
By I and II we have: 1/x = 1 + x --> 1 = x + x² --> x² + x - 1 = 0
delta = 5 --> x = (-1 +- sqrt(5))/2
x is positive, so we have x = (sqrt(5) - 1)/2
By II, d = 1 + (sqrt(5) - 1)/2 = (sqrt(5) + 1)/2 (III)
By Pythagoras theorem, y² + h² = 1 (IV)
By Pythagoras theorem, (1 + y)² + h² = d²
Using III: y² + 2y + 1 + h² = (5 + 2*sqrt(5) + 1)/4
(y² + h²) + 1 + 2y = (6 + 2*sqrt(5))/4
Using IV: 2y + 2 = (3 + sqrt(5))/2
2y = (3 + sqrt(5))/2 - 4/2 = (sqrt(5) - 1)/2
y = (sqrt(5) - 1)/4
But, sin(18°) = BF/BC = y/1 = (sqrt(5) - 1)/4
Your approach is interesting (and different from the usual method). However, I'm not exactly sure how you deduce that the angle between AB and AC is 36°, and that the angle between CB and CF is half of that. Also, I'm not sure how you deduce that ABG is isosceles.
Yes, problem 1 uses an idea that is extremely similar to how Hamming codes are formed: parity. An explanation is here: http://datagenetics.com/blog/december12014/index.html (section "Parity"). If we eliminate the top-left corner of the board (which is not involved in any of the 6 parity filters), and take all 257 possible boards on the 63 remaining squares that all have the same parity pattern, these boards form a Hamming code on 63 bits.
BrunoVisnadi wrote:
Also, is there an algorithm to find the 2^(2^N - N - 1) numbers that cover every binary number with 2^N - 1 digits, for higher values of N?
There is a "general algorithm" based on parity and data bits that can be used to generate Hamming codes: https://en.wikipedia.org/wiki/Hamming_code (section "General algorithm"). Note that the Hamming code generated is a (2N-N-1)-dimensional subspace of Z2 ^ (2N-1). The columns of the parity check matrix consist of all possible combinations of nonzero vectors of length N; the ones corresponding to powers of two represent parity bits (N of them) and the others represent data bits (2N-N-1 of them). Since the parity bits are uniquely determined from the data bits, the Hamming code is obtained by plugging in all 2^(2N-N-1) possible sequences for the data bits. To get just a basis of size 2N-N-1, for each of the 2N-N-1 data bits, plug in 1 for that bit and 0 for all other data bits to get its corresponding bitword. The case N=3 is illustrated on Wikipedia.
Joined: 10/27/2004
Posts: 1978
Location: Making an escape
Warp wrote:
Your approach is interesting (and different from the usual method). However, I'm not exactly sure how you deduce that the angle between AB and AC is 36°, and that the angle between CB and CF is half of that. Also, I'm not sure how you deduce that ABG is isosceles.
Basic geometry. Observe that triangle ABC is isocolese, and go from there. Two things to keep in mind are that if a triangle is isocolese, then the angles at the base are equal, and if two angles in a triangle are equal, then the triangle is isoceles.
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
2-do:
Smurfs Nightmare, The (EU) GBC 10%
fin :
Mega Man: Dr. Wily's Revenge improvement: submitted
Mega Man II Improvement: submitted
Mega Man IV Improvement: submitted
Mega Man V Improvement: submitted
future plan:
-n-
2-do:
Smurfs Nightmare, The (EU) GBC 10%
fin :
Mega Man: Dr. Wily's Revenge improvement: submitted
Mega Man II Improvement: submitted
Mega Man IV Improvement: submitted
Mega Man V Improvement: submitted
future plan:
-n-
Let g(x) be the inverse function of (x-1)ln(x). Then the second solution is x=g(ln(2)).
Couldn't think of any better way to state the exact solution (even WolframAlpha doesn't give me anything). An approximation for x is x≈0.34632336227858092206485655.
Edit: Technically, to be well-defined, g(x) should be defined as the inverse function of (x-1)ln(x) on the interval (0,1). (By itself, (x-1)ln(x) has two branches, one on (0,1) and one on (1,∞).)
Thatguy,
It looks like it's not possible to use the W function to simplify this expression.
Warp, did you solve this equation? If so, give us a hint, which special function did you use?
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Let g(x) be the inverse function of (x-1)ln(x). Then the second solution is x=g(ln(2)).
Actually, a better definition might be to extend the Lambert W function. Let's call it where W(x;a) is the inverse of (x-a)e^(x).In this case x = W(2; -1) + 1
I got this wrong. Working it out:
xx - 2x = 0
xx = 2x
ln(xx) = ln(2x)
x ln(x) = ln(2x)
eln(x) ln(x) = ln(2x)
eln(x) ln(x) = ln(2) + ln(x)
ln(x) * (eln(x) - 1) = ln(2)
So we'd actually need a slightly different function. W(x;a) = f-1(x*(e(x)-a))
W(ln(2); 1) = ln(x)
x = eW(ln(2); 1)
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
I came here just to point out the trivial but surprising (to me, at least) corollary:
sin(18°) = (φ-1)/2
where φ is the golden ratio. Alternatively, we can define φ in terms of sin(18°):
φ = 2sin(18°) + 1
Let ABCDE be a regular pentagon with side = 1.
By playing a little bit, we can get those angles quite easily.
Let d = AC, x = GC, y = BF, h = CF.
ΔGBC ≅ ΔBCA --> AC/AB = CB/CG --> d/1 = d = 1/x (I)
ΔABG is isosceles. Therefore AG = AB = 1.
AC = AG + GC --> d = 1 + x (II)
By I and II we have: 1/x = 1 + x --> 1 = x + x² --> x² + x - 1 = 0
delta = 5 --> x = (-1 +- sqrt(5))/2
x is positive, so we have x = (sqrt(5) - 1)/2
By II, d = 1 + (sqrt(5) - 1)/2 = (sqrt(5) + 1)/2 (III)
By Pythagoras theorem, y² + h² = 1 (IV)
By Pythagoras theorem, (1 + y)² + h² = d²
Using III: y² + 2y + 1 + h² = (5 + 2*sqrt(5) + 1)/4
(y² + h²) + 1 + 2y = (6 + 2*sqrt(5))/4
Using IV: 2y + 2 = (3 + sqrt(5))/2
2y = (3 + sqrt(5))/2 - 4/2 = (sqrt(5) - 1)/2
y = (sqrt(5) - 1)/4
But, sin(18°) = BF/BC = y/1 = (sqrt(5) - 1)/4
