Category Archives: Mathematical problem solving

Counting with martingales

In this post I will provide a gentle introduction to the theory of martingales (also called “fair games”) by way of a beautiful proof, due to Johan Wästlund, that there are precisely n^{n-2} labeled trees on n vertices.

Apertif: a true story

In my early twenties, I appeared on the TV show Jeopardy! That’s not what this story is about, but it’s the reason I found myself in the Resorts Casino in Atlantic City, where the Jeopardy! tryouts were held (Merv Griffin owned both the TV show and the casino). At the time, I had a deep ambivalence (which I still feel) toward gambling: I enjoyed the thrill of betting, but also believed the world would be better off without casinos preying on the poor and vulnerable in our society. I didn’t want to give any money to the casino, but I did want to play a little blackjack, and I wanted to be able to tell my friends that I had won money in Atlantic City. So I hatched what seemed like a failsafe strategy: I would bet $1 at the blackjack table, and if I won I’d collect $1 and leave a winner. If I lost the dollar I had bet in the first round, I’d double my bet to $2 and if I won I’d stop playing and once again leave with a net profit of $1. If I lost, I’d double my bet once again and continue playing. Since I knew the game of blackjack reasonably well, my odds of winning any given hand were pretty close to 50% and my strategy seemed guaranteed to eventually result in walking home with a net profit of $1, which is all I wanted to accomplish. I figured that most people didn’t have the self-discipline to stick with such a strategy, but I was determined.

Here’s what happened: I lost the first hand and doubled my bet to $2. Then I lost again and doubled my bet to $4. Then I lost again. And again. And again. In fact, 7 times in a row, I lost. In my pursuit of a $1 payoff, I had just lost $127. And the problem was, I didn’t have $128 in my wallet to double my bet once again, and my ATM card had a daily limit which I had already just about reached. And frankly, I was unnerved by the extreme unlikeliness of what had just happened. So I tucked my tail between my legs and sheepishly left the casino with a big loss and nothing to show for it except this story. You’re welcome, Merv.

Martingales

Unbeknownst to me, the doubling strategy I employed (which I thought at the time was my own clever invention) has a long history. It has been known for hundreds of years as the “martingale” strategy; it is mentioned, for example, in Giacomo Casanova‘s memoirs, published in 1754 (“I went [to the casino of Venice], taking all the gold I could get, and by means of what in gambling is called the martingale I won three or four times a day during the rest of the carnival.”) Clearly not everyone was as lucky as Casanova, however (in more ways than one). In his 1849 “Mille et un fantômes”, Alexandre Dumas writes, “An old man, who had spent his life looking for a winning formula (martingale), spent the last days of his life putting it into practice, and his last pennies to see it fail. The martingale is as elusive as the soul.” And in his 1853 book “Newcomes: Memoirs of a Most Respectable Family”, William Makepeace Thackeray writes, “You have not played as yet? Do not do so; above all avoid a martingale if you do.” (For the still somewhat murky origins of the word ‘martingale’, see this paper by Roger Mansuy.)

Continue reading →

Complementary sets of natural numbers and Galois connections

In this post, I’d like to discuss a beautiful result about complementary sets of natural numbers due to Lambek and Moser. I first learned about their theorem as a high school student (from Ross Honsberger’s delightful book “Ingenuity in Mathematics”), but it’s only more recently that I learned about the “Galois” connection.

To motivate the discussion, consider the following question. Let F = \{ 0,1,4,9,16,25,\ldots \} be the sequence of squares, and let G = \{ 2,3,5,6,7,8,10,\ldots \} be its complement in {\mathbb N} = \{ 0,1,2,3,\ldots \}. What is the n^{\rm th} term of the sequence G? In other words, can we give a formula for the n^{\rm th} non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the n^{\rm th} non-square is equal to n + \{ \sqrt{n} \}, where \{ x \} denotes the closest integer to x. Similarly, if T = \{ 0,1,3,6,10,\ldots \} denotes the set of triangular numbers, the n^{\rm th} element of the complement of T is equal to n + \{ \sqrt{2n} \}.

Figure by Scott Kim
Continue reading →

Infinitely many primes via generating functions

A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in this paper by Paul Pollack.)

To motivate the proof, and illustrate its working in an (admittedly silly) special case, suppose that there were just two prime numbers, called p and q. Then by the fundamental theorem of arithmetic (i.e., unique factorization into primes) we would have the following identity between generating functions:

\sum_{n=2}^\infty z^n = \sum_{k=1}^\infty z^{kp} + \sum_{k=1}^\infty z^{kq} - \sum_{k=1}^\infty z^{kpq}.

Indeed, there is precisely one term z^n for each integer n \geq 2 on the left-hand side, and the same is true for the right-hand side (consider separately the cases where p \mid n but q \nmid n, q \mid n but p \nmid n, and pq \mid n). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc {\mathbb D} = \{z \in {\mathbb C} \; : \; |z|<1 \}:

\frac{z^2}{1-z} = \frac{z^p}{1-z^p} + \frac{z^q}{1-z^q} - \frac{z^{pq}}{1-z^{pq}}.

This is impossible, however, as we see by letting z approach a primitive pq^{\rm th} root of unity, since each term stays bounded except for \frac{z^{pq}}{1-z^{pq}}, which tends to infinity.

Continue reading →

The Drunkard’s Walk and Catalan Numbers

In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers.  This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.

In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):

A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is p (and therefore his probability of taking a step toward the cliff is 1-p). What is the probability that the man will eventually fall off the cliff?

Continue reading →