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 ...

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 ...

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 ...

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. Now, we open Pandrora’s hard drive: Definition: A...

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. Unf...

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 num...

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 of...

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 ...

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-...

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. It took mathematician...

Problem: What is the area of the triangle within the rectangle? Solution: In a moment of inspiration, we draw the following additional line: Now the answer is obvious. Once we split the rectangle into two smaller rectangles, the sides of the triangle become diagonals of their respective rectangles. ...

Problem: Find the sum of the first 1000 natural numbers. Solution: Write the numbers twice as follows: $ \begin{matrix} 1 & + & 2 & + & \dots & + & 999 & + & 1000 \\\ 1000 & + & 999 & + & \dots & + & 2 & + & 1 \end{matrix}$ Summing the numbers in each column, we have: $ 2 (1 + 2 + \dots + 1000) = 10...

Problem: At any party of 1000 people, must there always exist two people at the party who have the same number of friends at the party? For the sake of this problem, one cannot be friends with oneself, and friendship is bidirectional. Solution: This must always happen. Suppose to the contrary, that ...

Problem: 1000 players compete in a tournament. In each round, players are matched with opponents, and the winner proceeds to the next round. If there are an odd number of players in a round, one player chosen at random sits out of that round. What is the total number of games are played in the tourn...

A Bully By Any Other Name From the New York Times: “Shopping online in late July, Clarabelle Rodriguez typed the name of her favorite eyeglass brand into Google’s search bar. In moments, she found the perfect frames — made by a French company called Lafont — on a Web site that looked snazzy and stoo...

Dangling Nodes and Non-Uniqueness Recall where we left off last time. Given a web $ W$ with no dangling nodes, the link matrix for $ W$ has 1 as an eigenvalue, and if the corresponding eigenspace has dimension 1, then any associated eigenvector gives a ranking of the pages in $ W$ which is consisten...

My next book will be Practical Math for Programmers A High-Level Overview of Fully Homomorphic Encryption Searching for Riemann Hypothesis Counterexamples Linear Programming and Healthy Diets Hybrid Images Bezier Curves and Picasso

Story Time Linear algebra was founded around the same time as Calculus (think Leibniz, circa 1700) solely for the purpose of solving general systems of linear equations. The coefficients of a system were written in a grid form, with rows corresponding to equations and columns to the unknown variable...

The Web as a Graph The goal of this post is to assign an “importance score” $ x_i \in [0,1]$ to each of a set of web pages indexed $ v_i$ in a way that consistently captures our idea of which websites are likely to be important. But before we can extract information from the structure of the interne...

The Quest to Capture Speed Companies and researchers spend hundreds of millions of dollars for the fruits of their algorithms. Whether one is indexing websites on the internet for search, folding proteins, or figuring out which warehouse is the most cost-effective to ship a product from, improvement...

Binary Search Binary search is perhaps the first and most basic nontrivial algorithm a student learns. For the mathematicians out there, binary search is a fast procedure to determine whether a sorted list contains a particular element. Here is a pseudocode implementation: # Binary Search: # Given a...

The goal of this post is to use prime numbers to make interesting and asymmetric graphics, and to do so in the context of the web design language CSS. Number Patterns For the longest time numbers have fascinated mathematicians and laymen alike. Patterns in numbers are decidedly simple to recognize, ...

Importance on the Web As a society living in the “Information Age,” it comes as no surprise that we are faced with the task of sorting through vast oceans of content. With the admission that most content is actually junk, we must wisely choose the objects of our analysis. The appropriately named sit...