2048 and algebra (Part 6)

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 the previous posts, we have 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.

The first equation,

$2t + 4f = \sum T_i$ ,

says that the sum of the tiles that were introduced has to be equal to the sum of the tiles $T_i$ that appear on the final board. Directly adding the sixteen tiles above yields

$2t + 4f = 262,140$ .

This sum can also be calculated using a trick to be discussed in tomorrow’s post.

The second equation,

$2(t - t_0) + \displaystyle \sum_{T_i \ge 8} (\log_2 T_i -2) T_i = P$ ,

says that the total number of points $P$ may be divided into the contributions provided by the tiles on the final board. For example, the 16-tile was formed by joining two 8-tiles for 16 points. Each of those 8-tiles were formed by joining two 4-tiles for another $2 \times 8 = 16$ points. Added together, the 16-tiles results in $2 \times 16 = (\log_2 16 - 2) \times 16 = 32$ points. This analysis does not account for any 4-tiles that were created by adding two 2-tiles. The number of such 2-tiles is $t - t_0$ , where $t_0$ is the number of 2-tiles that appear on the final board (in this case, $t_0 = 0$ ). These additions result in $(t - t_0)/2$ 2-tiles worth $4 \times (t-t_0)/2 = 2(t-t_0)$ points.

For the board above, this equation becomes

$2t + \displaystyle \sum_{T_i \ge 8} (\log_2 T_i - 2) T_i = 3,867,072$

and (for this particular board) the sum can be written more simply as

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

Directly adding the sum $1 \cdot 8 + 2 \cdot 16 + 3 \cdot 32 + \dots + 15 \cdot 131,072$ — and being very careful to double-check the arithmetic — yields the second equation

$2t + 3,670,024 = 3,867,072$

This sum can also be calculated using a trick to be discussed in a future post.

Solving, we find

$2t = 197,048$

$t = 98,524$

Substituting into the first equation:

$2 \times 98,524 + 4f = 262,140$

$197,048 + 4f = 262,140$

$4f = 65,092$

$f = 16,273$

So we conclude that 98,524 2-tiles and 16,273 4-tiles were introduced to the board. Stated another way, about 85.8% of the new tiles were 2-tiles, while about 14.2% of the new tiles were 4-tiles. Also, since two tiles were on the board before any moves were made, a total of $98,524 + 16,273 - 2 = 114,795$ moves were needed to reach the above board.

2048 and algebra (Part 5)

(The above board is the only picture I currently have of reaching 4096 without using an undo — the version of the game that I had at the time permitted two undos per game. I have also reached 8192 in game mode — I was really lucky that day — but I sadly don’t have a screenshot to memorialize the occasion.)

In the previous post, I used two insights to develop of a system of two equations in two unknowns. Let $t$ and $f$ denote the number of 2-tiles and 4-tiles, respectively, that were introduced by the game. The sum of the tiles on the final board must also be the sum of the 2-tiles and 4-tiles that were introduced during the course of the game. Therefore,

$2t + 4f = 3 \times 2 + 3 \times 4 + 2 \times 8 + 16 + 4096$

$2t + 4f = 4146$

Next, we consider how the total of 44,148 points was reached by looking at the final tiles.

