Hall’s Marriage Theorem explained intuitively

Imagine that you have 4 students looking for a job, and 4 positions available to fill. Not all students are equal — some are smarter than others. So the companies want to hire only the smartest students.

(Students are happy with any job they can get)

In this diagram, a bipartite graph, the students are at the top and the companies are at the bottom. A student and a company is connected if the company wants to hire the student. For example, Costco will hire any student, so Costco is connected to Andrei, Bill, Corki, and Danny.

Hall’s Theorem, formally

Hall’s Theorem tells us when we can have the perfect matching:

Suppose G is a bipartite graph with bipartition (A,B). There is a matching that covers A if and only if for every subset X \subseteq A, N(X) \geq |X| where N(X) is the number of neighbors of X.

Huh what?

Hall’s Theorem, intuitively

If you look closely at the diagram, you’ll notice that it doesn’t quite work:

Both Blizzard and Google want to hire Corki and only Corki. But Corki can only work for one company! So the whole thing collapses; the matching fails.

Let’s rewrite Hall’s condition in the context of students and jobs:

For a set of n companies, denote m to mean the number of students that at least one of these companies want. If m \geq n for every set of companies, then a matching is possible. Otherwise, the matching fails.

Here, a set of {Blizzard, Google} consists of 2 companies, but only one student, Corki, is wanted by either company. Since 1 < 2, the matching fails.

Suppose we tell this to Blizzard’s hiring manager, who decides he’ll hire Andrei instead:

Then the matching is successful and every student gets a job. Yay!

Notice that in this example, there are 4 students and 4 jobs. In general, these numbers don’t need to be equal. If we have 10 students and 4 jobs, and we want to fill every job, we can still use Hall’s Theorem. (of course, not every student will get a job)

I like this theorem because it seems so simple. The matching can fail in an obvious way. But if it doesn’t fail in this obvious way, then there’s no way it can fail in a less obvious way — it can’t fail at all.

Application: Putnam 2012 Problem B3

Let’s apply our knowledge to a harder problem. Actually, this problem becomes quite easy if we know to use Hall’s Theorem:

Suppose 2m teams play in a round-robin tournament. Over a period of 2m-1 days, every team plays every other team exactly once. There are no ties.

Show that for each day we can select a winning team, without selecting the same team twice.

Hint: we can view the teams as one half of the bipartite graph, and the days as the other half. A team is connected to a day if it won its match that day.


That’s the hint. Here’s a more detailed solution.

We want to find a matching that covers all the days. Suppose, for contradiction, that this is impossible.

From Hall’s Theorem, there has to be a set of n days, in which there are fewer than n winners in these n days.

Let’s call a team a “loser” if it lost every single game in these n days:

So this poor loser team has lost to n different teams in these n days.

But wait! If it has lost to n teams, then these n teams are winners! Yet we just stated that there are less than n winners. Contradiction — QED.

A CMOQR Problem and why not to Trust Brute Force

Recently I was invited to compete in the CMOQR — a qualifier contest for the Canadian Math Olympiad. The contest consisted of eight problems, and contestants were allowed about a week’s time to submit written solutions via email.

After a few days, I was able to solve all of the problems except one — the second part of the seventh problem:

Seven people participate in a tournament, in which each pair of players play one game, and one player is declared the winner and the other the loser. A triplet ABC is considered cyclic if A beats B, B beats C, and C beats A.

Can you always separate the seven players into two rooms, so that neither room contains a cyclic triplet?

(Note: the first half of the problem asked the same question for six people — and it’s not too difficult to prove that no matter what, we can put them into two rooms so that neither the first nor the second room contains a cyclic triplet.)

But what happens when we add another person? Can we still put four people in one room, and three people in the other, so that neither rooms contain a cyclic triplet?

There are two possibilities here:

  • One, it’s always possible. No matter what combinations of wins and losses have occurred, we can always separate them into two rooms in such a way. To prove this, we’ll need to systematically consider all possible combinations, and one by one, verify that the statement is possible for each of the cases.
  • Two, it’s not always possible. Then there is some counterexample — some combination of wins and losses so that no matter how we separate them, one of the rooms has a cyclic triplet. This is easier to prove: provided that we have the counterexample, we just have to verify that indeed, this case is a counterexample to the statement.

But there’s a problem. Which of the cases does the solution fall into? That is, should we look for a quick solution by counterexample, or look for some mathematical invariant that no counterexample can exist?

Brute Force?

It would be really helpful if we knew the counterexample, or knew for sure what the counterexample was. What if we wrote a computer program to check all the cases? After all, there are only 7 people in the problem, and 7 choose 2 or 21 games played. Then since each game is either won by one player or the other, there are only 2^21 combinations overall (although that does count some duplicates). And 2^21 is slightly over two million cases to check — completely within the bounds of brute force.

So I coded up a possibility-checker. Generate all 2^21 possible arrangements, then for each one, check all possible ways to separate them into two rooms. If it turns out that no matter how we arrange them, a cyclic triplet persists, then display the counterexample. Simple.

