I submitted my extra credit solution before realizing that the problem specification isn't entirely clear. Am I assuming correctly that the slips are drawn without replacement? That is, Kyle does not put his slip back before Julien draws?
On the triangle being split up into identical triangles, each similar to the original... The original triangle has area 1/2 * b * h = 1, and hypotenuse c = sqrt(5). In order to split into 5 identical triangles, each must have area 1/5. So, if the new triangles have legs b' and h', then 1/2 b' h' = 1/5. Since they're similar to the original triangle, b' = 2h'. Thus, h'^2 = 1/5, h' = sqrt(5)/5, and b' = 2sqrt(5)/5. The hypotenuse c' = sqrt(b'^2 + h'^2) = 4/5 + 1/5 = 1.
We have to be able to make each of the sides of the original triangle by combining up to 5 of b', h', and c'. Is this possible? Well, the total perimeter of the original triangle is P = 1 + 2 + sqrt(5). sqrt(5) > 2, so P > 5. Even if we aligned all 5 of our identical similar triangles with their longest sides (the hypotenuse, length 1) along the perimeter of our original triangle, we would not be able to cover the length. Therefore, no, we are not able to divide the triangle into 5 identical similar triangles.
I'm a little confused about the Extra Credit. It says "Kyle draws first and looks at his slip of paper." But in the next paragraph you ask: "Which slip or slips of paper might Kyle have drawn?"
He has only drawn one. There may be more than one slip he could draw that produces the result that the odds are as even as they could be.
Consider that the game was just played needing a single flip, H or T. In that case, the game is 50/50 regardless of which player gets which slip, so the answer to the question would be that Kyle could have drawn either H or T.
Ooh whoops, I botched my connections extra credit solution. After seeing five guesses wouldn't work, I then moronically "solved" with six, in terms of determining the sets, then using two more guesses to actually lock them in. Now that I understand...
Not sure this is that much simpler than the given tree, but seems you can do:
Check four "static" combos, not overly similar (not all work). ABC{D,E,F} + ACDH works. For each of the 35 combos, this gives a list of four results, some combo of ONE AWAY, NOTHING or DONE. This splits up the 35 combos into:
- 10 unique results (e.g. only one sequence gives NOTHING-NOTHING-NOTHING-ONE AWAY: ACGH), four of which which hit DONE, and the other six you can pick up in two more guesses
- 5 pairs of combos (e.g. only two combos give ONE-ONE-NOTHING-NOTHING). For these, you can guess one of them with your 5th guess. If that's wrong, two more (6th and 7th) will pick up the solution.
- 5 groups of three (e.g. three combos give NOTHING-NOTHING-ONE-ONE: ABFG, ACFH, ADEH). Turns out for each of these (not too hard to confirm) groups of three, you can check any of the three, and either it's correct (you're done in six guesses) or the remaining two combos give different results (one gives ONE, other NOTHING), and you can finish in 7 total. E.g. guess ABFG, and that's two away from ACFH but one away from ADEH (by complement).
I'm amused that people thought 10% was low! I was expecting a much smaller number.
Last week I posted (after the deadline) that I'd found a six-guess solution. I'm pretty certain about this solution, which doesn't user a binary tree. I'll recheck to make sure I didn't mess something up, then send it to you.
Dec 16, 2023·edited Dec 16, 2023Liked by Zach Wissner-Gross
In fact, the binary tree posted only uses 6 guesses, not 7! All of the final guesses are just the complement of the previous guess--either the complement or the original will solve the puzzle!
I think I see the issue now; the seventh guess isn't a guess. When you guess the first set of four correct ones, the game automatically puts the other four into a set. You're counting a last guess that doesn't need guessing.
I submitted my extra credit solution before realizing that the problem specification isn't entirely clear. Am I assuming correctly that the slips are drawn without replacement? That is, Kyle does not put his slip back before Julien draws?
That's right, the slips are drawn without replacement.
In the extra credit, you listed THH twice, and missed TTH.
Thanks, updated!
My solution to the first coin problem using Markov chain:
https://bogdanlata.github.io/projects/2_project/
It took me awhile. Thanks
On the triangle being split up into identical triangles, each similar to the original... The original triangle has area 1/2 * b * h = 1, and hypotenuse c = sqrt(5). In order to split into 5 identical triangles, each must have area 1/5. So, if the new triangles have legs b' and h', then 1/2 b' h' = 1/5. Since they're similar to the original triangle, b' = 2h'. Thus, h'^2 = 1/5, h' = sqrt(5)/5, and b' = 2sqrt(5)/5. The hypotenuse c' = sqrt(b'^2 + h'^2) = 4/5 + 1/5 = 1.
We have to be able to make each of the sides of the original triangle by combining up to 5 of b', h', and c'. Is this possible? Well, the total perimeter of the original triangle is P = 1 + 2 + sqrt(5). sqrt(5) > 2, so P > 5. Even if we aligned all 5 of our identical similar triangles with their longest sides (the hypotenuse, length 1) along the perimeter of our original triangle, we would not be able to cover the length. Therefore, no, we are not able to divide the triangle into 5 identical similar triangles.
Aw, heck, I see how this is wrong now.
I'm a little confused about the Extra Credit. It says "Kyle draws first and looks at his slip of paper." But in the next paragraph you ask: "Which slip or slips of paper might Kyle have drawn?"
Hasn't Kyle only drawn one slip of paper?
He has only drawn one. There may be more than one slip he could draw that produces the result that the odds are as even as they could be.
Consider that the game was just played needing a single flip, H or T. In that case, the game is 50/50 regardless of which player gets which slip, so the answer to the question would be that Kyle could have drawn either H or T.
Ah, got it! Thanks.
Ooh whoops, I botched my connections extra credit solution. After seeing five guesses wouldn't work, I then moronically "solved" with six, in terms of determining the sets, then using two more guesses to actually lock them in. Now that I understand...
Not sure this is that much simpler than the given tree, but seems you can do:
Check four "static" combos, not overly similar (not all work). ABC{D,E,F} + ACDH works. For each of the 35 combos, this gives a list of four results, some combo of ONE AWAY, NOTHING or DONE. This splits up the 35 combos into:
- 10 unique results (e.g. only one sequence gives NOTHING-NOTHING-NOTHING-ONE AWAY: ACGH), four of which which hit DONE, and the other six you can pick up in two more guesses
- 5 pairs of combos (e.g. only two combos give ONE-ONE-NOTHING-NOTHING). For these, you can guess one of them with your 5th guess. If that's wrong, two more (6th and 7th) will pick up the solution.
- 5 groups of three (e.g. three combos give NOTHING-NOTHING-ONE-ONE: ABFG, ACFH, ADEH). Turns out for each of these (not too hard to confirm) groups of three, you can check any of the three, and either it's correct (you're done in six guesses) or the remaining two combos give different results (one gives ONE, other NOTHING), and you can finish in 7 total. E.g. guess ABFG, and that's two away from ACFH but one away from ADEH (by complement).
I'm amused that people thought 10% was low! I was expecting a much smaller number.
Last week I posted (after the deadline) that I'd found a six-guess solution. I'm pretty certain about this solution, which doesn't user a binary tree. I'll recheck to make sure I didn't mess something up, then send it to you.
In fact, the binary tree posted only uses 6 guesses, not 7! All of the final guesses are just the complement of the previous guess--either the complement or the original will solve the puzzle!
I think I see the issue now; the seventh guess isn't a guess. When you guess the first set of four correct ones, the game automatically puts the other four into a set. You're counting a last guess that doesn't need guessing.
Yup, and I accepted all such interpretations of "guess" as correct.
It makes a lot more sense now :)