A Puzzle is Born Sitting around a poolside table, in the cool air and soft light of a June evening, a few of my old friends and I played a game of Texas Hold ‘Em. While we played we chatted about our times in high school, of our old teachers, friends, and, of course, our times playing poker.

It’s often that a student’s first exposure to rigorous mathematics is through set theory, as originally studied by Georg Cantor. This means we will not treat set theory axiomatically (as in ZF set theory), but rather we will take the definition of a set for granted, and allow any operation to be performed on a set. This will be clear when we present examples, and it will be clear why this is a bad idea when we present paradoxes.

Problem: Show 31.5 = 32.5. “Solution”: Explanation: It appears that by shifting around the pieces of one triangle, we have constructed a second figure which covers less area!

Problem: Show there are finitely many primes. “Solution”: Suppose to the contrary there are infinitely many primes. Let $ P$ be the set of primes, and $ S$ the set of square-free natural numbers (numbers whose prime factorization has no repeated factors). To each square-free number $ n \in S$ there corresponds a subset of primes, specifically the primes which make up $ n$’s prime factorization.

This is the first in a series of “false proofs.” Despite their falsity, they will be part of the Proof Gallery. The reason for putting them there is that often times a false proof gives insight into the nature of the problem domain. We will be careful to choose problems which do so. Problem: Show 1 = 2. “Solution”: Let $ a=b \neq 0$. Then $ a^2 = ab$, and $ a^2 – b^2 = ab – b^2$.

Problem: $ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots = 1$ Solution: Problem: $ \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots = \frac{1}{2}$ Solution: Problem: $ \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \dots = \frac{1}{3}$ Solution: Problem: $ 1 + r + r^2 + \dots = \frac{1}{1-r}$ if $ r < 1$. Solution: This last one follows from similarity of the subsequent trapezoids: the right edge of the teal(ish) trapezoid has length $ r$, and

We assume the reader is familiar with the concepts of determinism and finite automata, or has read the corresponding primer on this blog. The Mother of All Computers Last time we saw some models for computation, and saw in turn how limited they were.

The first step in studying the sorts of possible computations (and more interestingly, those things which cannot be computed) is to define exactly what we mean by a “computation.” At a high level, this is easy: a computation is simply a function. Given some input, produce the appropriate output. Unfortunately this is much too general. For instance, we could define almost anything we want in terms of functions.

Problem: Prove that for all $ n,k \in \mathbb{N}, k > 1$, we have $$\sum \limits_{i=0}^{n} k^i = \frac{k^{n+1}-1}{k-1}$$ Solution: Representing the numbers in base $ k$, we have that each term of the sum is all 0’s except for a 1 in the $ i$th place. Hence, the sum of all terms is the $ n$-digit number comprised of all 1’s. Multiplying by $ k-1$ gives us the $ n$-digit number where every digit is $ k-1$.

Additional Patterns Last time we left the reader with the assertion that Conway’s game of life does not always stabilize. Specifically, there exist patterns which result in unbounded cell population growth. Although John Conway’s original conjecture was that all patterns eventually stabilize (and offered $50 to anyone who could provide a proof or counterexample), he was proven wrong.

Cellular Automata There is a long history of mathematical models for computation. One very important one is the Turing Machine, which is the foundation of our implementations of actual computers today. On the other end of the spectrum, one of the simpler models of computation (often simply called a system) is a cellular automaton. Surprisingly enough, there are deep connections between the two.