I ran the program. It quickly cycled through every possible arrangement, three seconds later exiting without producing a counterexample.

Alright. So there’s no counterexample. I would have to find some nice mathematical invariant, showing that no matter what, there is always some way to group the players so that neither room has a cyclic triplet.

But no such invariant came. I tried several things, but in each attempt couldn’t quite show that the statement held for every case. I knew that there was no counterexample, but I couldn’t prove it. But why? There must be some tricky way to show that no counterexample existed; whatever it was, I couldn’t find it.

Brute Force poorly implemented

Reluctantly, as the deadline came and passed, I submitted my set of solutions without solving the problem. When the solutions came out a week later, the solution to this problem did not contain any tricky way to disprove the counterexample. Instead, what I found was this:

Let A_0 \ldots A_6 be seven players. Let A_i beat A_j when the difference i-j \equiv 1,2,4 \mod 7.

Huh? A counterexample, really? Let’s look at it.

Everything is symmetric — we can ‘cycle’ the players around without changing anything. Also, if we take four players, two of them are consecutive. Let them be A_0 and A_1.

At this point everything falls into place: in any subset of four players, three of them are cyclic.

But wait … my program had not found any counterexamples! And right here is a counterexample! The culprit was obvious (the reader may have foreseen this by now) — of course, there had to be a problem with my program.

Running my code through a debugger, I found a logic error in the routine converting binary numbers to array configurations, meaning that not all possible configurations were tried. As a result, the counterexample slipped through the hole.

After fixing the code, the program found not one, but a total of 7520 (although not necessarily distinct) counterexamples. Most of them had no elegant structure, but the solution’s configuration was among them.

For the interested, here is the fixed code.

When to Start Over?

It is true that the program could have been better written, better debugged. But how could you know whether a counterexample existed and your program didn’t find it, or if no counterexample existed at all?

In hindsight, it seems that writing the brute force program made me worse off than if I hadn’t written it at all. After the program ran without finding a single counterexample, I was confident that no counterexample existed, and set out about proving that, instead of looking for counterexamples or symmetry.

When you are stuck on such a math problem — that is, after making a bit of progress you get stuck — it might be profitable to start over. More often than I would like, I prove a series of neat things, without being able to prove the desired result. Then a look at the solutions manual reveals that a very short solution — one or two steps — lay in the opposite direction.

I’ll put an end to my philosophical musings of the day. Fortunately, the cutoff for the CMOQR was low enough that even without solving every single problem, I was still able to meet the cutoff.

Mathcamp 2011

This year I got invited to Mathcamp, a five week summer camp for “mathematically talented high school students”. The camp will run from July 3 to August 7 this year, in Reed College in Portland, Oregon. This means I will be leaving three days from the time of writing!

The camp is quite expensive — $4000 for normal students — but thankfully, Mathcamp has given me a pretty generous scholarship.

Application to Mathcamp required, among other things, a eight question qualifying quiz. After working on them for one week, I managed to solve six of the problems and half of a seventh problem. One of my favorite problems in the quiz is the third:

In a park there is a merry go round with n seats, and n kids waiting to get on (the kids are evenly spaced around the merry go round). The kids climb on one by one in some order, only taking the seat in front of them and only if the seat is empty; however, each time a kid climbs on, the merry go round rotates counterclockwise by one position. For what values of n is it possible for every kid to get a seat?

My solution goes as follows (I’m assuming that it’s okay to discuss solutions by now as the deadline for submitting solutions has passed more than two months ago):

Let the children be numbered 0,1,2,\cdots,n-1 clockwise and the seats also numbered 0,1,2,\cdots,n-1 so that child 0 is matched with seat 0, and so on.

Let us denote a sequence of moves by c_1,c_2,\cdots,c_n as the sequence that the children get on the ride: for example if c_1,c_2,c_3 = 0,2,1 then child 0 gets on, followed by child 2 then child 1. Each time a child gets on, the seats shift counterclockwise by one, so child c_1 gets onto seat c_1, but child c_2 gets onto seat c_2+1 (modulo n), child c_3 gets onto seat c_3+2, and so on.

Suppose that a particular sequence c_1,\cdots,c_n works at getting every child on the ride. Then c_1,c_2+1,\cdots,c_n+(n-1) must take on every value between 0 and n-1 modulo n. We claim that this is possible when n is odd, and impossible when n is even.

If n is odd, let c_1,\cdots,c_n=0,1,2,\cdots,n-1. We use sums to show that this sequence indeed works, and every child gets a different seat (by every sum being different modulo n). The sums in this case are 0,2,4,\cdots,n-1,n+1,n+3,\cdots,2n-2 so the sums modulo n are 0,2,4,\cdots,n-1,1,3,5,\cdots,n-2. Clearly, this covers every integer modulo n exactly once.

We claim this is impossible when n is even. Suppose the contrary, that this is possible, or in other words, c_1,c_2+1,\cdots,c_n+(n-1) take on every value between 0 and n-1 modulo n. Adding everything up gives

