Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

December 2021 - Challenge

<< November 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


Challenge: 30/11/2021 @ 12:00 PM EST
Solution: 04/01/2022 @ 12:00 PM EST
List Updated: 10/01/2022 @ 12:00 PM EST

People who answered correctly:

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