IBM Ponder This #192 · April 2014

Inspired by the viral 2048 game (http://en.wikipedia.org/wiki/2048_(video_game)) 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.

Solution

Best opened after a real attempt

To be added.