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.


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.


Follow

Get every new post delivered to your Inbox.

Join 72 other followers