Posted on December 21, 2013June 19, 2015 in Mathematics

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.

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.

Posted on March 6, 2012 in Mathematics, Programming

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.

Posted on June 29, 2011June 23, 2015 in Mathematics

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.

Posted on April 14, 2011June 23, 2015 in Mathematics

Problem 10 of the 2011 Euclid Math Contest (remix)

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

Posted on February 20, 2011June 26, 2015 in Mathematics

Calculus magic

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

Posted on January 13, 2011 in Mathematics

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

Posted on December 12, 2010June 26, 2015 in Mathematics

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 $u$ be 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.

Posted on November 16, 2010June 26, 2015 in Mathematics

AHSMC 2010 Part I

The first math contest of this year! The AHSMC, has 16 multiple choice problems. 20 free marks, then 5 marks for every correct answer, 2 marks for every blank answer, and 0 for every wrong answer, so possible scores range from 20 to 100. The contest is written in 80 minutes, without a calculator.

The answers I got were: bacb bedd ccbe acbe. I’ll post my solutions here.

Problem 1

The number of positive integers $n$ such that $4n$ has 2 digits is

(a) 21; (b) 22; (c) 23; (d) 24; (e) 25

As $4n$ is between 10 and 99, $3 \leq n \leq 24$ , giving 22 values. The answer is (b).

Problem 2

A 4×6 plot of land is divided into 1×1 lots by fences parallel to the edges (with fences along the edges too). The total length of the fences is

(a) 58; (b) 62; (c) 68; (d) 72; (e) 96

Count the vertical fences separately from the horizontal fences. So let’s suppose the grid is 4 columns and 6 rows, then we have 5 vertical fences and 7 horizontal fences; each vertical fence is 6 units long and each horizontal fence 4 units long.

Therefore the total length is $5 \times 6 + 7 \times 4$ or $58$ . The answer is (a).

Problem 3

The GCD of two positive numbers is 1, and the LCM is 10. If neither of them are 10, their sum is

(a) 3; (b) 6; (c) 7; (d) 11; (e) none of these

Obviously the numbers are 2 and 5, as no other two coprime numbers both divide into 10. So their sum is 7. The answer is (c).

Problem 4

How many non-negative solutions $(x,y)$ are there to the equation $3x+2y=27$ ?

(a) 4; (b) 5; (c) 8; (d) 9; (e) 10

Solving for x, we get $x = \frac{27-2y}{3}$ or $x = 9 - \frac{2y}{3}$ . So in order for x to be non-negative, both $3 | 2y$ and $\frac{2y}{3} \leq 9$ , so then $y \leq 13$ . Of the numbers y between 0 and 13 inclusive, 5 of them are divisible by 3. The answer is (b).

Problem 5

The sequence 1,2,3,4,6,7,8,9,… is obtained by deleting multiples of 5 from the positive integers. What is the 2010th term?

(a) 2511; (b) 2512; (c) 2513; (d) 2514; (e) none of these

Notice that the 4th term is 4, the 5th term is 9, the 12th term is 14, and so on. So the pattern is that the $4n \mathrm{th}$ term is $5n-1$ .

Therefore term 2008 would be $5(502) - 1 = 2509$ ; then term 2009 is 2511 (skipping 2510) and term 2010 is 2512. The answer is (b).

Problem 6

5 people in a building are on floors 1, 2, 3, 21, and 40. In order to minimize their total travel distance, what floor should they get together on?

(a) 18; (b) 19; (c) 20; (d) 21; (e) none of these

Suppose we choose floor 19. Then the total distance is 18+17+16+2+21 or 74. If we choose 17, the total distance is 17+16+15+3+22 or 73, which is smaller.

In fact we can repeat this several times: at floor 3, the total is 2+1+0+18+37 or only 58 floors in total. The answer is (e).

Problem 7

9 holes are arranged in a 3×3 configuration. Two pigeons each choose a hole at random (possible the same one). The probability that they choose two holes on the opposite side of an interior wall is

(a) $\frac{1}{18}$ ; (b) $\frac{1}{9}$ ; (c) $\frac{4}{27}$ ; (d) $\frac{8}{27}$ ; (e) $\frac{1}{3}$

Let the first pigeon choose a random hole. Then we split the problem into 3 cases:

