Ponder This Challenge - December 2021 - Galton Board

A Galton board consists of a set of cells (9, in our example) above which are places rows of pins, such that if a ball hits a pin, it as equal probability to fall to the right or to the left. The down-most row has 8 pins, the one above has 7 pins and so forth, up to the first row which consists of one pin and above it a funnel from which balls drop balls on the pins.

The cell where a ball lands is determined by the random sequence of "left/right" choices determined as it fell. For example, to end up in the middle cell exactly four left bounces and four right bounces must occur, or be chosen. There are exactly ${8 \choose 4}=70$ sequences of "L/R" of length 8 with equal number of "L" and "R", and a total of $2^8=256$ such sequences, so the probability of a ball landing in the middle square is around $0.272$. By repeating the experiment with many balls, the distribution of balls in the cells will closely approximate the normal distribution, hence acting as a simply real-life toy example for demonstrating the power of probability.

The Galton board can be made deterministic by replacing each fixed pin by a moveable pin which can be in "LEFT" or "RIGHT" orientation, such that if a ball falls on a "LEFT" pin, the ball goes to the left but the pin changes orientation and becomes "RIGHT", and vice verse.

We can also use static pins which always point to left or right.

The score for a deterministic Galton board is computed as follows: Given a board with $n$ cells and $m$ balls, the balls are dropped into the cells one by one (each changing the pins in its course) and we obtain a distribution $a_1, a_2, \ldots, a_n$ of the balls in the cells (such that $a_1+\cdots+a_n = m$). Now, given a permutation on $n$ elements, $\sigma \in S_n$, the score, dependent on $\sigma$, is computed as $\prod_{k=1}^n(\frac{n\cdot a_{\sigma(k)}}{m})^k$.

You are given the number of cells $n$ and the permutation $\sigma$ and can choose the orientation of the pins in the Galton board before the balls are dropped in order to maximize your score.

The orientation of the pins can be described as a string of length $\frac{n(n-1)}{2}$ of the symbols "L", "R", "<" and ">" where

• "L" means a dynamic pin which drops the ball to the left and then becomes "R"
• "R" means a dynamic pin which drops the ball to the right and then becomes "L"
• "<" means a static pin which drops the ball to the left and remains "<"
• ">" means a static pin which drops the ball to the right and remains ">"

The symbols denote the status of the pins beginning from the top row (single pin) to the bottom row ($n-1$ pins). The permutation $\sigma$ can be described by a list of integers, $[\sigma(1), \sigma(2),\ldots ,\sigma(n)]$

For example, in the case of $n=5$ and $m=15$ balls, the peg string "RRRRRLLRLR" will result in ball distribution [1, 3, 6, 4, 1], and with sigma=[1, 2, 5, 4, 3] the score will be approximately 1.25.

Your goal: For $n=9$ and m=150, Given the permutation [5, 6, 4, 7, 3, 8, 2, 9, 1], find an initial orientation of the pins of the board such that the resulting score is at least 5.

A bonus "*" will be given for finding a score of at least 20 for n=10 m=150 and permutation [4, 8, 2, 7, 10, 6, 3, 9, 1, 5]

Solution

• Click here to view the solution

  Possible solutions for the riddles are

  "RLL<L><<L><RR>><<R>>><<<L>>><<<<R>>>"  
  
  "RL><L><<RL<LRL><<<<R>R>>>L>><R<RL>R><<<R<<<<L"
  

  These specific solutions were found by Andreas Stiller and can be visualized by a nice "Christmas tree":

         R
        L L
       < L >
      < < L >
     < R R > >
    < < R > > >
   < < < L > > >
  < < < < R > > >
  
          R
         L >
        < L >
       < < R L
      < L R L >
     < < < < R >
    R > > > L > >
   < R < R L > R >
  < < < R < < < < L
  

  It was a lucky coincidance that a riddle with such solutions was chosen for December.

Solvers

