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 options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
April 2014
Inspired by the viral 2048 game (http://en.wikipedia.org/wiki/2048_%28video_game%29) game, this month's question is a simpler one-dimensional version of it. Assume that random independent numbers, either 2 or 4 with a 50% chance each, come in from the right side of a bar with N slots. The numbers are always squeezed to the left and every time two adjacent numbers are the same - they are replaced by their sum. The game ends when all the N slots are occupied - and therefore there is no room for a new number.
What is the expected maximum number in the array when the game ends?
When N=1, the game ends after one round, leaving either 2 or 4 with the same probability and hence the average is 3.
When N=2, the game can reach 8 (for example, when the input is 2, 2, 4, 2, and the result is 8, 2), but can also be stuck with a 4 (such as when the input is 2, 2, 2, and the result is 4, 2).
Computing the average we get 5.5, or 11/2.
What is the average when N=5? Express this value as a quotient of two coprime integers.
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:
03/31/2014 @ 01:00 PM EST
Solution:
05/01/2014 @ 01:00 PM EST
List Updated:
03/31/2014 @ 01:00 PM EST
People who answered correctly:
Antoine Comeau (03/31/2014 07:58 PM EDT)
Adam Daire (03/31/2014 11:06 PM EDT)
Florian Fischer (04/01/2014 12:19 AM EDT)
Oleg Vlasii (04/01/2014 12:51 AM EDT)
Reiner Martin (04/01/2014 03:21 AM EDT)
Christopher Marks (04/01/2014 03:57 AM EDT)
Liubing Yu (04/01/2014 05:53 AM EDT)
Jean-Baptiste Rouquier (04/01/2014 09:19 AM EDT)
Don Dodson (04/01/2014 10:24 AM EDT)
José Eduardo Gaboardi de Carvalho (04/01/2014 10:57 AM EDT)
Claus Andersen & David Brink ( 04/01/2014 01:32 PMEDT)
Todd Will (04/01/2014 02:47 PM EDT)
John Tromp (04/01/2014 02:54 PM EDT)
János Kramár (04/01/2014 03:00 PM EDT)
Andrea Andenna (04/01/2014 04:23 PM EDT)
Zach Wegner (04/01/2014 04:42 PM EDT)
Anatoli Plotnikov (04/01/2014 05:18 PM EDT)
Gilles-Philippe Paillé (04/01/2014 08:33 PM EDT)
Gadi Aleksandrowicz (04/02/2014 02:22 AM EDT)
Matthieu Grouès (04/02/2014 01:59 AM EDT)
David Brink & Claus Andersen (04/02/2014 04:09 AM EDT)
Lorenz Reichel (04/02/2014 05:15 AM EDT)
Chuck Carroll (04/02/2014 05:54 AM EDT)
Amir Sarid (04/02/2014 06:00 AM EDT)
Mathias Schenker (04/02/2014 08:45 AM EDT)
Alan Murray (04/02/2014 10:39 AM EDT)
Fletcher Dostie (04/02/2014 10:54 AM EDT)
Gilad Weiss (04/02/2014 01:04 PM EDT)
David Friedman (04/02/2014 01:43 PM EDT)
Igor Novak (04/02/2014 04:43 PM EDT)
Gil Citro (04/02/2014 07:19 PM EDT)
Rami Pearl (04/03/2014 12:52 AM EDT)
Dan Dima(04/03/2014 08:17 AM EDT)
Christian Blatter (04/03/2014 09:48 AM EDT)
Michael Schuresko (04/03/2014 11:44 AM EDT)
Radu-Alexandru Todor (04/03/2014 05:28 PM EDT)
Peter Gerritson (04/03/2014 07:03 PM EDT)
Alexandre Gilotte (04/03/2014 03:40 PM EDT)
Andrew Gacek (04/03/2014 07:21 PM EDT)
Benjamin Phillabaum (04/03/2014 08:21 PM EDT)
Tony Harrison (04/04/2014 11:23 AM EDT)
Motty Porat (04/04/2014 03:40 PM EDT)
Jackson Burlew (04/04/2014 04:05 PM EDT)
Janos Csorba (04/04/2014 04:57 PM EDT)
Leandro Araújo(04/04/2014 07:59 PM EDT)
Larry Kearney (04/05/2014 05:00 PM EDT)
Hakan Summakoglu (04/06/2014 10:35 AM EDT)
Dan Ismailescu (04/06/2014 10:48 AM EDT)
Clive Tong (04/06/2014 12:09 PM EDT)
Shirish Chinchalkar (04/06/2014 06:03 PM EDT)
Hayk Aleksanyan (04/07/2014 04:56 AM EDT)
Naftali Peles (04/07/2014 07:20 AM EDT)
Kan Shen (04/07/2014 07:47 AM EDT)
Álvaro Begué (04/07/2014 10:14 AM EDT)
Michael Slifker (04/07/2014 01:26 PM EDT)
Joseph DeVincentis (04/07/2014 01:37 PM EDT)
Arthur Breitman (04/07/2014 02:24 PM EDT)
Tom Sirgedas (04/07/2014 05:06 PM EDT)
John Snyder (04/07/2014 05:17 PM EDT)
Sri Mallikarjun J (04/07/2014 07:03 PM EDT)
Deron Stewart (04/08/2014 05:01 PM EDT)
Anoop Ghanwani (04/08/2014 11:36 PM EDT)
Armin Krauss (04/09/2014 02:55 PM EDT)
Victor Chang (04/09/2014 05:21 PM EDT)
Serge Thill (04/10/2014 06:07 AM EDT)
Lawrence Hon (04/10/2014 10:16 AM EDT)
Daniel Bitin (04/11/2014 08:25 AM EDT)
Lv Jianhao (04/11/2014 08:42 AM EDT)
Chris Shannon (04/11/2014 04:38 PM EDT)
Emir Haleva (04/12/2014 01:56 PM EDT)
William Kang (04/13/2014 11:48 AM EDT)
Seongwoo Hong (04/13/2014 02:13 PM EDT)
Tim Cieplowski (04/13/2014 05:21 PM EDT)
Cynthia Beauchemin (04/14/2014 12:47 AM EDT)
Michael Wilms (04/14/2014 01:01 AM EDT)
Fabio Filatrella (04/14/2014 03:23 AM EDT)
Olivier Mercier (04/14/2014 08:38 AM EDT)
Philip Kinlen (04/15/2014 05:05 AM EDT)
Michael Rosola (04/15/2014 04:07 PM EDT)
Joe Clark (04/15/2014 05:02 PM EDT)
Will O'Leary (04/15/2014 09:11 PM EDT)
Balakrishnan Varadarajan (04/15/2014 11:32 PM EDT)
Xianpeishi (04/16/2014 03:22 AM EDT)
Alex Fleischer (04/16/2014 10:59 AM EDT)
Jeong Ho Ha (04/19/2014 08:49 AM EDT)
Jaesung Son (04/19/2014 11:47 AM EDT)
David Yang (04/19/2014 01:26 PM EDT)
Mark Stuckel (04/19/2014 09:15 PM EDT)
Boris Rakus (04/20/2014 03:17 AM EDT)
Nagendra Gulur (04/21/2014 02:00 PM EDT)
Peter Shim (04/21/2014 09:01 PM EDT)
Brian Mathason (04/22/2014 09:14 AM EDT)
Tamir Ganor (04/23/2014 06:57 AM EDT)
Harald Bögeholz (04/23/2014 03:47 PM EDT)
David Greer (04/24/2014 01:15 PM EDT)
Adrian Orzepowski (04/25/2014 02:11 AM EDT)
Ziheng Deng (04/25/2014 06:02 PM EDT)
Ran Raviv (04/25/2014 08:21 PM EDT)
Nyles Heise (04/26/2014 01:03 AM EDT)
Chap Alex (04/26/2014 02:38 AM EDT)
Markus Boettle (04/27/2014 10:06 AM EDT)
Hu Shuai (04/27/2014 01:48 PM EDT)
Philipp Seemann (04/27/2014 05:30 PM EDT)
Stéphane Higueret (04/27/2014 06:48 PM EDT)
Florian Speelman (04/28/2014 04:51 PM EDT)
Tamir Ganor & Shouky Dan (04/30/2014 07:16 AM EDT)
Marcel Caria (04/30/2014 12:11 PM EDT)
Konstantin Dzhigardzhyan (04/30/2014 02:49 PM EDT)
Hyunkee Sung (04/30/2014 04:39 PM EDT)
Bradley H Sherman (04/30/2014 08:19 PM EDT)
Mauro Bampo (04/30/2014 09:34 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.