If it’s in one of the 4 corners, then the next pigeon has a $\frac{2}{9}$ chance of landing in the correct spot, so the probability here is $\frac{4}{9} \times \frac{2}{9}$ .
If it’s in one of the 4 edges, then the next pigeon has a $\frac{3}{9}$ chance of landing in the correct spot. This is a probability of $\frac{4}{9} \times \frac{3}{9}$ .
If it’s in the center hole, then the next pigeon may land in 4 possible places, so the probability here is $\frac{1}{9} \times \frac{4}{9}$ .

The total is $\frac{4}{9} \times \frac{2}{9} + \frac{4}{9} \times \frac{3}{9} + \frac{1}{9} \times \frac{4}{9}$ which is equal to $\frac{8}{27}$ . The answer is (d).

Problem 8

The set of real x where $\frac{1}{x} \leq -3 \leq x$ is:

(a) $\{x \leq - \frac{1}{3}\}$ ; (b) $\{-3 \leq x \leq - \frac{1}{3}\}$ ; (c) $\{ -3 \leq x < 0 \}$ ; (d) $\{ - \frac{1}{3} \leq x < 0 \}$ ; (e) none of these

I solved this graphically:

The answer is (d).

Problem 9

In quadrilateral $ABCD$ , $AB || DC$ , $DC = 2AB$ , $\angle ADC = 30^\circ$ , $BCD = 50^\circ$ . M is the midpoint of CD. The measure of $\angle AMB$ is

(a) 80; (b) 90; (c) 100; (d) 110; (e) 120

Because $DC || AB$ and $DM = AB = MC$ , both ABMD and ABCM are parallelograms. Opposite angles in parallelograms are equal, so $\angle MAB = 50^\circ$ , $\angle MBA = 30^\circ$ . Thus $\angle AMB = 100^\circ$ . The answer is (c).

Problem 10

We construct isosceles but non-equilateral triangles with integer side lengths between 1 and 9 inclusive. The number of such non-congruent triangles is

(a) 16; (b) 36; (c) 52; (d) 61; (e) none of these

Let the sides be a, b, c with $a \geq b \geq c$ . There are 2 cases, one where $a=b$ and the other when $b=c$ .

First, the case $a=b$ . If $c=1$ , a can be from 2 to 9; if $c=2$ then a can be from 3 to 9, and so on. So the possibilities are 8+7+6+…+1 = 36.

Next, the case $b=c$ . We have $a > 2b$ so for $a=9$ we have b = 1, 2, 3, 4, and if $a=8$ then b = 1, 2, 3, and so on. Then the possibilities are 4+3+3+2+2+1+1 or 16.

The combined possibilities are 36+16 = 52. The answer is (c).

Problem 11

Which of the following is the largest?

(a) $2^{2^{2^{2^3}}}$ ; (b) $2^{2^{2^{3^2}}}$ ; (c) $2^{2^{3^{2^2}}}$ ; (d) $2^{3^{2^{2^2}}}$ ; (e) $3^{2^{2^{2^2}}}$

Immediately we know that B>A because $3^2 > 2^3$ . Next, B>C because 512 > 81. Comparing B and D, we compare $2^{512}$ with $3^{16}$ . Obviously B is bigger.

Finally we compare B with E. $B=2^{2^{512}}$ and $E = 3^{2^{16}}$ . But B can be written as $4^{2^{511}}$ which is obviously bigger. The answer is (b).

Problem 12

A gold number is one expressible in the form $ab + a + b$ for positive integers a and b. The number of gold numbers between 1 and 20 inclusive is

(a) 8; (b) 9; (c) 10; (d) 11; (e) 12

Write $ab + a + b$ as $a(b+1) + b$ . Take this modulo $b+1$ , so $n \equiv b \mod b+1$ . Then $n+1 \equiv 0 \mod b+1$ or $b+1 | n+1$ , with $b+1 > 1$ . Now if $n+1$ is composite this is possible, but if n+1 is prime then this is impossible (if $b=n$ then $a=0$ , a contradiction). Therefore a gold number is any number that’s not one less than a prime.

Below 20, the primes are 2, 3, 5, 7, 11, 13, 17, 19, so 8 numbers between 1 and 20 are not gold numbers. Then 12 are gold numbers. The answer is (e).

Problem 13

In tetrahedron ABCD, edges DA, DB, DC are perpendicular. If $DA=1$ , $DB=DC=2$ , then the radius of a sphere passing through A, B, C, D is:

(a) $\frac{3}{2}$ ; (b) $\frac{\sqrt{5}+1}{2}$ ; (c) $\sqrt{3}$ ; (d) $\sqrt{2} +\frac{1}{2}$ ; (e) none of these

Put the tetrahedron on a 3D cartesian grid with D being at $(0,0,0)$ , A at $(1,0,0)$ , B at $(0,2,0)$ , and C at $(0,0,2)$ . The equation of a sphere is $(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2$ , and since we know four points on the sphere, we can get four equations:

$a^2 + b^2 + c^2 = r^2$

$(1-a)^2 + b^2 + c^2 = r^2$

$a^2 + (2-b)^2 + c^2 = r^2$

$a^2 + b^2 + (2-c)^2 = r^2$

Solving for a, b, c, we get $a = \frac{1}{2}$ , $b = 1$ , $c = 1$ . So the radius, or distance from origin is $\sqrt{(\frac{1}{2})^2 + 1^2 + 1^2}$ or $\frac{3}{2}$ . The answer is (a).

Problem 14

Let $f(x) = x^2$ , $g(x) = x^4$ . We apply f and g alternatively: $f(x)$ , $g(f(x))$ , $f(g(f(x)))$ , etc. When we apply f 50 times and g 49 times, the answer is $x^n$ where n is

(a) 148; (b) 296; (c) $2^{148}$ ; (d) $2^{296}$ ; (e) none of these

Rather than looking at the numbers themselves, we look at the exponents. Then $f(x)$ multiplies the exponent by 2 and $g(x)$ multiplies the exponent by 4. Applying f 50 times and g 49 times gives an exponent of $2^{50} \cdot 4^{49}$ or $2^{148}$ . The answer is (c).

Problem 15

Triangle ABC has area 1. X and Y are on AB such that $XY = 2AX$ , and Z is a point on AC such that $XZ || YC$ and $YZ || BC$ . The area of $XYZ$ is

(a) $\frac{1}{27}$ ; (b) $\frac{2}{27}$ ; (c) $\frac{1}{9}$ ; (d) $\frac{2}{9}$ ; (e) $\frac{1}{3}$

As $XZ || YC$ , it follows that triangles $AXZ$ and $AYC$ are similar, and $AY : AX = 3:1$ so $AC:AZ = 3:1$ and $AB:AY = 3:1$ .

The area of $ABC$ is 1, so $AYC$ is $\frac{1}{3}$ and $AYZ$ is $\frac{1}{9}$ , and $XYC$ is $\frac{2}{27}$ . The answer is (b).

Problem 16

The number of integers n for which $2n+1 | n^3 -3n + 2$ is

(a) 3; (b) 4; (c) 5; (d) 6; (e) 8

Notice the left side is always odd, and the right side is always even. Therefore, it is equivalent to count solutions to $2n+1 | 8(n^3 - 3n + 2)$ .

Now $8(n^2 - 3n + 2) = 8 n^3 - 24n + 16$ and by long division we have $2n+1 | (2n+1) (4n^2 - 2n + 11) + 27$ , or $2n + 1 | 27$ .

27 has 4 positive factors (1, 3, 9, 27) and 4 negative factors, all odd. Thus there are 8 solutions. The answer is (e).

Posted on September 24, 2010June 26, 2015 in Mathematics

Notes on Catalan’s Conjecture

Alright so I’ve been a bit busy lately with school and all the homework and such, leaving me with much less time to study and write about mathematics than during the summer. But after a three week break I’m now blogging again. Yay. Anyways.

Catalan’s conjecture is an interesting conjecture in number theory. In this equation

$x^a - y^b = 1$

The only solution with $x, y, a, b > 1$ is $3^2 - 2^3 = 1$ . That is to say, there are no two other powers with a difference of 1.

This was conjectured in 1844, but only recently proven in 2002 by Mihăilescu, so it’s known also as Mihăilescu’s theorem. Mihăilescu’s proof of the theorem uses some very sophisticated techniques, and is beyond the scope of this blog post.

It turns out that Catalan’s conjecture is useful for solving some interesting number theory problems. We can sometimes reduce a problem down to a very specific instance of Catalan’s conjecture, then apply the proof, essentially overkilling the problem. Here are some examples.

Problem 1

Find all triples of positive integers $(a,b,c)$ where

$a^2 + 2^{b+1} = 3^c$

Solution

We look at powers modulo 4. It can be seen that $4 | 2^{b+1}$ when $b$ is positive, thus $2^{b+1} \equiv 0 \mod 4$ and $a^2 \equiv 3^c \mod 4$ .

Next note that $3 \equiv -1 \mod 4$ so $3^c \equiv (-1)^c \mod 4$ . As $3^c$ is always odd and $2^{b+1}$ is always even, $a^2$ must be odd hence $a$ must be odd. Taking the modulo 4, $a^2 \equiv 1 \mod 4$ (if $a \equiv 1$ or $a \equiv 3$ ). Thus $(-1)^c \equiv 1 \mod 4$ , implying that $c$ is even.

Then $c$ can be written as $2m$ for some $m$ . The equation is then $a^2 + 2^{b+1} = 3^{2m}$ , and with differences of squares,

$2^{b+1} = 3^{2m} - a^2 = (3^m+a) (3^m-a)$ .

The product of $3^m+a$ and $3^m-a$ is a power of 2, so both must themselves be powers of 2. Then there exists $x$ and $y$ where $x,y \in \mathbb{N}_0$ and $x<y$ such that

$3^m - a = 2^x$

$3^m + a = 2^y$

$x+y = b+1$

Adding the first two yields

$2 \cdot 3^m = 2^x + 2^y$

Putting $x=0$ causes a parity error. If $x \geq 2$ then the RHS is divisible by 4 while the LHS clearly isn’t. This makes $x=1$ , giving

$3^m = 1 + 2^{y-1}$ .

This is a case of Catalan’s conjecture. The only solutions to $(m,y)$ are $(1,2)$ and $(2,4)$ . Now we can just substitute the solutions for $(m,y)$ to get solutions for $(a,b,c)$ . They are $(1,2,2)$ and $(7,4,4)$ .

Problem 1a

Here is a very similar problem: find all integer solutions to

$3^a + 4^b = c^2$

The solution is left to the reader.

Hint: rewrite as a difference of squares and subtract

Problem 2

Find all triples $(x,y,n)$ of non-negative integers such that

$x^n = y^4 + 4$

Solution

Obviously $n$ cannot be 0. We first look at $n=1$ . Then, $x = y^4 + 4$ , and any triple $(y^4+4, y, 1)$ satisfies the equation.

Next we consider when $n=2$ . Then $x^2 = y^4 + 4$ , or as a difference of squares, $(x+y^2) (x-y^2) = 4$ . The solution then is $x=2$ and $y=0$ , or $(2,0,2)$ .

Now we try $n>2$ . Suppose that $y$ is even. Then in the equation $x^n = y^4 + 4$ , $4 | y^4$ and $4 | RHS$ so $4 | LHS$ , thus $x$ is even. Then $x^n = 2^n k^n$ for some $k$ , and it is clear that $n \leq 2$ , which is a contridiction.

So $y$ must be odd. The RHS, $y^4 + 4$ , can be written as $y^4 + 4y^2 + 4 - 4y^2$ , or $(y+2+2y)(y+2-2y)$ . This gives us

$x^n = (y^2 + 2y + 2) (y^2 - 2y + 2)$ .

We claim that for odd $y$ , $y^2 + 2y + 2 \perp y^2-2y+2$ . Let $k$ be the GCD of $y^2+2y+2$ and $y^2-2y+2$ so that $k | y^2+2y+2$ and $k | y^2-2y+2$ . Then $k|4y$ (the difference). As $y^2+2y+2$ is odd, and $k$ divides it, $k$ must be odd so $k|y$ . But $y^2+2y+2 = y(y+2)+2$ so $k|y$ and $k|y(y+2)+2$ , thus $k=1$ .

Hence for some integers $u$ and $v$ where $uv=x$ ,

$u^n = y^2 + 2y + 2$

$v^n = y^2 - 2y + 2$

Alternatively, $u^n = (y+1)^2 + 1$ and $v^n = (y-1)^2 + 1$ .

From Catalan’s conjecture, the equation $x^a - y^2 = 1$ with $a>2$ has no solutions other than $1^n-0^2=1$ . But we have the simultaneous equations $u^n - (y+1)^2 = 1$ and $v^n - (y-1)^2 = 1$ . This is clearly impossible.

Thus the only solutions are $(y^4+4,y,1)$ and $(2,0,2)$ .

Posted on August 11, 2010March 15, 2016 in Mathematics

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.

Solution

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.