Each 8-tile was formed by joining two 4-tiles (for 8 points). Some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 8-tile is worth $1 \times 8$ points, plus 4 times some undetermined number.
Each 16-tile was formed by joining two 8-tiles (for 16 points). Each of those two 8-tiles was formed by joining two 4-tiles (for 8 points for each 8-tile, or $2 \times 8 = 16$ more points). Again, some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 16-tile is worth $16 + 16 = 2 \times 16 = 32$ points, plus 4 times some undetermined number.
There are no 32-tiles on this board. However, to continue the pattern, any 32-tiles are formed by joining two 16-tiles (for 32 points). Each of those two 16-tiles was formed by joining two 8-tiles (for 16 points for each 16-tile, or $2 \times 16 = 32$ more points). Each of those four 8-tiles was formed by joining two 4-tiles (for 8 points for each 8-tile, or $4 \times 8 = 32$ more points). Again, some of those 4-tiles were added by the computer; others were formed by joining two 2-tiles (for 4 points each). So each 16-tile is worth $32 + 32 + 32 = 3 \times 32 = 96$ points, plus 4 times some undetermined number.
By now, the pattern should be clear. Any 64-tile on the board would contribute $4 \times 64 = 256$ points, plus 4 times some undetermined number (as a reminder, the number of 4-tiles formed by adding in the course of making the 64-tile).
Any 128-tile on the board would contribute $5 \times 128 = 640$ points, plus 4 times some undetermined number.
And, in general, a $2^n$ -tile would contribute $(n-2) \times 2^n$ points, plus 4 times some undetermined number.
In particular, when $n = 12$ , a 4096-tile would contribute $10 \times 2^{12} = 40,960$ points, plus 4 times some undetermined number.

In summary, for the above board, there are:

Three 4-tiles (for 4 times some undetermined number),
Two 8-tiles (for $2 \times 8 = 16$ points plus 4 times some undetermined number),
One 16-tile (for $32$ points plus 4 times some undetermined number), and
One 4096-tile (for $40,960$ points plus 4 times some undetermined number).

Adding, this board will have $16 + 32 + 40,960 = 41,008$ , plus 4 times some undetermined number.

What is this undetermined number? It is the number of 4-tiles that are formed by combined two 2-tiles throughout the course of the game thus far. Since $t$ is the number of 2-tiles that have appeared and there are three 2-tiles on the board above, we conclude that $t-3$ 2-tiles have been combined into $(t-3)/2$ 4-tiles throughout the course of the game, resulting in $4 \times (t-3)/2 = 2(t-3)$ points. Therefore, we have the second equation

$41,008 + 2(t-3) = 44,148$

Let’s start solving:

$2(t-3) = 3,140$

$t -3 = 1570$

$t = 1573$

Substituting into the first equation:

$2 \times 1573 + 4f = 4146$

$3146 + 4f = 4146$

$4f = 1000$

$f = 250$

So we conclude that 1573 2-tiles and 250 4-tiles were introduced to the board. Stated another way, about 86.3% of the new tiles were 2-tiles, while about 13.7% of the new tiles were 4-tiles. Also, since two tiles were on the board before any moves were made, a total of $1573 + 250 - 2 = 1821$ moves were needed to reach the above board.

2048 and algebra (Part 4)

In the previous two posts, we developed two key insights (which will be used to develop of system of two equations in two unknowns):

1. Likewise, the 16-tile on the board was formed by adding two 8-tiles (16 points). Each of those 8-tiles was formed by adding two 4-tiles ( $2 \times 8$ , or another 16 points). And those 4-tiles, as well as the final 4-tile on the board, could have been (a) newly introduced by the game or else (b) formed by adding to 2-tiles (thus adding 4 points to the score for each of those 4-tiles).

Let $t$ and $f$ denote the number of 2-tiles and 4-tiles, respectively, that were introduced by the game. Since there are three 2-tiles on this final board, we conclude that $t-3$ 2-tiles were combined to make $(t-3)/2$ 4-tiles. Since each of these 4-tiles adds 4 points, we conclude that the final score of 44 points was obtained as follows:

$16 + 2 \times 8 + 4 \left( \displaystyle \frac{t-3}{2} \right) = 44$

$2(16) + 2(t-3) = 44$

$32 + 2(t-3) = 44$

2. The sum of the tiles on the final board is $2 \times 3 + 4 + 16 = 26$ . This also must be the sum of the 2-tiles and 4-tiles that were introduced during the course of the game. This gives us a second equation:

$2t + 4f = 26$ .

So we have a system of two equations in the two unknowns $t$ and $f$ . This is actually a simple system of equations to solve. Starting with the first equation:

$2(t-3) = 12$

$t -3 = 6$

$t = 9$

Substituting into the second equation:

$2 \times 9 + 4f = 26$

$18 + 4f = 26$

