Ponder This — April’s Challenge!

You are cordially invited to match wits with some of the best minds in IBM.

Seems some of us can’t see a problem without wanting to take a crack at solving it. Does that sound like you? Good. Forge ahead and ponder this month’s problem.

Ponder This Challenge:

Inspired by the viral 2048 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 left side of a bar with N slots. The numbers are always squeezed to the left and every time two equal 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.

__________

IBM Research will post the names of those who submit a correct, original solution on their website! If you don’t want your name posted then please include such a statement in your submission. Send your submission to the webmaster.

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

Comments

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s