This is a natural follow-up to our first gallery entry on the impossibility of tiling certain chessboards with dominoes. Problem: Suppose we remove two squares from a chessboard which have opposite color. Is it possible to tile the remaining squares with 2-by-1 dominoes?

Note, while the problem below arose in ring theory (specifically, Euclidean domains), the proof itself is elementary, and so the title should not scare away any viewers. In fact, we boil the problem down to something which requires no knowledge of abstract algebra at all. Problem: Show that the ring $ \mathbb{Z}[\sqrt{2}]$ has infinitely many units.

Recalling our series on Conway’s Game of Life, here is an implementation of Life within Life. Unfortunately, it does not “prove” what I hoped it might, so unless a reader has a suggestion on what this demonstration proves, it doesn’t belong in the proof gallery. But it sure is impressive.

Problem: Show 1 = 2 (with calculus) “Solution”: Consider the following: $ 1^2 = 1$ $ 2^2 = 2 + 2$ $ 3^2 = 3 + 3 + 3$ $ \vdots$ $ x^2 = x + x + \dots + x$ ($ x$ times) And since this is true for all values of $ x$, we may take the derivative of both sides, and the equality remains true.

Preamble: This proof is not particularly elegant or insightful. However, it belongs in this gallery for two reasons. First, it is an example of the goal of most mathematics: to classify things. In the same way that all natural numbers can be built up from primes, every group can be built up from simple groups. So if we want to understand all groups, it suffices to understand the simple ones.

or, How I Learned to Love Functional Programming We recognize that not every reader has an appreciation for functional programming. Yet here on this blog, we’ve done most of our work in languages teeming with functional paradigms. It’s time for us to take a stand and shout from the digital mountaintops, “I love functional programming!” In fact, functional programming was part of this author’s inspiration for Math ∩ Programming.

Problem: Determine an arithmetic expression for $ \binom{n}{2}$. Solution: The following picture describes a bijection between the set of yellow dots and the set of pairs of purple dots: In particular, selecting any yellow dots and travelling downward along diagonals gives a unique pair of blue dots. Conversely, picking any pair of blue dots gives a unique yellow dot which is the meeting point (the “peak”) of the inward diagonals.

Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory. Problem: Let $ G$ be an infinite graph. Show that $ G$ is $ n$-colorable if and only if every finite subgraph $ G_0 \subset G$ is $ n$-colorable.

I want to thank all my readers for visiting Math ∩ Programming as often as you do, and doubly thank those who are kind enough to leave a comment. Unfortunately over the next few weeks I may not have time to do work as much on this blog as I have in the past two months.

Problem: Show that $ \sqrt{2}$ is an irrational number (can’t be expressed as a fraction of integers). Solution: Suppose to the contrary that $ \sqrt{2} = a/b$ for integers $ a,b$, and that this representation is fully reduced, so that $ \textup{gcd}(a,b) = 1$. Consider the isosceles right triangle with side length $ b$ and hypotenuse length $ a$, as in the picture on the left.

This post assumes some basic familiarity with Euclidean geometry and linear algebra. Though we do not assume so much knowledge as is contained in our primer on inner product spaces, we will be working with the real Euclidean inner product. For the purpose of this post, it suffices to know about the “dot product” of two vectors. The General Problem One of the main problems in machine learning is to classify data.