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

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.


Problem 10 of the 2011 Euclid Math Contest (remix)

April 14, 2011

I wrote the Euclid contest this year two days ago, on tuesday. There were 10 problems, and the tenth problem was a nice geometry problem. Three subproblems with a nice neat triangle on the right, with the subproblems getting progressively harder and harder. As I proceeded with the problem, I couldn’t help but imagine it as a Project Euler problem — instead of finding one such integer triangle, it would ask you to find the sum of the perimeters of all such integer triangles with perimeter less than 10^12 or some large number.

A modified problem

In the above diagram, \angle CAK = 2 \angle KAB and \angle ABC = 2 \angle KAB. Let a = CB, b = AC, c = AB, d = AK, and x = KB. Write an algorithm to find triangles satisfying these conditions where a, b, c are all integers.

Similar triangles

It is difficult to try to find integer triangles with such strange requirements as these. It seems that the line AK is completely unnecessary, but if we take it out, there doesn’t seem to be any way to relate the angle ratios to integer side lengths.

We can prove that \triangle CAK is similar to \triangle ABC. Being an exterior angle, CKA = 3 \theta, and also \angle CAB = 3 \theta. Both of the triangles have an angle of measure 2 \theta and another angle of measure 3 \theta, thus they are similar.

From the similar triangles ratio

\frac{b}{d} = \frac{a}{c}

We can write d in terms of the three sides of the triangle:

d = \frac{bc}{a}

Similarly, the side CK can be written as a-x. Then we have the ratio

\frac{a}{b} = \frac{b}{a-x}

Solving for x allows us to express it in terms of the three sides of the triangle, again:

x = \frac{a^2 - b^2}{a}

Constructing another similar triangle

Our goal here is to relate the lengths a, b, c with a simple equation, which then the problem turns into a number theory problem. Since we can write the lengths d and x in terms of a, b, and c, we can also relate any of a, b, c, d, x in an equation.

Again, there doesn’t seem to be a way to relate all of the variables together, in a way that any solution implies the original angle ratio required — unless we make a construction.

Here we extend AB to F, so that KB = BF and \triangle KBF is an isosceles triangle.

Again, since the exterior angle here is 2 \theta, both \angle BKF = \angle BFK = \theta. Also with this construction, \triangle AKF \sim \triangle KBF, and is also isosceles, hence d = AK = KF.

With this construction, we can write the ratio

\frac{x}{d} = \frac{d}{c+x}

Perfect! Cross multiplying and then substituting in the original sides of the triangles gives

(\frac{a^2-b^2}{a})(c+\frac{a^2-b^2}{a}) = (\frac{bc}{a})^2

Simplifying this gives

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

Number theory magic

Now that we have an equation relating the three side lengths — it’s easy to verify that any three integers satisfying the triangle inequality gives a triangle with the required conditions — we can use number theory to try to generate integers that fit the equation.

If we expand the equation, we get

a^4+a^3 c-2 a^2 b^2-a b^2 c+b^4-b^2 c^2 = 0

It makes sense to solve for c, which can be done using just the quadratic formula:

c = \frac{a^3 - ab^2 \pm \sqrt{(ab^2-a^3)^2 + 4b^2(b^4 + a^4 - 2a^2 b^2)}}{2b^2}

We need the discriminant D — the expression inside the square root — to be a perfect square, where we are allowed to have integer values for a and b. If we can get D to be a perfect square, then c will turn out to be a rational number. Then multiplying all three variables by a constant gives integer values for all three.

So we defined D:

D = (ab^2-a^3)^2 + 4b^2(b^4 + a^4 - 2a^2 b^2)

Expanding this gives

D = a^6 - 7a^2 b^4 + 2 a^4 b^2 + 4b^6

Fortunately, this expression has an interesting factorization:

D = (a^2+4b^2) (a+b)^2 (a-b)^2

Or we can also write

\sqrt{D} = (a+b) (a-b) \sqrt{a^2 + 4b^2}

We’ve simplified this problem to finding values where a^2 + 4b^2 is a perfect square, that is:

a^2 + (2b)^2 = k^2

This is just finding Pythagorean triples where one of the two sides are even! For instance, in the triple (3,4,5), we have a=3 and b=2. However, substituting a=3, b=2 into the quadratic formula gives c=5. This is almost a solution, only that the sides have to satisfy the triangle inequality (two sides have to add up to more than the third side).

The next Pythagorean triple (5,12,13) gives a=5 and b=6. Substituting this in gives c=11/9, which does satisfy the triangle inequality. Multiplying everything by 9 gives a=45, b=54, c=11 as the smallest working combination.

With this method, it is possible to quickly find arbitrarily many such triples, using Pythagorean triples as a starting point (which can be generated quickly with known methods).


Calculus magic

February 20, 2011

You have probably seen some version of this curve at some time or another:

The blue lines are drawn by putting n evenly spaced points in the interval [0,1] for both the horizontal and vertical axis and connecting them.

As n approaches infinity, the question is, what is the area occupied by the blue lines? The area is clearly finite since the entire shape is bounded by a 1×1 square, but how much of that square is occupied?

