2048 and algebra (Part 8)

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:

2048-0

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 showed that the formula for the sum of a finite geometric series can be used to calculate the first sum:

\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2} = 4(2^{15} - 1) = 262,140

Let’s now consider the second (and more complicated) sum, which can be written as

2^3 + 2 \cdot 2^4 + 3 \cdot 2^5 + \cdot + 15 \cdot 2^{17}

For reasons that will become clear shortly, this sum can be written in expanded form as

2^3

+ 2^4 + 2^4

+ 2^5 + 2^5 + 2^5

\vdots

+ 2^{17} + 2^{17} + 2^{17} + \dots + 2^{17}

 Let’s now rearrange the terms of this sum. We will do this by adding along the diagonals instead of along the rows. In this way, the above sum can be rearranged as

2^3 + 2^4 + 2^5 + \dots + 2^{17}

+ 2^4 + 2^5 + \dots + 2^{17}

+ 2^5 + \dots + 2^{17}

\vdots

+ 2^{17}

Each of these new rows (or the original diagonals) is a geometric series and can be calculated using the formula:

2^3 + 2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3

2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^4 (1-2^{14})}{1-2} = 2^{18} - 2^4

2^5 + \dots + 2^{17} = \displaystyle \frac{2^5 (1-2^{13})}{1-2} = 2^{18} - 2^5

\vdots

2^{17} = (2-1) \cdot 2^{17} = 2^{18} - 2^{17}

So, thus far in the calculation, we have established that

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

Simplifying,

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2}=\displaystyle \sum_{n=3}^{17} 2^{18} - \sum_{n=3}^{17} 2^n

The first sum on the right is the sum of a constant being added to itself 15 times:

\displaystyle \sum_{n=3}^{17} 2^{18} = 15 \times 2^{18}

The second sum on the right is yet another geometric series. Indeed, it’s the same geometric  series from the first diagonal above:

\sum_{n=3}^{17} 2^n = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3

Therefore,

\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

Not surprisingly, this matches the sum that was found via direct addition.

Leave a comment

1 Comment

  1. 2048 and algebra: Index | Mean Green Math

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 )

Google photo

You are commenting using your Google 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.

%d bloggers like this: