Puzzle Time - Election Edition
-
wrote on 12 Oct 2020, 15:59 last edited by jon-nyc 10 Dec 2020, 16:00
That doesn’t make any sense. “The successful paths are the remaining ones” isn’t true. It’s a small subset of the remaining ones.
Remember you have to stay in the lead the whole time.
-
wrote on 12 Oct 2020, 16:02 last edited by Klaus 10 Dec 2020, 16:02
By "lead to a tie" I mean: It ever happens that K is not in the lead. Hence by definition the remaining ones must be the ones where K is always leading.
-
wrote on 12 Oct 2020, 16:07 last edited by
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
-
wrote on 12 Oct 2020, 16:08 last edited by Klaus 10 Dec 2020, 16:09
Here's how to construct the 1:1 correspondence.
Assume a path that leads to a tie, say
KKHH...
which yields a tie after 4 votes.
Now take every vote until the tie and flip K with H and vice versa.
The remainder stays the same.HHKK...
That's the corresponding path starting with H.
That correspondence works both ways because every path starting with H must eventually be tied at some point (because K has more votes).
-
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
wrote on 12 Oct 2020, 16:11 last edited by@jon-nyc said in Puzzle Time - Election Edition:
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
Exactly. Those cases shouldn't count as successful. And I don't count them, since they are among the paths where there is at least one tie in between.
-
wrote on 12 Oct 2020, 16:20 last edited by Klaus
Let me illustrate that my solution works with a simpler case:
Let's say that K wins with 3 votes against 2 votes for H.
According to my solution, the probability would be (3-2)/(3+2) = 20%.
Let's consider all 10 possible sequences:
HKKKH
HKKHK
HKHKK
HHKKK
KHKKH
KHKHK
KHHKK
KKHKH
KKHHK
KKKHHOnly two of these are successful, namely:
KKHKH
KKKHH2 out of 10; exactly the 20% my formula predicted.
You can also see the 1:1 correspondence of the remaining 8 ones: There's an equal number of paths starting with H and unsuccessful paths starting with K, namely 4 each. Flip at the first tie and you get the corresponding other one. Here are the four pairs of the correspondence.
HKKKH - KHKKH
HKKHK - KHKKH
HKHKK - KHHKK
HHKKK - KKHHK -
wrote on 12 Oct 2020, 16:31 last edited by
Ah, I thought you meant those that ended in a tie. Not those that tied at all. Let me look at it again after I’m done with lunch
-
Ah, I thought you meant those that ended in a tie. Not those that tied at all. Let me look at it again after I’m done with lunch
-
wrote on 13 Oct 2020, 08:44 last edited by Klaus
By the way, there's an interesting pattern in the puzzles you post. They seem to be extremely complicated and involve all kinds of advanced maths, but then it turns out there's some kind of trick that only applies in the very specific situation that suddenly makes all the complexity go away and there's a very simple solution. I assume one could also come up with all the formulas to compute the number of distinct successful paths (which would involve Catalan numbers and stuff), divide it by the total number of paths, and, after a lot of algebraic manipulation, end up with the same formula. So the actual puzzle is to find a shortcut to the formula, which, in this case, turns out to be the identification of the path correspondence.
-
wrote on 13 Oct 2020, 13:37 last edited by jon-nyc
Your solution is neat.
Another is similar to a cycle lemma proof.
Imagine randomly arranging the votes in a circle and trying to decide where to start in order to satisfy the goal of K always being ahead. You can remove any adjacent pairs KH as they will not lead to an increase in H votes. You are left with 10 Ks at the end of this process, corresponding to starting points that would have resulted in K always being ahead.
10/200=5%
-
Your solution is neat.
Another is similar to a cycle lemma proof.
Imagine randomly arranging the votes in a circle and trying to decide where to start in order to satisfy the goal of K always being ahead. You can remove any adjacent pairs KH as they will not lead to an increase in H votes. You are left with 10 Ks at the end of this process, corresponding to starting points that would have resulted in K always being ahead.
10/200=5%
wrote on 13 Oct 2020, 14:51 last edited by@jon-nyc said in Puzzle Time - Election Edition:
Imagine randomly arranging the votes in a circle and trying to decide where to start in order to satisfy the goal of K always being ahead. You can remove any adjacent pairs KH as they will not lead to an increase in H votes. You are left with 10 Ks at the end of this process, corresponding to starting points that would have resulted in K always being ahead.
You lost me at "You are left with 10 Ks...". Can you elaborate?
-
wrote on 13 Oct 2020, 15:05 last edited by jon-nyc
You would finish the process and there would be 10 ‘K’ votes remaining. Had you started counting from any of those 10 spots on the circle than you would have always had a positive number because every H vote you came across would have been preceded (not necessarily immediately) by a canceling K vote.
-
wrote on 13 Oct 2020, 15:06 last edited by
Try it with a circle of 10 (6K,4H) and you’ll see what I mean.
-
wrote on 13 Oct 2020, 15:07 last edited by
I want to know if the reason Horace hasn’t chimed in is because he’s indignant at his loss to Klaus.
-
wrote on 13 Oct 2020, 15:14 last edited by
Maybe Klaus’s answers weren’t sealed properly and therefore were thrown out.
Horace is likely busy setting up his transition team.