\begin{array}{l} (c_1+c_2+\cdots+c_n)+(1+2+\cdots+(n-1)) \\ \hspace{50 px} \equiv (1+2+\cdots+(n-1)) \mod n \end{array}

But since c_1,c_2,\cdots,c_n is a permutation of 0,\cdots,n-1, their sum is \frac{n(n-1)}{2}. Hence

\frac{n(n-1)}{2} \equiv 0 \mod n

Since n is even, it can be written as 2m for some integer m. Then

\begin{array}{cc} m(2m-1) & \equiv 0 \mod 2m\\ 2m^2-m & \equiv 0 \mod 2m\\ m & \equiv 0 \mod 2m \end{array}

This is a contridiction. Hence the arrangement is impossible when n is even.

Simplifying a sum of consecutive cubes

If you were asked to find the sum of the first four cubes, you would easily be able to do so:

1^3 + 2^3 + 3^3 + 4^3 = 100

But here you may notice something interesting:

1^3 + 2^3 + 3^3 + 4^3 = (1+2+3+4)^2

It turns out that this holds for the sum of the first n cubes for any n — an identity. This identity can be written also as:

\displaystyle \sum_{i=1}^n i^3 = \left( \displaystyle \sum_{i=1}^n i \right)^2

A second way of expressing the same identity simplifies the right side and expresses it as a combination:

\displaystyle \sum_{i=1}^n i^3 = \binom{n+1}{2}^2

A proof by bijection

This identity can be proven combinatorially by noticing that \binom{n+1}{2} is the number of ways to choose 2 elements with repetition from the set {1..n} — the following is a proof by Benjamin and Orrison.

In this proof, we prove the third form of the identity

\displaystyle \sum_{i=1}^n i^3 = \binom{n+1}{2}^2

by constructing one set of size \displaystyle \sum_{i=1}^n i^3 and constructing another set of size \binom{n+1}{2}^2, then constructing a bijection between the two sets.

Let S be the set of ordered 4-pairs (a,b,c,d) such that 1 \leq a,b,c \leq d \leq n — that is, the fourth integer of the pair is greater or equal to each of the other three. If we fix d, the number of possibilities for the variables a,b,c is d^3. As d ranges from 1 to n, the total number of elements in S is equal to \displaystyle \sum_{i=1}^n i^3.

Also, since \binom{n+1}{2} is the number of ways to choose 2 elements with repetition from the set {1..n}, there are \binom{n+1}{2} pairs of integers (h,i) satisfying 1 \leq h \leq i \leq n. So let T be the set of pairs of such pairs ((h,i),(j,k)) where 1 \leq h \leq i \leq n and 1 \leq j \leq k \leq n. The number of elements in T is then \binom{n+1}{2}^2.

We further partition the sets as follows: let S_1 be the subset of S where a \leq b and let S_2 be the subset of S where a > b. Similarly, let T_1 be the subset of T where i \leq k and let T_2 be the subset of T where i > k. We can construct a bijection between S and T by constructing two bijections:

S_1 \leftrightarrow T_1

S_2 \leftrightarrow T_2

The following is trivially a bijection from S_1 to T_1 — the case where a \leq b:

(a,b,c,d) \rightarrow ((a,b),(c,d))

The equivalent bijection from S_2 to T_2 — the case where a > b:

(a,b,c,d) \rightarrow ((c,d),(b,a-1))

We can confirm that the two operations we defined are indeed bijections. This proves the identity.

Solving Mathematical Problems (TOT 2010 Senior, P2)

Often, when looking through solutions of difficult olympiad problems, one would wonder, how are you supposed to come up with something like that? The steps are numerous and each one seems to be the work of a wizard…

One book that I like is Solving Mathematical Problems – A Personal Perspective by Terrence Tao. It’s a problem book, but one that’s slightly different from the others. Instead of merely giving a solution to its problems, it gives some insight on the mathematician’s thoughts as he solves the olympiad problem, such that the steps seem reasonable and logical

Here I’m going to attempt dissecting a recent contest problem I encountered (from the Tournament of Towns contest a few weeks ago) in the style of Tao.

The Problem

On a circular track, 2n cyclists start in the same direction at the same time, all at different but constant speeds. No three cyclists meet at the same time. If two cyclists are at the same position on the track, we say they meet. Prove that by the time every pair of cyclists have met at least once, each cyclist has had at least n^2 meetings.

The problem seems confusing, with so much seemingly unrelated information. We can always start by drawing a picture:

This doesn’t seem to help that much. A circle suggests that the formula for the circumference – C = \pi d might come into play, but looking at the rest of the problem, this seems unlikely, because the problem (especially the result we try to prove) is combinatorial, not geometric.

Let’s go back and look at what we’re given. First, all of the cyclists have constant velocity. So we can write the constant velocities of each of the 2n cyclists as v_1, v_2, \cdots, v_{2n}. We are also given that all of the velocities are different. Then why not simplify things for ourselves by ordering the cyclists in order of increasing velocity, that is, v_1 < v_2 < \cdots < v_{2n}? At the same time, we’ll label the cyclists according to their velocities, so we have C_1, C_2, \cdots, C_{2n}.

