Sudoku Variants

I’m finally starting to think about sudoku, and am having a lot of fun with it.

I’m taking an online class on artificial intelligence with udacity, and sudoku is being used to illustrate some ideas used to solve constraint satisfaction problems.

Naturally, before solving sudoku puzzles by using the algorithms described in the online course, I thought about what I could do with a brute force approach, which naturally led me to think about variants of sudoku where brute force is a feasible approach. And that’s what I’ll write about here.

But first, let’s recap the basics. To begin with, what is sudoku?
Continue reading “Sudoku Variants”

Girard’s Theorem

Here’s one of my favorite theorems from geometry, both because of the result itself, and because of the proof I’ll describe in this blog post. I suspect it was much better known when spherical trigonometry used to be part of the standard curriculum, but that was before my time. Now it seems to be forgotten, and if it’s mentioned at all it’s in a differential geometry course as an elementary consequence of the more general and powerful Gauss-Bonnet theorem.

One of the very old and well known results about triangles is that the sum of the angles is equal to \pi (or 180^o if you measure angles in degrees instead of radians, which is almost never done in modern mathematics). Girard’s theorem can be viewed as the analogous result in the context of spherical geometry, where the analogue of line segments in the plane is great circle arcs on the sphere.

Girard’s Theorem For a spherical triangle on a unit sphere (i.e. radius equal to one) with interior angles A,B,C the quantity A+B+C-\pi is equal to the area of the triangle.

The way this is proved nowadays (which is not the proof I’ll discuss later in this post) is by first proving the Gauss-Bonnet theorem. To do that you need to work in the more general context of Riemannian geometry where lines in a plane generalize to geodesics in a surface (or an n dimensional Riemannian manifold if you really want to generalize). And then you need to introduce the concept of curvature.

Once you’ve done all that, you can finally state and prove the Gauss-Bonnet theorem, which says that the quantity A+B+C-\pi (where the curves that make up a triangle are geodesics) is equal to the integral of the curvature over the surface of the triangle. For a unit sphere the curvature is one, and for the plane the curvature is zero, and so the Gauss-Bonnet theorem can be used to prove both results mentioned above.

Just as there’s a much more direct and elementary proof of the result for planar triangles, there’s a much more direct and elementary proof of the result for spherical triangles, and that’s what I’ll write about in this post.

To warm up for the proof, I’d like to discuss the solution to a seemingly unrelated combinatorial problem. It turns out to be very closely related, since an approach to solving it is exactly the same as an approach to proving Girard’s theorem.

Problem Consider all words consisting of three characters a, b,c How many words of length three are there where all three characters occur? Continue reading “Girard’s Theorem”

Sample Variance Intuition

This blog post will focus on the intuition behind the n-1 divisor of the standard variance. No proofs, but lots of context and motivation.

And you’ll be pleased to know that this post is self contained. You don’t need to read either of my previous two posts on sample variance.

For a population X_1, X_2, \ldots , X_N the population variance is defined by

\sigma^2 = \frac{1}{N} \sum\limits_{i=1}^{N} (X_i - \mu)^2 where \mu = \frac{1}{N} \sum\limits_{i=1}^{N} X_i

and for a sample x_1, x_2, \ldots , x_n the sample variance is defined by

s^2 = \frac{1}{n-1} \sum\limits_{i=1}^{n} (x_i - \overline{x})^2 where \overline{x} = \frac{1}{n} \sum\limits_{i=1}^{n} x_i

And the question is “why doesn’t the sample variance have the same formula as the population variance?” i.e why isn’t the sample variance given by the direct analogue of the population variance, which is known as the “uncorrected sample variance”:

{s_n}^2 = \frac{1}{n} \sum\limits_{i=1}^{n} (x_i - \overline{x})^2

For the purpose of building intuition, there’s two facts that I think are extremely important to keep in mind.
Continue reading “Sample Variance Intuition”

Rational and Irrational Values of Powers

Here’s a cute little existence argument that I was exposed to as an undergraduate and have never forgotten. It shows that there must be irrational positive reals \alpha and \beta for which \alpha^\beta is rational. Furthermore, it’s done by showing that one of two very specific pairs of numbers (either \alpha=\sqrt{2}, \beta=\sqrt{2} or \alpha={\sqrt{2}}^{\sqrt{2}}, \beta=\sqrt{2}) satisfies the condition, but without establishing which of the two pairs satisfies the condition.

The argument is elementary. First look at the case \alpha=\sqrt{2}, \beta=\sqrt{2} If \alpha^\beta = {\sqrt{2}}^{\sqrt{2}} is rational, we have an example, and we’re done. If not then {\sqrt{2}}^{\sqrt{2}} must be irrational, and so \alpha^\beta where \alpha = {\sqrt{2}}^{\sqrt{2}} (assumed to be irrational) and \beta=\sqrt{2} is an example of an irrational raised to an irrational. And it’s rational. In fact, it’s 2, because \alpha^\beta =({{\sqrt{2}}^{\sqrt{2}}})^{\sqrt{2}} = {{\sqrt{2}}^{{\sqrt{2}}{\sqrt{2}}}} = {\sqrt{2}}^2 = 2

It’s a great little elementary existence argument, and I think it’s worth being exposed to it. But, it’s also worth knowing that with (much) more advanced techniques we can actually say which of the two choices satisfies the condition Continue reading “Rational and Irrational Values of Powers”

Paradox Without Self Reference

This post is about an elementary result from mathematical logic (due to Stephen Yablo in the early 1990’s) that I think deserves to better known.

I’d always assumed that “Russell-like” logical paradoxes (e.g. the inability to assign either a true or a false value to the statement “this sentence is false”, or to the statement “the collection of collections that don’t contain themselves contains itself”) required circular self-reference. Apparently not, provided you use an infinite number of statements.

The construction is simple: consider an infinite sequence of sentences S_1, S_2, S_3,\ldots where S_i is

S_j is false for all j \textgreater i

If you want to see the details of why this is problematic, it’s in the paper “Paradox Without Self Reference” available at http://www.mit.edu/~yablo/pwsr.pdf But I think it’s more fun to figure it out for yourself, and it’s not that hard. The difficulty was in realizing that the result was possible (I didn’t realize it, and I had more than enough mathematical training to do so before the paper was published), not in proving it.

In you really want to see an argument for why there’s a paradox, I’ll provide one here that’s slightly different in unimportant details only from the one in the paper. Continue reading “Paradox Without Self Reference”