Hall’s Marriage Theorem explained intuitively

December 21, 2013

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 2n teams play in a round-robin tournament. Over a period of 2n-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.

Solution

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

March 6, 2012

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

June 29, 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

May 20, 2011

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)

December 12, 2010

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

October 22, 2010

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

September 3, 2010

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!}}

Simplifying:

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


Follow

Get every new post delivered to your Inbox.

Join 69 other followers