What else are we given? The number of cyclists is even, and no three cyclists meet at the same time. As there doesn’t seem to be much we can do to make use of these conditions, we can leave them aside for now.

Now if the length of the track is d, then each cyclist goes around the track every \frac{d}{v} units of time. The event only really ends when every pair of cyclists have met at least once – when does this happen? If we look at any two cyclists – C_i and C_j with C_j being the faster cyclist – the two have a velocity difference of v_j - v_i. Therefore cyclists C_i and C_j will meet every \frac{d}{v_j-v_i} units of time.

But it isn’t over until this happens for every pair of cyclists – \frac{d}{v_j-v_i} might be very large; in other words v_j - v_i could be very small. Since we ordered v_1, v_2, \cdots, v_{2n} in increasing velocity, the smallest value for v_j-v_i should be between two adjacent cyclists. If we let ube the smallest v_j - v_i, then

u = \mathrm{min} \{ v_2-v_1, v_3-v_2, \cdots, v_{2n} - v_{2n-1} \}

Furthermore, we can now say that the event ends at time \frac{d}{u} (from the start).

It seems that we are getting somewhere. But we haven’t really touched the point we’re trying to prove, that each cyclist has had n^2 meetings at this point. Let’s look at pairs of adjacent cyclists. If C_i and C_j are adjacent, then we know by definition that they must meet at least once in the time \frac{d}{u}.

But what about non-adjacent cyclists? If C_i and C_j are separated by exactly one cyclist, C_m, then v_m - v_i \geq u and v_j - v_m \geq u. Adding the two together gives v_j - v_i \geq 2u, so they meet at least once every \frac{d}{2u} units of time. Equivalently, they meet at least twice in the time \frac{d}{u}.

It follows that any pair of cyclists C_i and C_j meet at least every \frac{d}{u(j-i)} units of time, so they meet at least u(j-i) times in the course of the event.

We’re on home stretch here. How can use this new information to show that every cyclist has had n^2 meetings? Let’s look at any arbitrary cyclist, C_i. In the event, he meets at least i-1 times with C_1, at least i-2 times with C_2, at least 2n-i times with C_{2n}, and so on.

So the total number of times he meets is

\frac{i(i-1) + (2n-i)(2n-i+1)}{2}

All we have to do now is simplify:

\frac{i^2 - i + 4n^2 - 2ni + 2n - 2ni + i^2 - i}{2} \\= i^2 - i + 2n^2 - 2ni + n \\ = n^2 + (n-i)^2 + n - i \\ = n^2 + (n-i)(n-i+1) \geq n^2

since n-i and n-i+1 are consecutive integers and their product must be positive. This concludes the proof.

The hockey stick theorem: an animated proof

An interesting theorem related to Pascal’s triangle is the hockey stick theorem or the christmas stocking theorem. This theorem states that the sum of a diagonal in Pascal’s triangle is the element perpendicularly under it (image from Wolfram Mathworld):

So here the sum of the blue numbers , 1+4+10+20+35+56, is equal to the red number, 126. It is easy to see why it’s called the hockey stick theorem – the shape looks like a hockey stick!

An alternative, algebraic formulation of the hockey stick theorem is follows:

\displaystyle\sum_{i=0}^{k} \binom{n+1}{i} = \binom{n+k+1}{k}

But this works in two ways, considering the symmetry of Pascal’s triangle. The flipped version would be:

\displaystyle\sum_{i=0}^{k} \binom{n+1}{n} = \binom{n+k+1}{n+1}

Using Pascal’s identity, it is fairly trivial to prove either identity by induction. Instead I present an intuitive, animated version of the proof:

Stepping Stones: solution with Young tableaux

About a year ago or so, I created a math problem and submitted it to CsTutoringCenter. Titled Stepping Stones, my problem statement went like this:

In a certain river, there are a bunch of stepping stones arranged from one side to the other. A very athletic person can cross the river by jumping on these stepping stones, one at a time.

A stepping stone is big enough for only one person, and the gap between two stepping stones is small enough that it is possible to jump between two adjacent stepping stones.

You are an army commander trying to get a group of soldiers across this river (using these stepping stones). Initially your n soldiers are placed on the first n stepping stones. Your task is to get all of them onto the last n stepping stones.

For example, here are the five possible ways to get a group of two soldiers across a river with five stepping stones:

1) ##---  #-#--  -##--  -#-#-  --##-  --#-#  ---##
2) ##---  #-#--  -##--  -#-#-  -#--#  --#-#  ---##
3) ##---  #-#--  #--#-  -#-#-  --##-  --#-#  ---##
4) ##---  #-#--  #--#-  -#-#-  -#--#  --#-#  ---##
5) ##---  #-#--  #--#-  #---#  -#--#  --#-#  ---##