• *Stéphane Higueret (2/12/2021 11:08 PM IDT)
• *Bertram Felgenhauer (3/12/2021 2:57 AM IDT)
• *Quentin Higueret (3/12/2021 10:16 AM IDT)
• *Christoph Schmidt (6/12/2021 3:50 PM IDT)
• *Alper Halbutogullari (7/12/2021 9:51 AM IDT)
• *Paul Revenant (7/12/2021 1:53 PM IDT)
• Graham Hemsley (7/12/2021 2:57 PM IDT)
• *Reiner Martin (8/12/2021 1:37 PM IDT)
• *Phil Proudman (8/12/2021 1:42 PM IDT)
• *Lazar Ilic (8/12/2021 2:49 PM IDT)
• Daniel Chong Jyh Tar (8/12/2021 6:47 PM IDT)
• *Bert Dobbelaere (8/12/2021 7:11 PM IDT)
• *David Greer (8/12/2021 7:55 PM IDT)
• *Amos Guler (8/12/2021 8:25 PM IDT)
• *Kennedy (8/12/2021 9:23 PM IDT)
• *Dieter Beckerle (8/12/2021 11:15 PM IDT)
• *Gary M. Gerken (9/12/2021 4:34 AM IDT)
• *Christofer Ohlsson (9/12/2021 1:56 PM IDT)
• *Victor Chang (10/12/2021 6:22 AM IDT)
• John Goh (10/12/2021 4:22 PM IDT)
• Chuck Rasbold (11/12/2021 7:57 AM IDT)
• *Peter Moser (11/12/2021 11:35 PM IDT)
• Liubing Yu (12/12/2021 8:37 AM IDT)
• *Dan Dima (12/12/2021 11:24 AM IDT)
• *Dominik Reichl (12/12/2021 12:48 PM IDT)
• *Robert Royals (12/12/2021 8:02 PM IDT)
• Lorenz Reichel (12/12/2021 10:08 PM IDT)
• Harald Bögeholz (13/12/2021 4:47 PM IDT)
• *Tim Walters (15/12/2021 4:19 AM IDT)
• *Chuck Carroll (15/12/2021 7:52 PM IDT)
• *Chris Shannon (16/12/2021 10:17 AM IDT)
• *Thomas Pircher (16/12/2021 11:41 AM IDT)
• *Daniel Bitin (17/12/2021 5:39 PM IDT)
• *Sebastian Bohm & Martí Bosch (17/12/2021 5:40 PM IDT)
• *Stancu Mihai (17/12/2021 10:13 PM IDT)
• *Nicolas Lopez (17/12/2021 11:49 PM IDT)
• *Sri Mallikarjun J (18/12/2021 6:27 PM IDT)
• *Latchezar Christov (18/12/2021 6:52 PM IDT)
• *Clive Tong (18/12/2021 8:46 PM IDT)
• Fabio Michele Negroni (18/12/2021 10:48 PM IDT)
• *Shouky Dan and Tamir Ganor (19/12/2021 8:16 AM IDT)
• *Walter Schmidt (19/12/2021 12:36 PM IDT)
• *Guillaume Escamocher (20/12/2021 7:46 PM IDT)
• *Fabio Filatrella (20/12/2021 9:37 PM IDT)
• *Arunkumar Pandian (22/12/2021 8:13 PM IDT)
• *Nyles Heise (22/12/2021 28:28 PM IDT)
• Andrew Mullins (23/12/2021 4:23 PM IDT)
• *Vladimir Volevich (23/12/2021 4:35 PM IDT)
• *Marco Bellocchi (24/12/2021 6:44 PM IDT)
• *Kedar Karhadkar (27/12/2021 12:07 AM IDT)
• *Stefan Wirth (27/12/2021 8:50 PM IDT)
• *Erik Wünstel (28/12/2021 10:12 PM IDT)
• *Sanandan Swaminathan (29/12/2021 3:27 AM IDT)
• *Andreas Stiller (29/12/2021 8:46 PM IDT)
• *Motty Porat (29/12/2021 9:37 PM IDT)
• *Balakrishnan Varadarajan (31/12/2021 8:19 PM IDT)
• *Andy Greig (1/1/2022 6:32 PM IDT)
• *Radu-Alexandru Todor (2/1/2022 1:53 AM IDT)
• *Li Li (3/1/2022 7:18 AM IDT)
• *Todd Will (3/1/2022 7:56 PM IDT)
• *Kang Jin Cho (6/1/2021 6:28 PM IDT)