Positive and recurrent walks

It is rather well-known that the number of up-down walks that start at $0$ and stay nonnegative until ending at $0$ after $2n$ steps is the $n$th Catalan number, $C_n=\frac{1}{n+1}\binom{2n}{n}$. Such paths, in which we either go up by $1$ or down by $1$ at each step and never fall below the $x$-axis, are called Dyck paths. An example for $n=5$ is shown below.

What is not so well-known is that:

The number of up-down walks of length $2n$ that stay nonnegative, but do not necessarily return to $0$ at the end, is simply $\binom{2n}{n}$.

This fact came up in my research a few days ago, and I figured that this had to be a trivial theorem that was easy to prove. Several hours of failed attempts later, I found myself googling “positive walks central binomial coefficients” and came across a wonderful recent paper of M. van Leeuwen.

Symmedians and circumcircles

Classical Euclidean geometry is one of the oldest branches of mathematics, and in my opinion still as beautiful as ever. Here is a cute little geometric gemstone that was introduced to me recently by a fellow staff member at MOSP.

Consider a triangle $ABC$ drawn in the plane. Let $M$ be the midpoint of $BC$, and let $O$ be the circumcenter of triangle $ABC$, that is, the center of the circle $\Omega$ passing through $A$, $B$, and $C$.

Now let $\omega$ the circumcircle of triangle $BOC$, and let $D$ be the point on $\omega$ outside of $ABC$ for which $MD$ is perpendicular to $BC$. Then it turns out that the line $AD$ can be obtained by reflecting the median $AM$ across the angle bisector of angle $A$! This reflection of $AM$ is called a symmedian of the triangle.

How can we go about proving this? Well, it suffices to show that angle $BAD$ is congruent to angle $CAM$. One way to go about showing angle measures are equal is by finding similar triangles. Triangles $AMC$ and $ABD$ look promising; let’s start by calculating angle $ABD$. This is equal to angle $B$ plus angle $CBD$, which is an inscribed angle on circle $\omega$. By the inscribed angle theorem (there is a beautiful interactive demonstration at that link!) angle $CBD$ is equal to angle $DOC$, which is half the arc $BC$ on circle $\Omega$. Thus angle $DOC$, and hence angle $CBD$, is equal to angle $A$ of the triangle.

Olympiad vs. research mathematics

Recently, some interesting discussions on math education and mathematical philosophy have taken place on, of all places, my Facebook wall. Since Facebook is a rather restrictive medium, I feel it’s time to widen the scope of my blog to include such topics.

I am currently sitting in the main common area in our residence halls at the Math Olympiad Summer program (abbreviated MOP) in the middle of Lincoln, Nebraska. It is rather quiet, as the students are all taking their 5th “MOP test” in the last two weeks, and my fellow instructors and graders are either proctoring the tests or preparing more material to teach these brilliant kids.

It got me thinking about a topic that is often discussed among mathematicians and among those in math contest circles: How correlated is mathematical contest ability with mathematical research ability? Does one help or hinder the other? Is the social environment that math competitions create hostile to noncompetitive students, especially women?

Geometry of the real projective plane

I’ll be flying to Nebraska tomorrow to teach at the Math Olympiad Summer Program. One of my more advanced classes will be on projective geometry and how it can help us understand Euclidean geometry. I thought I would share the introduction from my handout, since it is an attempt to demonstrate one of the many reasons projective geometry is such a gemstone:

General projective planes

Let’s start with some general theory. A projective plane is any set $P$, which we call the set of points, and a nonempty collection $L$ of subsets of $P$ called lines, such that the following four axioms hold:

P1: Every pair of distinct points are contained in exactly one line.

P2: Every pair of distinct lines intersect in exactly one point.

P3: There are four distinct points $a,b,c,d\in P$ no three of which lie on a line.

P4: Every line contains at least three points.

Axiom P2 raises some alarms. In Euclidean geometry, we assume that there are parallel lines that never meet, but here, we’re requiring that every pair of lines intersect. So the usual Euclidean plane is not a projective plane.

Teeter-totter transpositions

In attempting to write problems for the USAMO, I came across an interesting variant of Knuth equivalence whose structure is rather intricate.

Suppose we start with the numbers $1,2,3,\ldots,n$ written in a row. At each step, we may choose three adjacent numbers in the sequence, say $a,b,c$, and if either $a\lt b \lt c$ or $c\lt b\lt a$ then we can switch $a$ and $c$. So for instance, we might start with 12345 and change it to 32145. At this point we cannot use the subsequence 2,1,4 to change the 2 and 4, but we can use 1,4,5 and end up with 32541. The question is, how many possible sequences can we end up with after a sequence of such moves? (I call them `teeter-totter moves’, since you can either change three consecutive elements from increasing to decreasing or vice versa.)