Let C(k,n) be the number of ways of which n soldiers can cross a river with k stepping stones. In the example, C(5,2) = 5.

Find C(50,12) mod 987654321.

Of course, small values of C(k,n) may be bruteforced by a computer. But C(50,12) is well out of reach of brute force, and substantial mathematics is needed. Or for the lazy, it is possible to find small values by brute force, then look the sequence up on OEIS to find the formula.

Bijection to a matrix representation

We find that any instance of the problem can be represented, or bijected to a special matrix, one where each row and column is increasing.

Let us number the soldiers in the following fashion. Let the rightmost soldier, that is, the soldier first to move, be labelled 1. The soldier behind him is labelled 2, and so on, until the last soldier to move is labelled n. Since the order of soldiers cannot change, each soldier moves exactly k-n times.

Consider a very simple case, with 4 stones and 2 soldiers. One possible way is the first soldier moving twice, followed by the second moving twice.

This move sequence can be represented by [1,1,2,2]. The other sequence, and the only other sequence is [1,2,1,2].

Firstly a sequence like [1,1,1,2] is invalid because in a valid sequence, each soldier has to move the same number of times. Another invalid case is something like [2,1,1,2], since obviously 2 cannot move the first turn. But how can you tell whether [1,2,1,1,2,1,3,2,3,3,2,3] is valid or not?

It isn’t very easy to tell in sequence form. Instead we represent the sequence as a matrix form.

Let’s try some examples first, The sequence [1,1,2,2] in matrix form is:

\begin{array}{cc} 1&2 \\ 3&4 \end{array}

The other sequence, [1,2,1,2], is:

\begin{array}{cc} 1&3 \\ 2&4 \end{array}

Try a more complex example, [1,2,1,1,2,1,3,2,3,3,2,3]:

\begin{array}{cccc} 1&3&4&6 \\ 2&5&8&11 \\ 7&9&10&12 \end{array}

To create the matrix, first have a counter and initialize it to 1; when the first soldier moves, place the counter in the first cell that’s unfilled in the first row, and increment the counter. Now if the second soldier moves, we place the counter in the second row (first unfilled cell), and increment it again, and so on. By the time we’re through all of the soldier moves, the matrix should be nice and rectangular.

Perhaps a different explanation is more intuitive. If A_{3,2} = 7 (where A is the matrix, A_{3,2} means row 3, column 2), that means on move 7, soldier number 3 makes his move number 2.

From this interpretation, several important facts surface. The rows must be increasing, obviously, since if the row is not increasing, say 7 comes before 5, move 7 happened before move 5, which can’t be!

Less obviously, the column has to be increasing. Suppose that in some matrix, A_{2,7}=20, and the cell directly underneath, A_{3,7} = 19. In that case soldier 3 made his move 7 before soldier 2 made his move 7. This results in soldier 3 ahead of soldier 2 (or at least on the same stone)!

So with k stones and n soldiers, the matrix should have n rows and k-n columns. The m \times n cells contain the numbers 1 \ldots mn, while each row and each column is increasing. Our job is to enumerate these matrices, since such a matrix forms a 1-to-1 correspondence to a valid move sequence.

Enumerating matrices with the hook length formula

A Young tableau is an interesting combinatorial object, based on the Ferrers diagram. From a Ferrers diagram of size n, a Young tableau is one where every number from 1 \ldots n is filled in it and all rows and all columns are increasing:

From any cell of a Young tableau, a hook is formed by extending all the way down, and all the way to the right:

The hook length of a cell is the length of its hook (including itself). In the above picture, the hook length is 5. Each cell in the tableau has a hook and a hook length.

The number of valid Young tableaux with a given shape \lambda and with n cells is given by the hook length formula:

N = \frac{n!}{\prod_{x \in \lambda} \mathrm{hook}_x}

A special case of the hook length formula can be used to enumerate rectangular Young tableaux. For instance, we have a 3*4 Young tableau. If we fill each cell with its hook length we get:

The count would then be

\frac{12!}{6 \cdot 5 \cdot 4 \cdot 5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}

Or alternatively,

\frac{12!}{\frac{6!}{3!} \cdot \frac{5!}{2!} \cdot \frac{4!}{1!} \cdot \frac{3!}{0!}}


\frac{12! \cdot 0! \cdot 1! \cdot 2! \cdot 3!}{3! \cdot 4! \cdot 5! \cdot 6!}

This can be generalized to a formula. If we have x rows and y columns:

\frac{(xy)! \prod_{i=1}^{y-1}i!}{\prod_{j=x}^{x+y-1} j!}

For C(k,n), we have n rows and k-n columns, thus by substitution we arrive at our formula:

C(k,n) = \frac{[n(k-n)]! \prod_{i=0}^{k-n-1}i!}{\prod_{j=n}^{k-1}j!}

This can be used to compute C(50,12), trivial to implement in Haskell or any other language.

A group of seventeen people

In a group of 17 people, every person has exactly 4 friends (friendship is mutual). Prove that there are two people who don’t know each other and having no mutual friends.