$4f = 8$

$f = 2$

This indeed matches what happened: nine 2-tiles and two 4-tiles were introduced to the board. Furthermore, since two of these tiles were on the initial board, we can conclude that it took nine moves to reach the final board.

2048 and algebra (Part 3)

To study this question, here’s a graphic showing the first nine moves in a typical game of 2048. I’ve included black circles to highlight the new 2-tiles and 4-tiles that are placed with each successive move, and I’ve added dark red ovals to indicate when two tiles are about to be combined in the next move.

In yesterday’s post, I raised one key insight about this game: we can calculate how many points were added for making each tile on the final board.

In today’s post, I raise a second insight. The final board has three 2-tiles, one 4-tile, and one 16-tile. So the sum of the tiles is 6 + 4 + 16, or 26. Also, during the course of the game, nine 2-tiles and two 4-tiles were introduced by the game. The sum of these tiles is 18 + 8, which is also 26. In other words, the sum of the tiles on the final board must equal the sum of the tiles that are introduced during the successive moves of the game.

With these two insights, we will (in tomorrow’s post) set up a system of two equations in two unknowns that will allow us to solve for the number of 2-tiles and 4-tiles that were introduced during the game using only the information on the final board.

2048 and algebra (Part 2)

Clearly, for these 9 moves, the computer introduced nine 2-tiles and two 4-tiles (including the two tiles that began the game in the initial position.) So here’s the question: is there a way, from looking only at the final board (with three 2-tiles, one 4-tile, and one 16-tile) and without looking at any of the prior history of the game, to calculate the number of 2-tiles and 4-tiles that were introduced?

In this post, I introduce the first of two insights that will allow us to answer these questions using algebra. (The second insight will be discussed in tomorrow’s post.) To study this question, let’s begin with the final board (with a score of 44 points) and look at how the tiles on the final board were formed.

Clearly, the three 2-tiles do not contribute anything to the final score. Net contribution: 0 points.

The one 4-tile on the final board (marked with a green circle) hypothetically could have either been a new tile that was introduced by the computer or else formed by combining two 2-tiles. In this case, we see that this particular 4-tile was indeed formed by adding two 2-tiles on Move 8. Net contribution: 4 points.

Handling the one 16-tile on the final board is a little more interesting. To begin, this 16-tile was formed from adding two 8-tiles on Move 8. Net contribution: 16 points.

Each of these 8-tiles were formed by adding two 4-tiles (one on Step 4, the other on Step 7). Net contribution: $2 \times 8$ , or another 16 points.

Two of the four tiles were formed by adding two 2-tiles (on steps 3 and 6). The other two four tiles were introduced by the computer (on steps 0 and 3) and were moved around the board prior to combining with another 4-tile. Net contribution: $2 \times 4$ , or 8 points.

So the total score is 4 points from making 4-tile on the final board and 16+16+8 = 40 points from making the 16-tile on the final board, for a total of 44 points.

This way of thinking about the game… how many points were added for making each tile on the final board… is one of two insights necessary to use algebra to solve for the prior history of the game. After discussing the second insight tomorrow, we’ll be ready to discuss the algebra of 2048.

2048 and algebra (Part 1)

In July and early August of this year, I finally defeated the wildly addicting 2048 game. That’s not to say that I reached the 2048-tile. No, I really defeated the game by reaching the event horizon that literally cannot be surpassed. (This is the usual way I overcome video-game addiction… play the game so much that I get sick of it.)

Over the four weeks or so that it took me to reach the event horizon, I thought of some interesting questions: From looking at only the above screenshot, 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?

It turns out that these questions can be solved with simple algebra. Indeed, if posed in the correct fashion, these questions can be answered using only elementary-school arithmetic. I will discuss the answers to these questions in this series of posts.

It should be noted that the above game board was accomplished in practice mode, and I needed perhaps a couple thousand undos to offset the bad luck of a tile randomly appearing in an unneeded place. I estimate the odds of a skilled player reaching the event horizon in game mode to be about $10^{5000}$ to one. Later in this series, I’ll give my rationale for this estimate.

