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.

Problem: Take a chessboard and cut off two opposite corners. Is it possible to completely tile the remaining board with 2-by-1 dominoes? Solution: Notice that every domino covers exactly one white tile and one black tile. Counting up the colors, we have 32 white and 30 black. Hence, any tiling by 2-by-1 dominoes will leave two extra white squares unaccounted for. So no such tiling is possible. Problem: Cut one corner off a chessboard.

Community Service Mathematics is supposed to be a process of discovery. Definitions, propositions, and methods of proof don’t come from nowhere, although after the fact (when presented in a textbook) they often seem to. As opposed to a textbook, real maths is highly non-linear.