We use a proof by contradiction. We attempt to construct a graph so that the required proof is false, that is, every pair is either friends or has at least one mutual friend. Then we show that this cannot work, and that something goes wrong when we try to construct such a graph.

Let us represent the entire network of 17 people as a graph with 17 nodes, with a friendship being an edge of the graph. It is given that everyone has 4 friends, and friendship being mutual it follows that the total number of edges, or friendships is \frac{4 \cdot 17}{2} or 34.

Next we count the number of paths of length 2. If indeed every pair of people are friends or friend-of-friends, then every pair should be separated by a path of at most length 2.

In the entire graph there are 17 people, thus 17 \choose 2 or 136 pairs of people. We already know that 34 of these pairs are friendships, so counting that out, we have 102 pairs of people who are not friends, and thus in our case are separated by a path length of exactly 2.

This establishes a lower bound for the number of friend-of-friends, as a friend-of-friend might be linked intermediately in more than one way. Furthermore, a friend-of-friend might already be one of the friends.

Next we count friend-of-friends a different way. How would the graph be so that the number of friend-of-friends is a maximal? Intuitively, there cannot be any immediate diamond-shapes (4-cycles) or triangles (3-cycles). We get a maximal of 12 friend-of-friends like this:

Each of your friends have a friendship with yourself (the central node), plus three other friends. None of the friend-of-friends are coincident.

Suppose that everyone is arranged in this optimal way, such that everyone has 12 friend-of-friends. Then how many paths of length 2 are there in all? It turns out that there are \frac{17 \cdot 12}{2}, or 102 in all.

This establishes an upper bound for the number of total friend-of-friends: a high number cannot be achieved since each node has its optimal configuration to maximize total friend-of-friends.

But we have the lower bound, \binom{17}{2} - 34 = 102, because each pair must be connected; we also have the upper bound, \frac{12 \cdot 17}{2} = 102, because more connections per person is not logically possible. So the lower bound is the upper bound, and the total number of friend-of-friends must be exactly 102.

The number 102 is not as important as what the condition implies. In order for this to succeed, each node must be in the optimal configuration. This means that in the entire graph, there must be no 3- or 4-cycles!

Having restricted the graph considerably, let use start by drawing the graph:

We introduce some new notation here. Let the four branches of the graph so far be considered as clusters A, B, C, D, each with 3 nodes in it. Notice there are exactly 17 nodes in the graph.

Consider the node A1. It ‘needs’ to have 4 connections, so where to? The 5 unlabelled nodes are already full. If we connect it to another node in the A cluster (A2,A3), it forms a 3-cycle (to the unlabelled node), which is not allowed. The only option is to connect it to something from a different cluster, say, D3.

Then what should it connect to? If we choose D2 or D1, we get a 4-cycle, again not allowed. So we must choose something from the B or C cluster.

It then follows that A1 is connected to one node in each of the three clusters. But that is not all.

We temporarily put aside diagonal connections (from A to C, or B to D). Now suppose that A1 is connected to B1, which is connected to C1, then to D1, and finally back to A1. This is a 4-cycle!

The only other option is to, instead of A1, connect to A2 (or A3, but they are currently interchangeable). Following, we connect to B2, C2, D2, A3, B3, C3, D3, and back to A1.

So the other nodes have to be connected in a 12-cycle. If we arrange the nodes on a circle, the connections look like this:

Now we have the diagonal clusters. A1 has to be connected to something in C. Suppose we choose C1. Then we have A1 -> B1 -> C1, which creates a 3-cycle. Similarly, if we choose C3, we get A1 -> D3 -> C3, which again creates a 3-cycle. The only option that avoids this problem is C2.

By this logic, it is possible to ‘force’ all six of the diagonals (this time represented by dotted lines):

So our graph is complete. Now all we have to do is find a pair not being friends, or being friend-of-friends. Easier, we can also find a 3- or 4- cycle, which implies the existence of such a pair.

Now despite our best efforts not to introduce 3- or 4-cycles, we inevitably still have a few (although it’s not entirely obvious at a first glance where they are). Do you see it?

Take A2, for instance. It connects to C3, then to B3, to D1, and back to A2. A 4-cycle! We are finished.

IMO 2010: Problem 5

Problem 5 of the IMO was definitely the most interesting problem in the contest, although one of the harder ones. A mere 37 people out of 511 managed to solve it completely.

What made it so different was that it did not require any particular knowledge on olympiad math theorems, indeed such knowledge would be useless for this problem. It required only creative insight, and quite a bit of it. Technically it’s a combinatorics problem, but no specific combinatorics experience is needed to solve the problem.

Also this problem was the target for a mini-polymath project organized by Terry Tao, which took about two and a half hours to get from start to solving the problem. The solution I’ll give is mostly based on the polymath solution, although I came up with my own finishing steps which I think is less awkward.


In each of six boxes B_1,B_2,B_3,B_4,B_5,B_6 there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box B_j with 1 \leq j \leq 5. Remove one coin from B_j and add two coins to B_{j+1}.

