Ponder This Challenge - April 2014 - 1D version of the 2048 game

Ponder This Challenge:

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

Solution

• Click here to view the solution

  The bottom line answer for the expected value of the maximum number in the array is, for N=5, 937669227/67108864 (which is approximately 13.97).

  Kudus to Christopher Marks who was the first to solve this month's challenge without using programming at all, but rather by merely doing a careful examination of cases.

  Among others, we also received the following solutions:

  A one-line Mathematica solution from Todd Will:

  ave[x_]:=ave[x]=If[Length[x]==5,Max[x],Mean[ave[Prepend[x,#]//.{a_,a_,b___}:>{2a,b}]&/@{2,4}]]

  A small Haskel program from John Tromp:

  import Data.Ratio

  avg :: [Integer] -> Ratio Integer
  avg ps | length ps >= 5 = maximum ps % 1
  avg ps = (avg' (2:ps) + avg' (4:ps)) / 2

  avg' :: [Integer] -> Ratio Integer
  avg' = avg . reduce

  reduce :: [Integer] -> [Integer]
  reduce (a:b:ps) | a == b = reduce (a+b : ps)
  reduce ps = ps

  main = print $ avg []

  And a PARI-GP program from Claus Andersen and David Brink.

  Replace(v)=
  {
  if(#v<2,return(v));
  if(v[#v-1]<>v[#v],return(v));
  Replace(vector(#v-1,i,if(i<#v-1,v[i],v[i]+v[i+1])))
  }

  Next()=
  {
  if(t==0,return());
  if(e[t]==2,
     e[t]=4;L[t]=Replace(concat(if(t>1,L[t-1],[]),4)),
     t--;Next())
  }

  April(n)=
  {
  p=0;
  e=[2];
  L=[[2]];
  t=1;
  s=0;c=0;j=0;
  while(t>0,
  if(#L[t]==n,
     \print(L[t]" "vector(t,i,e[i]));
     j++;p+=vecmax(L[t])/2^t;Next(),
     t++;
     if(#e<t,e=concat(e,0));e[t]=2;
     if(#L<t,L=concat(L,0));L[t]=Replace(concat(L[t-1],2))
  );
  );
  return(p)
  }

  April(1)
  April(2)
  April(3)
  April(4)
  April(5)

  John Snyder sent us a very detailed analysis of the problem. We chose to share his nice graphic representation of the Markov process here:

  Graphic representation of the Markov process by John Snyder

  Oleg Vlasii computed the answer for N=1,2,...,10 and noted the pattern
  A(n) = (F(n)*2^(f(n)-1)+3^f(n))/2^(2^N-N-1)
  where f(n) = 2^(n-1)-1
  and F(n) are integers; but a closed form formula still eludes us.

  ---

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

Solvers

• 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)
• (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)