Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse

The New Coffee Room

  1. TNCR
  2. General Discussion
  3. Puzzle Time - Election Edition

Puzzle Time - Election Edition

Scheduled Pinned Locked Moved General Discussion
30 Posts 4 Posters 186 Views
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • K Offline
    K Offline
    Klaus
    wrote on 12 Oct 2020, 11:23 last edited by
    #8

    Right. The factorial only kicks in once there aren't enough votes left anymore 🙂

    1 Reply Last reply
    • D Offline
      D Offline
      Doctor Phibes
      wrote on 12 Oct 2020, 12:06 last edited by Doctor Phibes 10 Dec 2020, 12:06
      #9

      You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.

      I was only joking

      K 1 Reply Last reply 12 Oct 2020, 15:25
      • J Offline
        J Offline
        jon-nyc
        wrote on 12 Oct 2020, 12:17 last edited by
        #10

        I was thinking you could model it as a lattice path of n=94, but only after the first two votes come in. But I haven’t figured out how to work the probabilities in.

        Only non-witches get due process.

        • Cotton Mather, Salem Massachusetts, 1692
        1 Reply Last reply
        • J Offline
          J Offline
          jon-nyc
          wrote on 12 Oct 2020, 12:20 last edited by
          #11

          That seems not quite right either, because you could go ‘off’ the path in K’s favor and return to it .

          Only non-witches get due process.

          • Cotton Mather, Salem Massachusetts, 1692
          1 Reply Last reply
          • J Offline
            J Offline
            jon-nyc
            wrote on 12 Oct 2020, 13:15 last edited by
            #12

            Might be as easy as to start calculating the probabilities at each step and see if it starts to form some recognizable series.

            Only non-witches get due process.

            • Cotton Mather, Salem Massachusetts, 1692
            1 Reply Last reply
            • D Doctor Phibes
              12 Oct 2020, 12:06

              You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.

              K Offline
              K Offline
              Klaus
              wrote on 12 Oct 2020, 15:25 last edited by
              #13

              @Doctor-Phibes said in Puzzle Time - Election Edition:

              You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.

              Yep, thought about that, too. What makes this problem difficult is that it's not a Markov chain: the probabilities change based on previous outcomes.

              A standard example in stochastic processes is that of a drunkard who either takes steps towards a cliff with probability p or the other way with probability 1-p, and then to compute the probability that he will eventually fall over the cliff. But that's simpler because it is a Markov chain, I think.

              1 Reply Last reply
              • K Offline
                K Offline
                Klaus
                wrote on 12 Oct 2020, 15:35 last edited by
                #14

                I think I got it.

                || (105-95) / (105+95) = 5%
                Derivation to follow.
                ||

                1 Reply Last reply
                • K Offline
                  K Offline
                  Klaus
                  wrote on 12 Oct 2020, 15:58 last edited by Klaus 10 Dec 2020, 15:59
                  #15

                  Here's why:

                  ||
                  Let's call a sequence of votes a path.

                  There's a one-to-one correspondence between the paths that start with H and the paths that start with K but lead to a tie.

                  Meaning there are just as many of the former as of the latter.

                  The "successful" paths are the remaining ones.

                  So the probability of being on a successful path is

                  1 - 2*(probability of starting with H).

                  The probability of starting with H is 95/200. Hence

                  1-2*95/200 = (105-95)/(105-95) = 0.05.

                  ||

                  That was way easier than I thought. Which probably means I screwed up 😉

                  1 Reply Last reply
                  • J Offline
                    J Offline
                    jon-nyc
                    wrote on 12 Oct 2020, 15:59 last edited by jon-nyc 10 Dec 2020, 16:00
                    #16

                    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.

                    Only non-witches get due process.

                    • Cotton Mather, Salem Massachusetts, 1692
                    1 Reply Last reply
                    • K Offline
                      K Offline
                      Klaus
                      wrote on 12 Oct 2020, 16:02 last edited by Klaus 10 Dec 2020, 16:02
                      #17

                      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.

                      1 Reply Last reply
                      • J Offline
                        J Offline
                        jon-nyc
                        wrote on 12 Oct 2020, 16:07 last edited by
                        #18

                        No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.

                        Only non-witches get due process.

                        • Cotton Mather, Salem Massachusetts, 1692
                        K 1 Reply Last reply 12 Oct 2020, 16:11
                        • K Offline
                          K Offline
                          Klaus
                          wrote on 12 Oct 2020, 16:08 last edited by Klaus 10 Dec 2020, 16:09
                          #19

                          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).

                          1 Reply Last reply
                          • J jon-nyc
                            12 Oct 2020, 16:07

                            No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.

                            K Offline
                            K Offline
                            Klaus
                            wrote on 12 Oct 2020, 16:11 last edited by
                            #20

                            @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.

                            1 Reply Last reply
                            • K Offline
                              K Offline
                              Klaus
                              wrote on 12 Oct 2020, 16:20 last edited by Klaus
                              #21

                              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
                              KKKHH

                              Only two of these are successful, namely:

                              KKHKH
                              KKKHH

                              2 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

                              1 Reply Last reply
                              • J Offline
                                J Offline
                                jon-nyc
                                wrote on 12 Oct 2020, 16:31 last edited by
                                #22

                                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

                                Only non-witches get due process.

                                • Cotton Mather, Salem Massachusetts, 1692
                                K 1 Reply Last reply 12 Oct 2020, 16:38
                                • J jon-nyc
                                  12 Oct 2020, 16:31

                                  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

                                  K Offline
                                  K Offline
                                  Klaus
                                  wrote on 12 Oct 2020, 16:38 last edited by Klaus 10 Dec 2020, 18:08
                                  #23

                                  @jon-nyc yes, I meant those that start with K but tie at any point later on. Also, nothing ends in a tie since the final result is 105:95.

                                  1 Reply Last reply
                                  • K Offline
                                    K Offline
                                    Klaus
                                    wrote on 13 Oct 2020, 08:44 last edited by Klaus
                                    #24

                                    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.

                                    1 Reply Last reply
                                    • J Offline
                                      J Offline
                                      jon-nyc
                                      wrote on 13 Oct 2020, 13:37 last edited by jon-nyc
                                      #25

                                      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%

                                      Only non-witches get due process.

                                      • Cotton Mather, Salem Massachusetts, 1692
                                      K 1 Reply Last reply 13 Oct 2020, 14:51
                                      • J jon-nyc
                                        13 Oct 2020, 13:37

                                        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%

                                        K Offline
                                        K Offline
                                        Klaus
                                        wrote on 13 Oct 2020, 14:51 last edited by
                                        #26

                                        @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?

                                        1 Reply Last reply
                                        • J Offline
                                          J Offline
                                          jon-nyc
                                          wrote on 13 Oct 2020, 15:05 last edited by jon-nyc
                                          #27

                                          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.

                                          Only non-witches get due process.

                                          • Cotton Mather, Salem Massachusetts, 1692
                                          1 Reply Last reply
                                          Reply
                                          • Reply as topic
                                          Log in to reply
                                          • Oldest to Newest
                                          • Newest to Oldest
                                          • Most Votes

                                          17/30

                                          12 Oct 2020, 16:02


                                          • Login

                                          • Don't have an account? Register

                                          • Login or register to search.
                                          17 out of 30
                                          • First post
                                            17/30
                                            Last post
                                          0
                                          • Categories
                                          • Recent
                                          • Tags
                                          • Popular
                                          • Users
                                          • Groups