Intuitively it might seem that the blue curve is a circle, however that intuition is wrong. In the above diagram, the red curve is the actual circle, and clearly the blue curve is outside the circle. But fortunately the area can be found with some calculus.

If we choose some point (a,0) on the x-axis, then obviously that point is connected to point (0,1-a) on the y-axis. The slope of this line is \frac{a-1}{a} and the equation of this line is y=\frac{a-1}{a}x+1-a. More conveniently, we can this expression as g(a,x), intuitively the line formed when we choose a as our x-axis point.

Let f(x) be the bounding curve for the blue lines. To find f(x), we want to choose the value a, given x, so that g(a,x) is maximized. To do this, we take the partial derivative \frac{\partial y}{\partial a}:

\frac{\partial y}{\partial a} = x(\frac{a-a+1}{a^2})-1=\frac{x}{a^2}-1

The optimal value of a is the one for which \frac{\partial y}{\partial a}=0, so solving for a we get a=\sqrt{x}. Then we have

f(x) = g(\sqrt{x},x) = x \frac{\sqrt{x}-1}{\sqrt{x}}+1-\sqrt{x}

f(x)= 1+x-2\sqrt{x}

Integrating f(x) from 0 to 1 gives us the answer:

\displaystyle \int_0^1 (1+x-2\sqrt{x}) dx = \frac{1}{6}


CMOQR 2011

January 13, 2011

Here I’m going to go over some of my solutions to the CMOQR (Canadian Math Olympiad Qualifying Repechage) — the qualifying contest for the CMO. Of the 8 questions, I managed to solve the first six but I didn’t manage to get the last two. My solutions here are going to be rather concise.

Problem 1

We know angle BOC so we know angle BAC. Use the cosine law on BOC to get BC=\sqrt{21}. Next use the cosine law again on BAC, but set x = AB and x+1 = AC. Solving for x, we get x=4.

Problem 2

No two of the sums are equal. Therefore no two of a,b,c,d,e are equal, so a<b<c<d<e. (letting abc mean a+b+c to avoid too many plus symbols) in set {a,b,c,d}, we have abc<abd<acd<bcd and similarly bcd<bce<bde<cde, therefore abc<abd<acd<bcd<bce<bde<cde. But we don’t have abe, ace, ade yet so abc<abd<abe<ace<ade<bde<cde.

In either case, abc is the smallest, abd is the second smallest, etc. Then abc=0, abd+3, bde=14, and cde=19. Thus we know d=c+3, b=c-5, e=a+11, so we have {a,b,c,d,e} = {a,c-5,c,c+3,a+11}.

As abc=0, we write everything in terms of c: a=5-2c and e=16-2c. Now we have {5-2c,c-5,c,c+3,16-c}. By substitution, acd=8 and bce=11. Since acd=8, abe=4 (not by deduction, rather it’s the only choice).

From a+b+e=4, we can solve for c and get c=4. It follows that the five numbers are {-3.-1,4,7,8}.

Problem 3

Adding the two equations and factoring gives (x+y+3)(x+y)=18. Solving the quadratic for x+y, we have x+y = -6 or x+y=3. Suppose x+y=-6: substituting back into the original two equations gives x=y=-3. Suppose that x+y=3. Substituting back gives x=0, y=3 or x=3,y=0.

Problem 4

Alphonse can always win. It turns out that he has a ‘strategy stealing’ strategy: first split into 2^{2011} and 5^{2011}. Beryl has to make some move now affecting one of the two piles (never both), and Alphonse can simply make the symmetrical move for the other pile. Obviously Beryl runs out of moves first.

Problem 5

It suffices to prove that for any 6 vertices of a 11-gon, there exists at least one pair of congruent triangles (either there are 6 black vertices, or there are 6 gold vertices). Enumerating all possible congruent triangles in a 11-gon is the same as enumerating all sets of integers adding to 11 — that is, {1,1,9}, {2,2,7} and so on. There are 10 such sets, so any 11 triangles must contain a pair of congruent ones.

Given 6 vertices we can form \binom{6}{3} = 20 triangles, so one pair must be congruent.

Problem 6

Let us write b for angle FBE and a for angle EBD. Obviously triangles ABF and EBF are congruent, so b = \frac{90-a}{2}. We want to prove that 30<a<45 or 22.5<b<30. To prove this we show that for a=30, b=30 then x>y, and then for a=45, b=22.5 then x<y, because then the value for which x=y must exist in that range.

The first case is simple, as if a=b=30 then we have 3 congruent triangles, and x=2y. The second case, EB=ED and (assuming the radius is 1), the area of BED is \frac{1}{2}. The area in the circle is \frac{ \pi}{8} so y = \frac{1}{2} - \frac{\pi}{8}. On the other hand x is twice of FBE minus \frac{\pi}{8} and using some trigonometry we get x = \tan 22.5 - \frac{\pi}{8}. To prove x<y for this case, it is sufficient to prove \tan 22.5 < \frac{1}{2}, which can be done using half angle formulas.


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.


Follow

Get every new post delivered to your Inbox.

Join 72 other followers