Double Angle Trigonometric Formulas

Problem: Derive the double angle identities

\sin(2\theta) = 2\sin(\theta)\cos(\theta)\\ \cos(2\theta) = \cos^2(\theta) - \sin^2(\theta)

Solution: Recall from linear algebra how one rotates a point in the plane. The matrix of rotation (derived by seeing where (1,0) and (0,1) go under a rotation by \theta, and writing those coordinates in the columns) is

A = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix}

Next, note that to rotate a point twice by \theta, we simply multiply the point (as a vector) by A twice. That is, multiply by A^2:

AAv = A^2v

Computing A^2 gives the following matrix:

A^2 = \begin{pmatrix} \cos^2(\theta) - \sin^2(\theta) & -2\sin(\theta)\cos(\theta) \\ 2\sin(\theta)\cos(\theta) & \cos^2(\theta) - \sin^2(\theta) \end{pmatrix}

But rotating twice by \theta is the same as rotating once by 2\theta, so we have the equality:

\begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\ \sin(2\theta) & \cos(2\theta) \end{pmatrix} = \begin{pmatrix} \cos^2(\theta) - \sin^2(\theta) & -2\sin(\theta)\cos(\theta) \\ 2\sin(\theta)\cos(\theta) & \cos^2(\theta) - \sin^2(\theta) \end{pmatrix}

The matrices are equal, so they must be equal entrywise, giving the identities we desire. \square

Discussion: There are (painful, messy) ways to derive these identities by drawing triangles on the unit circle and cultishly chanting “soh-cah-toa.” The key idea in this proof that one might study geometric transformations, and it is a truly mature viewpoint of mathematics. Specifically, over the last two hundred years the field of mathematics has changed focus from the study of mathematical “things” to the study of transformations of mathematical things. This proof is an elementary example of the power such perspective can provide. If you want to be really high-brow, start asking about transformations of transformations of things, and transformations of those transformations, and recurse until you’re doing something original.

False Proof – 2 = 4, As the Limit of an Infinite Power Tower

Problem: Prove that 2 = 4.

Solution: Consider the value of the following infinitely iterated exponent:

\displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}

Let a_n = \sqrt{2} \uparrow \uparrow n, that is, the above power tower where we stop at the n-th term. Then a_n is clearly an increasing sequence, and moreover a_n \leq 4 by a trivial induction argument: \sqrt{2} \leq 4 and if a_n \leq 4 then a_{n+1} = (\sqrt{2})^{a_n} \leq (\sqrt{2})^{4} = 4.

So by basic results in analysis, the sequence of a_n converges to a limit. Let’s call this limit x, and try to solve for it.

It is not hard to see that x is defined by the equation:

\displaystyle (\sqrt{2})^x = x,

simply because the infinite power tower starting at the second level is the same as the infinite power tower starting at the first level. However, we notice that x=2 and x=4 both satisfy this relationship. Hence,

\displaystyle 2 = \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}} = 4

And hence 2=4, as desired. \square

Explanation: The issue here is relatively subtle, but one trained in real analysis should have no trouble spotting the problem.

The first alarm is that we are claiming that the limit of a sequence is not unique, which is always false. Inspecting this argument more closely, we corner the flaw to our claim that x is defined by the equation (\sqrt{2})^x = x. It does, in fact, satisfy this equation, but there is a world of difference between satisfying an equation and being defined by satisfying an equation. One might say that this only makes sense when there is a unique solution to the equation. But as we just saw, there are multiple valid solutions here: 2 and 4 (I don’t immediately see any others; it’s clear no other powers of two will work).

Analogously, one might erroneously say that i is defined by satisfying the equation x^2 = -1, but this does not imply i = -i, since the equation has two differing complex roots. This is a slightly murky analogy, as complex conjugation gives an automorphism of \mathbb{C}. One would reasonably argue that i and -i “play the same role” in this field, while 2 and 4 play wildly different roles as real numbers. But nevertheless, they are not equal simply by virtue of satisfying the same equation.

Moreover, while we said the sequence was bounded from above by 4, an identical argument shows it’s bounded from above by 2. And so one can immediately conclude that the limit of the sequence cannot be 4.

In fact, this infinite tower power x^{x^{\cdot^{\cdot^{\cdot}}}} is continuous as a function, whose domain is the interval [e^{-e}, \sqrt[e]{e}] and whose range is [e^{-1},e]. For more information about interesting number-theoretic properties of infinite power towers, see this paper.

Classic Nintendo Games are NP-Hard

The heroes and heroines of classic Nintendo games.

Problem: Prove that generalized versions of Mario Brothers, Metroid, Donkey Kong, Pokemon, and Legend of Zelda are NP-hard.

Solutionhttp://arxiv.org/pdf/1203.1895v1.pdf

Discussion: Three researchers (including Erik Demaine, a computer science professor at MIT famous for his work with the mathematics of origami) recently finished a paper giving the complexity of a number of classic Nintendo games (the ones I loved to play). All are proven NP-hard, some are shown to be NP-complete, and some are PSPACE-complete. Recall, a problem is NP-hard if an NP-complete problem reduces to it, and a problem is NP-complete if it’s NP-hard and also in NP. As we have just posted a primer on NP-completeness and reduction proofs, this paper is a fun next step for anyone looking for a more detailed reduction proof. A pre-print is available for free on arXiv, and it’s relatively short and easy to read. I’ll summarize his result here, and leave most of the details to the reader. Each game is “generalized” to the task of determining whether one can get from a “start” location to a “finish” location. So the decision problem becomes: given a finite level of a game, can the player move from the starting location to the finishing location? All of the reduction proofs are from 3-Sat, and they all rely on a common framework which can be applied to any platform game. Pictorially, the framework looks like this:

The framework for reducing 3-Sat to platform games.

The player starts in the “start” gadget, which allows one to set up initial state requirements. For instance, in Super Mario Brothers, the start provides you with a mushroom, and you cannot get to the finish without being able to break blocks by jumping under them, which requires the mushroom power-up. Each “variable” gadget requires the player to make a variable assignment in such a way that the player can never return to that gadget to make a different decision. Then each “clause” gadget can be “unlocked” in some way, and each clause gadget can only be visited by the player once the player has chosen a satisfying variable assignment for that clause. Once the player has visited all variable gadgets, he goes to the “check in” area, and can travel back through all of the clauses to the finish if and only if he unlocked every clause. The crossover of the paths in the picture above requires another gadget to ensure that the player cannot switch paths (the details of this are in the paper).

For example, here is the variable gadget described in the paper for The Legend of Zelda, a Link to the Past:

The variable gadget for A Link to the Past.

Note that here we require Link has the hookshot, which can grapple onto chests, but has limited reach. The configuration of the chests requires him to choose a path down one of the two columns at the bottom, and from there he may never return.

Here’s another example. In the classic Super Mario Brothers game, a possible clause gadget is as follows.

The clause gadget for the original Super Mario Brothers.

Note that if the player can only enter through one of the three columns at the top, then the only thing he can do is kick a red koopa shell down so that it breaks the blocks, unlocking the way for Mario to pass underneath at the end. Note that Mario cannot win if he falls from the top ledge (since must always remain large, he can’t fit through a one-tile-high entryway). Further details include the hole at the bottom, in which any stray koopa shell will necessarily fall, but which Mario can easily jump over. We recommend reading the entire paper, because it goes into all of the necessary details of the construction of the gadgets for all of the games.

Future Work

We note that there are some parts of the paper that only got partial results, mostly due to the variation in the game play between the different titles. For instance, the original Super Mario Brothers is known to be NP-complete, but the added ability to pick up koopa shells in later Super Mario Brothers games potentially makes the decision problem more complex, and so it is unknown whether, say, Super Mario World is in NP. We will summarize exactly what is known in the table below. If readers have additions for newer games (for instance, it’s plausible that Super Mario Galaxy could be adapted to fit the same construction as the original Super Mario Bros.), please leave a comment with justification and we can update the table appropriately. I admit my own unfamiliarity with some of the more recent games.

Super Mario Brothers:

Game Title NP-hard in NP PSPACE-complete
Super Mario Bros.
Lost Levels
Super Mario Bros. 2
Super Mario Bros. 3
Super Mario Land
Super Mario World
Land 2: 6 Golden Coins
Super Mario Land 3
Yoshi’s Island
Super Mario 64
Sunshine
New Super Mario Bros.
Galaxy
New Super Mario Bros. Wii
Galaxy 2
Super Mario 3D Land

Legend of Zelda:

Game Title NP-hard in NP PSPACE-complete
The Legend of Zelda
The Adventure of Link
A Link to the Past
Link’s Awakening
Ocarina of Time
Majora’s Mask
Oracle of Seasons
Oracle of Ages
The Wind Waker
Four Swords Adventures
The Minish Cap
Twilight Princess
Phantom Hourglass
Spirit Tracks
Skyward Sword

Donkey Kong:

Game Title NP-hard in NP PSPACE-complete
Donkey Kong
Donkey Kong Country
Donkey Kong Land
Country 2: Diddy’s Kong Quest
Land 2
Country 3: Dixie Kong’s Double trouble!
Land 3
Donkey Kong 64
Donkey Kong Country Returns

Metroid:

Game Title NP-hard in NP PSPACE-complete
Metroid
Metroid II: Return of Samus
Super Metroid
Fusion
Prime
Prime 2: Echoes
Prime Hunters
Prime 3: Corruption
Other M

Pokemon:

Game Title NP-hard in NP PSPACE-complete
All Games
Only trainers

Fundamental Theorem of Algebra (With Picard’s Little Theorem)

This post assumes familiarity with some basic concepts in complex analysis, including continuity and entire (everywhere complex-differentiable) functions. This is likely the simplest proof of the theorem (at least, among those that this author has seen), although it stands on the shoulders of a highly nontrivial theorem.

The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In fact, it seems a new tool in mathematics can prove its worth by being able to prove the fundamental theorem in a different way. This series of proofs of the fundamental theorem also highlights how in mathematics there are many many ways to prove a single theorem, and in re-proving an established theorem we introduce new concepts and strategies. And perhaps most of all, we accentuate the unifying beauty of mathematics.

Problem: Let p(z): \mathbb{C} \to \mathbb{C} be a non-constant polynomial. Prove p(z) has a root in \mathbb{C}.

Solution: Picard’s Little Theorem states that any entire function \mathbb{C} \to \mathbb{C} whose range omits two distinct points must be constant. (See here for a proof sketch, and other notes)

Suppose to the contrary that p has no zero. We claim p also does not achieve some number in the set \left \{ \frac{1}{k} : k \in \mathbb{N} \right \}. Indeed, if it achieved all such values, we claim continuity would provide a zero. First, observe that as p(z) is unbounded for large enough |z|, we may pick a c \in \mathbb{R} such that |p(z)| > 1 whenever |z| > c. Then the points z_k such that p(z) = 1/k all lie within the closed disk of radius c. Because the set is closed and the complex plane is a complete metric space, we see that the sequence of z_k converges to some z, and by continuity p(z) = 0.

In other words, no such sequence of z_k can exist, and hence there is some 1/k omitted in the range of p(z). As polynomials are entire, Picard’s Little theorem applies, and we conclude that p(z) is constant, a contradiction. \square