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.

We will orient our dash of Python around the first and simplest problem from ProjectEuler.net. Installing Python To get Python on your computer, go to python’s website and follow the instructions for downloading and installing the interpreter. Most Window’s users can simply click here to download an installer, Mac OS 10.6 – 10.7 users can click here to get their installer, and linux users can (and should) fend for themselves.

So far on this blog we’ve assumed familiarity with the programming languages used (at the time of this writing, this is Mathematica and Java). This is unfair for the mathematicians who have little to no programming experience, and we admit that some readers tend to skim those technical sections with source code.

This primer exists for the background necessary to read our post on RSA encryption, but it also serves as a general primer to number theory. Oh, Numbers, Numbers, Numbers We start with some easy definitions.

This post assumes working knowledge of elementary number theory. Luckily for the non-mathematicians, we cover all required knowledge and notation in our number theory primer. So Three Thousand Years of Number Theory Wasn’t Pointless It’s often tough to come up with concrete applications of pure mathematics. In fact, before computers came along mathematics was used mostly for navigation, astronomy, and war.

Problem: Show that every natural number can be unambiguously described in fewer than twenty words. “Solution”: Suppose to the contrary that not every natural number can be so described. Let $ S$ be the set of all natural numbers which are describable in fewer than twenty words. Consider $ R = \mathbb{N}-S$, the set of all words which cannot be described in fewer than twenty words.

This post assumes familiarity with the terminology and notation of linear algebra, particularly inner product spaces. Fortunately, we have both a beginner’s primer on linear algebra and a follow-up primer on inner products. The Quest We are on a quest to write a program which recognizes images of faces. The general algorithm should be as follows. Get a bunch of sample images of people we want to recognize.