Transcript for:
ความท้าทายปริศนาประจำเดือนของ IBM Research

Title: IBM Research URL Source: https://research.ibm.com/haifa/ponderthis/challenges/December2021.html Published Time: 2017-02-01 Markdown Content: IBM Research | Ponder This | December 2021 Challenge =============== * [United States](http://www.ibm.com/planetwide/select/selector.html) [IBM](http://www.ibm.com/us-en/?lnk=m) * [Site map](http://www.ibm.com/sitemap/us/en/) [Close](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#) Search Submit * My IBM * [My IBM](https://myibm.ibm.com/?lnk=mmi) * [Log in](https://login.ibm.com/oidc/endpoint/default/authorize?redirect_uri=https%3A%2F%2Fmyibm.ibm.com%2FOIDCHandler.html&response_type=token&client_id=v18LoginProdCI&scope=openid&state=https%3A%2F%2Fresearch.ibm.com%2Fhaifa%2Fponderthis%2Fchallenges%2FDecember2021.html&nonce=8675309) * Site navigation Site navigation [Close](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html?lnk=hm#) * [IBM Research](https://research.ibm.com/?lnk=hm) * [Research areas](https://research.ibm.com/research-areas/?lnk=hm "Research areas") * [Work with us](https://research.ibm.com/work-with-us/?lnk=hm "Work with us") * [Careers](https://research.ibm.com/careers/?lnk=hm "Careers") * [About us](https://research.ibm.com/about/?lnk=hm "About us") * [Locations](https://research.ibm.com/locations/?lnk=hm "Locations") * [Featured projects](https://research.ibm.com/featured/?lnk=hm "Featured projects") * [Blog](https://research.ibm.com/blog/?lnk=hm "Blog") * [IBM Research](http://research.ibm.com/?lnk=hm) * [Research areas](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html?lnk=hm#) ------------------------------------------------------------------------------------------------ * [Work with us](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html?lnk=hm#) ---------------------------------------------------------------------------------------------- * [About us](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html?lnk=hm#) ------------------------------------------------------------------------------------------ * [Blog](https://www.ibm.com/blogs/research/?lnk=hm) * [Products & Solutions](javascript:void();) ------------------------------------------ * [The essentials](https://www.ibm.com/cloud/hybrid?lnk=hmhpmps_bues&lnk2=link) * [Top products & platforms](https://www.ibm.com/products?lnk=hmhpmps_bupr&lnk2=link) * [Industries](https://www.ibm.com/industries?lnk=hmhpmps_buin&lnk2=link) * [Artificial intelligence](https://ibm.com/cloud/ai?lnk=hmhpmps_buai&lnk2=link) * [Automation](https://www.ibm.com/about/automation?lnk=hmhpmps_buau&lnk2=link) * [Blockchain](https://www.ibm.com/blockchain?lnk=hmhpmps_bubc&lnk2=link) * [Business operations](https://www.ibm.com/business-operations?lnk=hmhpmps_buop&lnk2=link) * [Cloud computing](https://www.ibm.com/cloud?lnk=hmhpmps_bucl&lnk2=link) * [Data & Analytics](https://www.ibm.com/analytics?lnk=hmhpmps_buda&lnk2=link) * [IT infrastructure](https://www.ibm.com/it-infrastructure?lnk=hmhpmps_buit&lnk2=link) * [Security](https://www.ibm.com/security?lnk=hmhpmps_buse&lnk2=link) * [Supply chain](https://www.ibm.com/supply-chain?lnk=hmhpmps_busc&lnk2=link) * [View all products](https://www.ibm.com/products?lnk=hmhpmps_buall&lnk2=link) * [Consulting & Services](javascript:void();) ------------------------------------------- * [IBM Consulting](https://www.ibm.com/consulting?lnk=hmhpmco&lnk2=link) * [Business consulting services](https://www.ibm.com/services/business?lnk=hmhpmsc_bups&lnk2=link) * [Design & business strategy](https://www.ibm.com/services/ibmix/?lnk=hmhpmsc_budbs&lnk2=link) * [Hybrid multicloud services](https://www.ibm.com/cloud/services?lnk=hmhpmsc_bups) * [Talent management services](https://www.ibm.com/services/talent-management?lnk=hmhpmsc_buta&lnk2=link) * [Application services](https://www.ibm.com/services/applications?lnk=hmhpmsc_buas&lnk2=link) * [IBM Garage](https://www.ibm.com/garage?lnk=hmhpmsc_buas) * [Security services](https://www.ibm.com/security/services?lnk=hmhpmsc_buse&lnk2=link) * [Technology Support Services](https://www.ibm.com/services/technology-support?lnk=hmhpmsc_busv&lnk2=link) * [Payment plans for Services & Consulting](https://www.ibm.com/financing?lnk=hmhpmsc_bufi&lnk2=link) * [View all services](https://www.ibm.com/services?lnk=hmhpmsc_buall&lnk2=link) * [Learn & Support](javascript:void();) ------------------------------------- * [Support](https://www.ibm.com/mysupport?lnk=hmhpmls_busu&lnk2=link) * [Documentation](https://www.ibm.com/docs/en?lnk=hmhpmls_budc&lnk2=link) * [Developer education](https://developer.ibm.com/?lnk=hmhpmls_bude&lnk2=link) * [Training](https://www.ibm.com/training/?lnk=hmhpmls_butr&lnk2=link) * [Resources](https://www.ibm.com/blogs/?lnk=hmhpmls_bure&lnk2=link) * [What is...](https://www.ibm.com/cloud/learn?lnk=hmhpmls_buwi&lnk2=link) * [Explore more](javascript:void();) ---------------------------------- * [Partner with us](https://www.ibm.com/partners?lnk=hmhpmex_bupa&lnk2=link) * [IBM Research](https://research.ibm.com/?lnk=hmhpmex_bure&lnk2=link) * [About IBM](https://www.ibm.com/about?lnk=hmhpmex_buab) * [COVID-19](https://www.ibm.com/impact/covid-19?lnk=hmhpmex_buco&lnk2=link) [IBM Research](http://research.ibm.com/) * [Research areas](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#) * [Work with us](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#) * [About us](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#) * [Blog](https://www.ibm.com/blogs/research/) * [IBM Research](http://research.ibm.com/) Connect with us: [IBM Research Facebook](https://www.facebook.com/IBM) [IBM Research Twitter](https://twitter.com/ibmresearch) [IBM Research YouTube](https://www.youtube.com/user/IBMLabs?feature=watch) [IBM Research Blog](https://www.ibm.com/blogs/research/) Ponder **This** =============== **Welcome to our monthly puzzles.** You are cordially invited to match wits with some of the best minds in IBM Research. * [Home](https://research.ibm.com/haifa/ponderthis/index.shtml) * [This Month's Challenge](https://research.ibm.com/haifa/ponderthis/challenge.shtml) * [Last Month's Solution](https://research.ibm.com/haifa/ponderthis/solution.shtml) * [RSS](https://research.ibm.com/haifa/ponderthis/rss/index.xml) * [Contact Us](https://research.ibm.com/haifa/ponderthis/contact.shtml) December 2021 - Challenge ------------------------- [<< November](https://research.ibm.com/haifa/ponderthis/challenges/November2021.html) **December** [January \>\>](https://research.ibm.com/haifa/ponderthis/challenges/January2022.html) * * * 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 [[email protected]](mailto:[email protected]?subject=ANSWER:%20December%202021%20Ponder%20This). _If you have any problems you think we might enjoy, please send them in. All replies should be sent to:_ [[email protected]](mailto:[email protected]?Subject=PUZZLE%20SUGGESTION:&Body=Please%20include%20the%20answer%20with%20your%20submission.) **Challenge:** 30/11/2021 @ 12:00 PM EST **[Solution:](https://research.ibm.com/haifa/ponderthis/solutions/December2021.html)** 04/01/2022 @ 12:00 PM EST **List Updated:** 10/01/2022 @ 12:00 PM EST #### People who answered correctly: **\*Stphane 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 Bgeholz** (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 Wnstel** (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) * [Contact IBM](https://www.ibm.com/contact?lnk=flg-cont-usen) * [Privacy](https://www.ibm.com/us-en/privacy?lnk=flg) * [Terms of use](https://www.ibm.com/legal?lnk=flg-tous-usen) * [Accessibility](https://www.ibm.com/able/?lnk=flg-acce-usen) * [Cookie preferences](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#) ### Select a country/region United States - English [](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#)IBM web domains ibm.com, ibm.org, ibm-zcouncil.com, insights-on-business.com, jazz.net, mobilebusinessinsights.com, promontory.com, proveit.com, ptech.org, s81c.com, securityintelligence.com, skillsbuild.org, softlayer.com, storagecommunity.org, think-exchange.com, thoughtsoncloud.com, alphaevents.webcasts.com, ibm-cloud.github.io, ibmbigdatahub.com, bluemix.net, mybluemix.net, ibm.net, ibmcloud.com, galasa.dev, blueworkslive.com, swiss-quantum.ch, blueworkslive.com, cloudant.com, ibm.ie, ibm.fr, ibm.com.br, ibm.co, ibm.ca, community.watsonanalytics.com, datapower.com, skills.yourlearning.ibm.com, bluewolf.com, carbondesignsystem.com  About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your cookiepreferencesoptions. By visiting our website, you agree to our processing of information as described in IBMs[privacy statement](https://www.ibm.com/privacy). To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed[here](https://research.ibm.com/haifa/ponderthis/challenges/December2021.html#truste_domain_list). Accept all More options Cookie Preferences