Ponder This

December 2021 - Challenge

<< November December January >>

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]

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com