Type 2: Choose a nonempty box B_k with 1 \leq k \leq 4. Remove one coin from B_k and exchange the contents of (possibly empty) boxes B_{k+1} and B_{k+2}.

Determine whether there is a finite sequence of such operations that results in boxes B_1,B_2,B_3,B_4,B_5 being empty and box B_6 containing exactly 2010^{2010^{2010}} coins. (Note that a^{b^c}= a^{(b^c)}.)

Initial observations

It is not entirely obvious how this problem should be approached; thus we will begin by playing with it and jotting down any interesting observations.

We begin with one coin in each box. For convenience, I will express this as

(1,1,1,1,1,1) .

We need to have


Again for convenience, let us substitute

D = 2010^{2010^{2010}}.

Now we can express the two types of moves in our new notation. First, Type 1 moves (we shall call it Move 1):

(a,b) \to (a-1,b+2).

Next, Type 2 moves:

(a,b,c) \to (a-1,c,b).

Notice how applying Move 1 adds one coin to the system as a whole, while Move 2 takes away one coin.

By applying Move 2 over and over, it is easy to remove arbitrarily large amounts of coins from the system (as long as the coins are in the first four boxes).

On the other hand, it isn’t so clear how do add large amounts of coins to the system.

Applying Move 1 adds a coin to the system, so logically adding coins should be done by repeated usage of Move 1.

Given (a,b), applying Move 1 results in (a-1,b+2); applying it again results in (a-2,b+4). We can repeat this as many times as we like, or until the first box is depleted.

This creates a compound move for a pair, executed by applying Move 1 repeatedly:

(a,b) \to (0,b+2a).

What if we apply this on all six boxes? We first get


Next we have


A few more iterations and we will have:


We are far from our target: we have 63 coins and we’re stuck. There doesn’t seem to be any other way to introduce any more coins into the system.

The problem seems hopeless.

Building up a repository of compound moves

We first need a way of getting a large amount of coins into the system. From there is is easy to reduce the coins.

The compound move explained in the previous section is a first step. Let’s call it Compound Move 1:

(a,b) \to (0,b+2a).

The next compound move is less obvious. Suppose that we start with


Applying Move 1 gives us


which, using Compound Move 1, can be used to get


Now we apply Move 2. Using up a coin to switch the two boxes, we have


Or equivalently,


We can repeat this: switching, doubling, switching again, and so on, until the first box is depleted. This gives us


So here we have Compound Move 2:

(a,0,0) \to (0,2^a,0).

This is a lot better than what we had before. However, it’s still a while towards our goal.

With Compound Move 1, each additional coin in the left most box adds 2 coins to the next box.

But with Compound Move 2, each additional coin doubles the result in the next box.

Now this problem has a Towers of Hanoi feel to it. It turns out that we can take this one step further, which, when examined closely, looks remarkably similar to the previous case.

Suppose we have


in four consecutive boxes. Applying Move 1:


Applying Compound Move 2 using the last three boxes, we get


Now we apply Move 2 and switch the boxes:


If we do this again, we get


So, repeating this many times until the left box is empty gives us


No doubt the number we have is sufficiently big now. We will call this move Compound Move 3, which can only be expressed reasonably with Knuth’s up-arrow notation:

(a,0,0,0) \to (0, 2 \uparrow \uparrow a,0,0).

Putting it together

The configuration we want is


which is equivalent to


It’s relatively easy to get most of the boxes empty except for the third. From the starting position, Move 1 gives us


Applying Move 2 three times gives us


Move 1 then gives


We invoke Compound Move 3, getting

(0,0,0,2 \uparrow \uparrow 7,0,0).

Finally we can waste coins by consecutively executing Move 2 until we have


And we’re done.

An additional note

It is easy to show, albeit informally, that 2 \uparrow \uparrow 7 > \frac{D}{4}. If we take the binary log (I’ll write it as \log x) of both sides, we have

2 \uparrow \uparrow 6 > 2010^{2010} \cdot \log 2010 - 2.

It’s okay to ‘throw away’ the 2, considering the magnitude of the numbers. Taking the log again:

2 \uparrow \uparrow 5 > 2010 \cdot \log (2010 \cdot \log 2010).

Considering that 2 \uparrow \uparrow 5 = 2^{65536}, and the right hand side evaluates to just a few thousand, it’s fairly safe to say which is bigger.

Random Math Problems (3)

School finished yesterday. After one exam next week (for math), I’m done grade 10. I’ll probably have more time to write blog posts in the summer.

Problem 1

(from Geometry Revisited)

Prove that in this triangle (a being m+n), that

a(p^2+mn) = b^2m + c^2n

This seems like a really weird thing to prove, but apparently it’s known as Stewart’s theorem and is useful in some places.


Recall the Law of Cosines:

\cos C = \frac{a^2+b^2-c^2}{2ab}

We can apply the Law of Cosines twice to \angle AXB and \angle AXC:

\cos \angle AXB = \frac{p^2+m^2-c^2}{2mp}

