2048 and algebra (Part 9)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:


In yesterday’s post, we developed a system of two equations in two unknowns to solve for t and f, the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n.

2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we used the formula for the sum of a finite geometric series to calculate the second sum:

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3 = 3,670,024

In this post, I perform this calculation again, except symbolically and more compactly. The key initial steps are writing the series as a double sum and then interchanging the order of summation (much like reversing the order of integration in a double integral). This is a trick that I’ve used again and again in my own research efforts, but it seems that the students that I teach have never learned this trick. Here we go:

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=1}^{15} \sum_{k=1}^n 2^{n+2} = \displaystyle \sum_{k=1}^{15} \sum_{n=k}^{15} 2^{n+2}

The inner sum is a finite geometric series with 15-k+1 terms, common ratio of 2, and initial term 2^{k+2}. Therefore,

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{k=1}^{15} \frac{ 2^{k+2} \left(1 - 2^{15-k+1} \right) }{1 - 2}

= \displaystyle \sum_{k=1}^{15} \left(2^{18} - 2^{k+2} \right)

= \displaystyle \sum_{k=1}^{15} 2^{18} -\sum_{k=1}^{15} 2^{k+2}

 The first sum is merely the sum of a constant. The second sum is another finite geometric series with 15 terms, common ratio of 2, and initial term 2^3. So

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \displaystyle \frac{ 2^3 \left(1 - 2^{15} \right) }{1 - 2}

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left( 2^{18} - 2^3 \right)

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024

One thought on “2048 and algebra (Part 9)

Leave a Reply

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.