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.