\cos \angle AXC = \frac{p^2+n^2-b^2}{2np}

Adding the two together,

\cos \angle AXB + \cos \angle AXC = \frac{p^2+m^2-c^2}{2mp} + \frac{p^2+n^2-b^2}{2np}

Notice that because \cos(\theta) = \cos(180-\theta), the sum of cosines of supplementary angles is 0. Therefore,

\begin{array}{rcl} 0 &=& \frac{p^2+m^2-c^2}{2mp} + \frac{p^2 + n^2 - b^2}{2np} \\ &=& n(p^2+m^2-c^2) + m(p^2 + n^2 - b^2) \\ &=& np^2 + nm^2 - nc^2 + mp^2 + mn^2 - mb^2 \end{array}

Moving the two negative terms to the left hand side and factoring,

\begin{array}{rcl} b^2m + c^2n &=& np^2 + nm^2 + mp^2 + mn^2 \\ &=& n(p^2) + m(p^2) + n(mn) + m(mn) \\ &=& (m+n)(p^2+mn) \end{array}

The result follows:

b^2m + c^2n = a(p^2+mn)

Problem 2

(from the 2010 UVM contest)

How many ways are there to arrange the letters of the word NOODLES, so that the consonants (NDLS) appear in alphabetical order (although not necessarily consecutively)?


The four consonants must appear in the order of D, L, N, S. The three vowels, OOE, must appear somewhere in the five spaces between the consonants:

Thus the answer to the problem is the same as the number of ways to pack OOE into five boxes, a box being able to hold an arbitrary amount of letters, and permutations of letters within a box being counted as distinct.

This is half of the number of ways to pack ABC into five boxes, since there are two O’s in OOE. We will now calculate how many ways there are to pack ABC into five boxes.

We can split up this problem into several cases:

Case 1: All three letters ABC are in the same box. For any box there are 3! = 6 ways to permute ABC, while there are five boxes. The total for this case is 6*5 = 30.

Case 2: The three letters all go in three different boxes. This is simply P(5,3) which is 60.

Case 3: Two of the letters go in a box, while the third letter goes in a different box. This is a little bit tricky, so we break it in a few parts.

First of all we choose the two boxes of the five we use. The number of ways to do this is \binom{5}{2} which is 10. Secondly, if the two boxes are labelled Box 1 and Box 2, we can either put two letters in Box 1 and one in Box 2, or the other way around, giving an additional two ways.

Finally there are 3! or 6 ways to permute the three letters. The final count for case 3 is 10 * 2 * 6 or 120.

The number of ways to pack ABC into five boxes is the sum of the three cases, or 210. The answer to the problem is half of that, 105.

Problem 3

(again from the same UVM contest)

Point P is inside rectangle ABCD. If the distance from P to three corners of the rectangle are 5, 10, and 14, find the distance from P to the forth corner.


We first draw perpendicular lines from P to the four sides of the rectangle and label them a, b, c, and d, like this:

From pythagorean, we find that

b^2 + c^2 = 5^2

b^2 + d^2 = 10^2

a^2 + d^2 = 14^2

As we are looking for the length of DP, we can manipulate the three equations to get a value for a^2 + c^2:

(b^2 + c^2) + (a^2 + d^2)-(b^2+d^2) = a^2+c^2

Finally we can now substitute in real values to find a^2 + c^2:

a^2+c^2 = 5^2 + 14^2 - 10^2 = 121

The line DP can be found by taking a square root, it is 11.

General formula

When three of the four diagonals of a rectangle are known, the forth one can be calculated. Suppose we know m, n, and o. The formula for x is given by:

x = \sqrt{m^2 + n^2 - o^2}

Problem 4

This problem is from the Number Theory chapter of The Art and Craft of Problem Solving.

Prove that

\frac{n^3 + 2n}{n^4 + 3n^2 + 1}

is in lowest terms for all positive integers n.


Another way of saying this problem is that

\textrm{GCD}(n^3 + 2n,n^4 + 3n^2 + 1) = 1

for all positive integers n.

Then there does not exist any integer c, where c > 1, c | n^3+2n and c | n^4+3n^2+1. Supposing c exists, and it divides n^3+2n, we can prove by contradiction that c cannot simultaneously divide n^4+3n^2+1.

If c divides n^3+2n or n(n^2+2), then either c | n or c | n^2+2.

We can rewrite n^4 + 3n^2 + 1:

n^3 + 3n^2 + 1 = n^2(n^2+3) + 1

This way it can be seen that n \perp n^2(n^2+3) , as two consecutive integers are relatively prime.

To show that n^2+2 is also relatively prime, we rewrite it this way:

n^3 + 3n^2 + 1 = (n^2+1)(n^2+2)-1

This shows that, n^2+2 \perp (n^2+1)(n^2+2)-1.

As both n and n^2+2 are relatively prime to n^4 + 3n^2 + 1, it follows that c \perp n^4 + 3n^2 + 1, which is what needs to be shown.