For what it’s worth, my personal best in game mode was reaching the 8192-tile. I’m convinced that, even with the random placements of the new 2-tiles and 4-tiles, the skilled player can reach the 2048-tile nearly every time and should reach the 4096-tile most of the time. However, reaching the 8192-tile requires more luck than skill, and reaching the 16384-tile requires an extraordinary amount of luck.

Engaging students: Graphing an ellipse

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Samantha Smith. Her topic, from Precalculus: graphing an ellipse.

How has this topic appeared in pop culture?

Football is America’s favorite sport. There is practically a holiday for it: Super Bowl Sunday. I do not think students realize how much math is actually involved in the game of football, from statistics, to yards, the stadium and even the football itself. The video link below explores the shape of the football and of what importance the shape is. As you can see in the picture below, a 2D look of the football shows us that it is in the shape of an ellipse.

The video further explains how the 3D shape (Prolate Spheroid) spins in the air and is aerodynamic. Also, since it is not spherical, it is very unpredictable when it hits the ground. The football can easily change directions at a moments notice. This video is a really cool introduction to graphing an ellipse; it shows what the shape does in the real world. Students could even figure out a graph to represent a football. Overall, this is just a way to engage students in something that they are interested in.

https://www.nbclearn.com/nfl/cuecard/50824 (Geometric Shapes –Spheres, Ellipses, & Prolate Speroids)

D. History: What interesting things can you say about the people who contributed to the discovery and/or development of this topic?

Halley’s Comet has been observed since at least 240 B.C. It could be labeled as the most well-known comet. The comet is named after one of Isaac Newton’ friends, Edmond Halley. Halley worked closely with Newton and used Newton’s laws to calculate how gravitational fields effected comets. Up until this point in history, it was believed that comets traveled in a straight path, passing the Earth only once. Halley discovered that a comet observed in 1682 followed the same path as a comet observed in 1607 and 1531. He predicted the comet would return in 76 years, and it did. Halley’s Comet was last seen in 1986 so, according to Halley’s calculations, it will reappear in 2061.
Halley’s Comet has an elliptical orbit around the sun. It gets as close to the sun as the Earth and as far away from the sun as Pluto. This is an example of how ellipses appear in nature. We could also look at the elliptical orbits of the different planets around the sun. Students have grown up hearing about Newton’s Laws, but this is an actual event that supported and developed those laws in relation to ellipses.

What is Halley’s Comet?

How has this topic appeared in high culture?

Through my research on ellipses, the coolest application I found is Statuary Hall (the Whispering Gallery) in our nation’s capital. The Hall was constructed in the shape of an ellipse. It is said that if you stand at one focal point of the ellipse, you can hear someone whispering across the room at the other focal point because of the acoustical properties of the elliptical shape. The YouTube video below illustrates this phenomena. The gallery used to be a meeting place of the House of Representatives. According to legend, it was John Quincy Adams that discovered the room’s sound properties. He placed his desk at a focus so he could easily hear conversations across the room.

The first link below is a problem students can work out after transitioning from the story of the hall. Given the dimensions of the room, students find the equation of the ellipse that models the room, the foci of the ellipse, and the area of the ellipse. This one topic can cover multiple applications of the elliptical form of Statuary Hall.

Click to access PreAP-PreCal-Log-6.3.pdf

http://www.pleacher.com/mp/mlessons/calculus/appellip.html

Engaging students: Graphing a hyperbola

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Rebekah Bennett. Her topic, from Precalculus: graphing a hyperbola.

Hyperbolas are one of the hardest things to find within the real world. Relating to students, the hyperbola is popularly known as the Hurley symbol; A widely known surf symbol that is now branded on clothes and surf boards. It is also used widely in designs to create patterns on large carpets or flooring. They can also be used when building houses to make sure that a curve on the exterior or interior of the house is mirrored exactly how the buyer wants. Hyperbolas can be found when building graphics for games such as the game roller coaster tycoon. This is a game where several different graphics must be formed so that any type of roller coaster can be created. Also, when playing the wii or xbox Kinect, hyperbolas are used within the design of the system. Since both game systems are based on movement and there are several different types of ways someone can move, the system must have these resources available so that it can read what the person in doing. Hyperbolas are commonly found everywhere with some type of design.

