## 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?

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

## 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”

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$