To explore this topic, I would first show the students this video of the roller coaster “Fire and Ice” which is in Orlando, Florida at Universal Studios. This roller coaster was created so that when the two roller coasters go around a loop at the same time, they will never hit, making for a fun, adventurous time. This is what a hyperbola simply is; every point lies within the same ratio from focus to directrix. During the video point out the hyperbolic part of the roller coaster which is shown at the 49-51 second mark.

Now after watching the video, the students would be given about 8 minutes to explore by themselves or with a partner, how to create their own hyperbola. The student can use any resources he/she would like. Once the students have had enough time to explore, the teacher would then have the student watch an instructional video from Kahn Academy.

The video is very useful in teaching students how to graph a hyperbola because the instructor goes through step by step carefully explaining what each part means and why each part is placed where it is in the function. The video is engaging to the students since they don’t have to listen to their teacher say it a million times and then reinforce it. This is also helpful for the teacher because the student hears it from one source and then it is reinforced by the teacher, giving the teacher a second hand because it’s now coming from two sources not just one.

After the video, the students can now split up into groups of at least 3 and create their own “Fire and Ice” roller coaster from scratch. They will have the information from the video to help them know how to create the function and may also ask questions. The student may create their hyperbola roller coaster anyway they would like, using any directrix as well. But keep in mind that you would probably want to tell them it needs to be somewhat realistic or else you could get some crazy ideas. Once all the groups are finished, they will present their roller coaster to the class and be graded by their peers for one grade and then graded by the teacher for participation and correctness.

From previous math courses, the student should already know the terms slope and vertex. The student should’ve already learned how to graph a parabola. Everything that a student uses to graph a parabola is used to graph a hyperbola but yet with more information. Starting from the bottom, a parabola is used because all a hyperbola technically is, is the graph show a parabola and its mirrored image at the same time. From here the student learns about the directrix, which is the axis of symmetry that the parabola follows. The student will now be able to learn about asymptotes which are basically what a directrix is in a hyperbola function. This opens the door to several graphs of limits that the student will learn throughout calculus and higher math classes.

Engaging students: Using right-triangle trigonometry

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Shama Surani. Her topic, from Precalculus: using right-triangle trigonometry.

How could you as a teacher create an activity or project that involves your topic?

A project that Dorathy Scrudder, Sam Smith, and I did that involves right-triangle trigonometry in our PBI class last week, was to have the students to build bridges. Our driving question was “How can we redesign the bridge connecting I-35 and 635?” The students knew that the hypotenuse would be 34 feet, because there were two lanes, twelve feet each, and a shoulder of ten feet that we provided on a worksheet. As a group, they needed to decide on three to four angles between 10-45 degrees, and calculate the sine and cosine of the angle they chose. One particular group used the angle measures of 10°, 20°, 30°, and 40°. They all calculated the sine of their angles to find the height of the triangle, and used cosine to find the width of their triangle by using 34 as their hypotenuse. The picture above is by Sam Smith, and it illustrates the triangles that we wanted the students to calculate.

The students were instructed to make a scale model of a bridge so they were told that 1 feet = 0.5 centimeters. Hence, the students had to divide all their calculations by two. Then, the students had to check their measurements of their group members, and were provided materials such as cardstock, scissors, pipe cleaners, tape, rulers, and protractors in order to construct their bridges. They had to use a ruler to measure out what they found for sine and cosine on the cardstock, and make sure when they connected the line to make the hypotenuse that the hypotenuse had a length of 17 centimeters. After they drew their triangles, they had to use a protractor to verify that the angle they chose is what one of the angles were in the triangle. When our students presented, they were able to communicate what sine and cosine represented, and grasped the concepts.

Below are pictures of the triangles and bridges that one of our groups of students constructed. Overall, the students enjoyed this project, and with some tweaks, I believe this will be an engaging project for right triangle trigonometry.

How does this topic extend what your students should have learned in previous courses?

In previous classes, such in geometry, students should have learned about similar and congruent triangles in addition to triangle congruence such as side-side-side and side-angle-side. They should also have learned if they have a right angle triangle, and they are given two sides, they can find the other side by using the Pythagorean Theorem. The students should also have been exposed to special right triangles such as the 45°-45°-90° triangles and 30°-60°-90° triangles and the relationships to the sides. Right triangle trigonometry extends the ideas of these previous classes. Students know that there must be a 45°-45°-90° triangle has side lengths of 1, 1, and $\sqrt{2}$ which the lengths of 1 subtending the 45° angles. They also are aware that a 30°-60°-90° produces side lengths of 1, $\sqrt{3}$ , and 2, with the side length of 1 subtending the 30°, the length of $\sqrt{3}$ subtending the angle of 60°, and the length of 2 subtending the right angle. So, what happens when there is a right angle triangle, but the other two angles are not 45 degrees or 30 and 60 degrees? This is where right triangle trigonometry comes into play. Students will now be able to calculate the sine, cosine, and tangent and its reciprocal functions for those triangles that are right. Later, this topic will be extended to the unit circle and graphing the trigonometric functions as well as their reciprocal functions and inverse functions.

What are the contributions of various cultures to this topic?

Below are brief descriptions of various cultures that personally interested me.

Early Trigonometry

The Babylonians and Egyptians studied the sides of triangles other than angle measure since the concept of angle measure was not yet discovered. The Babylonian astronomers had detailed records on the rising and setting of stars, the motion of planets, and the solar and lunar eclipses. On the other hand, Egyptians used a primitive form of trigonometry in order to build the pyramids.

Greek Mathematics

Hipparchus of Nicaea, now known as the father of Trigonometry, compiled the first trigonometric table. He was the first one to formulate the corresponding values of arc and chord for a series of angles. Claudius Ptolemy wrote Almagest, which expanded on the ideas of Hipparchus’ ideas of chords in a circle. The Almagest is about astronomy, and astronomy relies heavily on trigonometry.

Indian Mathematics

Influential works called Siddhantas from the 4^th-5^th centry, first defined sine as the modern relationship between half an angle and half a chord. It also defined cosine, versine (which is 1 – cosine), and inverse sine. Aryabhata, an Indian astronomer and mathematician, expanded on the ideas of Siddhantas in another important work known as Aryabhatiya. Both of these works contain the earliest surviving tables of sine and versine values from 0 to 90 degrees, accurate to 4 decimal places. Interestingly enough, the words jya was for sine and kojya for cosine. It is now known as sine and cosine due to a mistranslation.

Islamic Mathematics

Muhammad ibn Mūsā al-Khwārizmī had produced accurate sine and cosine tables in the 9^th century AD. Habash al-Hasib al-Marwazi was the first to produce the table of cotangents in 830 AD. Similarly, Muhammad ibn Jābir al-Harrānī al-Battānī had discovered the reciprocal functions of secant and cosecant. He also produced the first table of cosecants.

Muslim mathematicians were using all six trigonometric functions by the 10^th century. In fact, they developed the method of triangulation which helped out with geography and surveying.

Chinese Mathematics

In China, early forms of trigonometry were not as widely appreciated as it was with the Greeks, Indians, and Muslims. However, Chinese mathematicians needed spherical geometry for calendrical science and astronomical calculations. Guo Shoujing improved the calendar system and Chinese astronomy by using spherical trigonometry in his calculations.

European Mathematics

Regiomontanus treated trigonometry as a distinct mathematical discipline. A student of Copernicus, Georg Joachim Rheticus, was the first one to define all six trigonometric functions in terms of right triangles other than circles in Opus palatinum de triangulis. Valentin Otho finished his work in 1596.

http://en.wikipedia.org/wiki/History_of_trigonometry