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

## A trivial inequality, and how to express its solution in the most cryptic way imaginable

February 19, 2012

Solutions to olympiad problems are seldom written with clarity in mind — just look at forum posts in the Art of Problem Solving. The author makes jumps and skips a bunch of steps, expecting the reader to fill in the gaps.

Usually this is not much of a problem — the missing steps become obvious when you sit down and think about what’s going on with a pencil and some paper. But sometimes, this is not the case.

### The problem

One of the worst examples I’ve seen comes in the book Inequalities, A Mathematical Olympiad Approach. By all means, this is an excellent book. Anyways, here’s one of its easier problems — and you’re expected to solve it using the triangle inequality:

Prove that for all real numbers a and b,

$||a|-|b|| \leq |a-b|$

### Attempt 1: Intuitive solution

It isn’t clear how the triangle inequality fits. If I weren’t required to use the triangle inequality, I might be tempted to do an intuitive, case-by-case argument.

Let’s visualize the absolute value of $a-b$ as the difference between the two numbers on a number line. Now we compare this distance $|a-b|$ with the distance after you take the absolute value of both of them, $||a|-|b||$. If one of the numbers is positive and the other negative, we clearly have a smaller distance if we ‘reflect’ the negative one over. Of course, if they’re both positive, or they’re both negative, then nothing happens and the distances remain equal.

There, a simple, fairly clear argument. Now let’s see what the book says.

### The book’s solution

Flip to the end of the book, and find

Consider $|a|=|a-b+b|$ and $|b|=|b-a+a|$, and apply the triangle inequality.

Huh. Perhaps if you are better versed than I am in the art of solving inequalities, you’ll understand what this solution is saying. But I, of course, had no idea.

Maybe try the substitution they suggest. I only see one place to possibly substitute $|a|$ for anything — and substituting gives $||a-b+b|-|b-a+a||$. Now what? I don’t think I did it right — this doesn’t make any sense.

To be fair, I cheated a little bit in the first attempt: I didn’t use the triangle inequality. Fair enough — let’s solve it with the triangle inequality then and come back to see if the solution makes any sense now.

### Attempt 2: Triangle inequality solution

A standard corollary to the triangle inequality of two variables is the following:

$|a|-|b| \leq |a-b|$

Combine this with the two variables switched around:

$|b|-|a| \leq |b-a| = |a-b|$

Combine the two inequalities and we get the desired

$||a|-|b|| \leq |a-b|$

Now let’s look at the solution again. Does it make sense? No, at no point here  did we do any $|a-b+b|$ substitution. Clearly the authors were thinking of a different solution that happened to also use the triangle inequality. Whatever it was, I had no idea what the solution meant.

### The book’s solution, decrypted

Out of ideas and hardly apt to let the issue rest, I consulted help online at a math forum. And look — it turns out that my solution was without a doubt the same solution as the book’s intended solution!

What the author meant was this: considering that $|a| = |a-b+b|$, we have $|a| \leq |a-b|+|b|$ from the triangle inequality. Then, moving the $|b|$ over we get $|a|-|b| \leq |a-b|$.

After that, the steps I took above are left to the reader.

Perhaps I’m a bit thick-headed, but your solution can’t possibly be very clear if a reader has the exact same solution yet can’t even recognize your solution as the same solution. Come to think of it, if I couldn’t even recognize the solution, what chance is there of anybody being able to follow the solution — especially if they’re new to inequalities?

Almost every one of the one-sentence phrasings of this solution I could think of would be clearer and less puzzling than the solution the book gives me.

## Fix for Digsby’s Facebook authentication error and broken Facebook support

January 26, 2012

To all Digsby users (ignore this post if you don’t use Digsby):

If you use Digsby with Facebook, you might have noticed that things behave strangely — the program pops up a window looking like this when it tries to connect to Facebook:

Then after you give it your credentials, Digsby still thinks you’re not logged in, and so on.

If you found this page via a google search, there’s a simple hack / workaround you can use to patch up this problem. Basically, instead of using the Facebook protocol to connect, we let Digsby use the Jabber protocol as a ‘proxy’ to connect to Facebook:

1. Go to Digsby -> My Accounts and in the Add Accounts section at the top, select the Jabber icon.
2. You should get a window that looks like this:
4. Remove the facebook account from Digsby

At this point, you’re done: Digsby should give you no more problems about Facebook.

Warning: the following is unnecessary and experimental! It might screw up the entire Digsby installation, forcing you to reinstall!

However, you can replace the Jabber icon with the Facebook one (this is for purely cosmetic purposes):

1. Go to C:\Program Files (x86)\Digsby\res\skins\default\serviceicons (that’s the default installation path on my machine, yours may be different)
2. Delete jabber.png, duplicate facebook.png, and rename it jabber.png
3. Restart Digsby

There you have it — hack accomplished:

## Understanding Harmonic Conjugates (sort of)

January 7, 2012

For many people (for me at least), the Harmonic Conjugate is a difficult concept to understand. I didn’t really get it the first time I saw it, at Mathcamp. Let’s take the definition of the harmonic conjugate:

AB and CD are harmonic conjugates if this equation holds:

$\frac{AC}{BC} = \frac{AD}{BD}$

If you’re like me, you’re thinking along the lines of “But why? Why is this defined this way? Why would we spend so much time proving things about this weird concept? What’s the point, what’s the use?”

Even now, I can’t really give you an intuitive explanation of why this equality is so important. On the other hand, I could certainly come up with a few problems in which the concept of the harmonic conjugate turns to be useful.

### Apollonius and Fleeing Ships

Apollonius’s problem was this: you are in control of a ship (point A on diagram), and you are in pursuit of another ship (point B). The other ship is fleeing in a straight line in some direction:

Your speed is (obviously) faster than the speed of the other ship: say they’re going at 30 km/h and you’re going at 50 km/h. Additionally, your ship is required to go in a straight line.

In which direction should you set off in order to intercept the fleeing ship?

### Solution with Harmonic Conjugates

The first step of the solution is to construct harmonic conjugates CD so that their ratio is the ratio of your speed to the other ship’s speed (we’ll prove later that this is actually possible; assume we can do this for now):

$\frac{AC}{BC} = \frac{AD}{BD} = \frac{5}{3}$

Next, draw a circle with diameter CD:

There is a point where the ray from B (their ship) intersects this circle. Now go to this point immediately, in a straight line: the ship will be there.

### The Proof

In order to prove that this works, we’ll need to take a step back and look at how we constructed the points C and D. The solution turns out to be evident directly from the construction of the harmonic conjugates.

Again, let’s assume our desired ratio is 5/3. Starting with the points A and B, the first step is constructing some point P so that:

$\frac{AP}{BP} = \frac{5}{3}$

This is fairly easy to do. Draw a circle of radius 5 around A, and draw a circle of radius 3 around B — the intersection P of these two circles forms the correct ratio. (if the circles don’t intersect, just scale everything up and try again)

Next, dropping the internal and external angle bisectors of the new triangle gives the harmonic conjugates C and D:

Why angle bisectors? From the angle bisector theorems (which I won’t prove here):

$\frac{AP}{BP} = \frac{AC}{BC} = \frac{5}{3}$

$\frac{AP}{BP} = \frac{AD}{BD} = \frac{5}{3}$

Combining the two proves that C and D are indeed harmonic conjugates to AB.

As a corollary, notice that because of angle bisecting, the angle CPD is always a right angle — hence, the locus of all points P forms a circle with diameter CD.

Returning to the ship problem, since each point P is defined as a point so that $\frac{AP}{BP} = \frac{5}{3}$, it follows that when both ships travel to such a point P, they will meet at the same time.

## My attempt at a Conquest AI

December 9, 2011

Before I move on, let me introduce Conquest – a chesslike minigame in Runescape. This isn’t a detailed description of the rules, just an overview to kind of get to know how the game works, if you haven’t seen it before.

You have a 20×20 board and some pieces (which you choose yourself and get to set up wherever you want, with some restrictions). You’re trying to kill all of your opponent’s pieces, which you have to do in order to win.

Each piece has a certain move radius — so it can move to any square within that radius (diagonals only counting as a distance of one). Then, once it has moved, it is allowed to attack an enemy within its range — again varying from piece to piece.

That’s the gist of the game. Oh yes, at certain times you can also use some silly special attacks in addition to moving and attacking — for instance, freeze an enemy piece for one move or temporarily boost the attack of one of your own pieces. And these special moves can be used on any pieces during your move, and in any combination.

### A Conquest AI… or not

So some months ago, I was playing Conquest. I was a decent player, but after a string of losses, I thought: maybe I can write an AI to play this game for me — perhaps better than a human can? Perhaps the same way you would write a chess AI?

Well, I scribbled some back of the envelope calculations, but I quickly realized that the number of possible moves at each position was far too large.

How large? A player has maybe 5 pieces, and if a piece’s average move radius is 4, then we already have 5*9*9 (remember 4 is the radius, not diameter) which is over 400. And that’s if we never attack or use special moves. If we take special moves into account, since special moves can be stacked on top of each other, assuming 5 valid targets per special move and 3 special moves we would multiply the 400 again by 5*5*5. For one move, we would need to consider 50000 possibilities.

In comparison, from any position in chess there are typically 30 or 40 legal moves. So the standard minimax algorithm would probably be no good, at least not without an incredible amount of heuristics. I had to try something different for this to work.

### Random has a chance

It turns out that there exists a very different strategy that worked quite well for Go-playing AIs. Instead of constructing and evaluating a huge search tree to find the best move, we simulate thousands random games, with random moves from each side. The move that gives us the best win percentage is played. All else being equal, a position that gives you a 90% chance of winning given random play from that point on is usually better than one with only a 30% chance of winning.

Here’s a screenshot of a connect-4 AI using this technique:

The Monte Carlo approach, as that’s what it’s called, seems absurd — there’s no way playing random moves can beat a good minimax! Indeed, Monte Carlo is never used to play chess, and I could sometimes beat the above AI. But where Monte Carlo really shines is when standard minimax is impractical — my scenario.

After finding and reading a few papers describing the method in detail, I was ready to start coding. However, there is still one more catch: to make it practical to set up the AI against other players over Runescape (and where the time limit for each move is usually 30 seconds), I would have to find a way to integrate the back end — the part that does the computations — with a front end that relayed the moves back and forth to the Runescape game client.

All is not lost, however: there were several freely available hacked clients for botting purposes: Powerbot allowed for users to write java scripts that automated tedious ingame actions.

That was about as far as I got though, unfortunately. Coding the game logic proved trickier than expected. A month or so after I started my account was banned for botting; later, Jagex (the company behind the game) made an update that rendered Powerbot (as well as every other similar hacked client) unusable. Without a game account nor a practical front-end, I called it quits.

## Solving the AB Game by Brute Force

November 7, 2011

The AB game, a variant of Mastermind, is played with pencil and paper and with two people. One person chooses a four digit number in which no digit is repeated, say X, and the other person tries to guess it in as few moves as possible. After the guesser guesses some number, say Y, the other person gives information on how closely Y matched with X:

• If some digit in Y coincides with a digit in X (in the same position), then the guesser scores an A.
• If some digit in Y exists in X but is in the wrong place, then the guesser scores a B.

For instance, if X is 1234 and we guess 2674, we get an A and a B, because the 4 is in the right place, and the 2 is one of the right numbers but isn’t in the right place.

This proceeds until the guesser gets the exact number.

When humans (or at least beginners) play the AB game, they usually do some form of uncoordinated trial and error, which gets the right answer after some large number of moves. This takes anywhere from about 8 to possibly 30 guesses. When I played this game with a friend, I didn’t have a very systematic strategy, but I wondered if a computer program could solve the game, always entering the optimal guess.

### A Bruteforce Solver

My first approach happened to work fairly well. Simply, the computer keeps track of a list of all possible numbers that the answer can be. At random, the computer guesses one of the numbers, and upon receiving feedback, eliminates every number in its list that doesn’t match that feedback. Quickly it eliminates whole swaths of combinations and arrives at the answer.

A typical session might go like this:

Guess 1: 6297. Score: 5040
b
Guess 2: 8512. Score: 1440
abb
Guess 3: 2315. Score: 83
bb
Guess 4: 5842. Score: 29
bb
Guess 5: 9581. Score: 13
ab
Guess 6: 8021. Score: 1


It took only 5 guesses for the computer to narrow down the choices to the only possible answer (8021).

A variant that is usually much harder for humans to solve is to allow the number chosen to have repeats. Although significantly trickier for humans to guess by trial and error, brute force doesn’t seem to be affected too much by it:

Guess 1: 1796. Score: 10000
b
Guess 2: 5881. Score: 3048
a
Guess 3: 0131. Score: 531
abb
Guess 4: 3311. Score: 15
aa
Guess 5: 3201. Score: 9
abb
Guess 6: 2011. Score: 1


The computer’s average of five or six is much better than a human can normally do! (although I haven’t researched possible human algorithms).

### Optimal or Not?

At this point you may begin to wonder if this strategy is the optimal one. Unfortunately, it is not — and I only need one counterexample to demonstrate that.

Suppose that instead of four numbers, you were allowed to choose 4 letters from A to Z. You choose the combination ABCW. Now suppose that the computer ‘knows’ that the first three letters are ABC — that is, it has eliminated all other combinations except for ABCD, ABCE, …, ABCZ.

By the random guessing algorithm, the computer is forced to guess ABCJ, ABCP, etc, until it eventually hits on ABCW at random. This may take a very high number of guesses.

A smarter strategy would be to guess combinations of four unknown letters, say DEFG, then HIJK, etc. Instead of eliminating one letter, you eliminate four letters at a time. Although some guesses have no chance of being correct, the number of guesses required is fewer in the long run.

### Source Code

I’ll put my somewhat unwieldy java code here for all to see:



import java.util.*;

public class ABSolver{

// Does cc1 and cc2 together match the pattern?
// If repeats are allowed, cc2 is matched against cc1.
static boolean fits(char[] cc1, char[] cc2, int A, int B){

int a = 0;
int b = 0;
for(int i=0; i<4; i++){
if(cc1[i] == cc2[i]) a++;
else{
for(int j=0; j<4; j++){
if(i != j && cc1[j] == cc2[i] && cc1[j]!=cc2[j]){
b++;
break;
}
}
}
}

return a==A && b==B;
}

public static void main(String[] args){

Random rand = new Random();
Scanner scan = new Scanner(System.in);

// Combinations that haven't been eliminated yet
List<char[]> ok = new ArrayList<char[]>(10000);

// Generate all possible combinations
for(int i = 0; i <= 9999; i++){

String i_s = Integer.toString(i);
while(i_s.length() != 4) i_s = "0" + i_s;

// Check for sameness
char a = i_s.charAt(0);
char b = i_s.charAt(1);
char c = i_s.charAt(2);
char d = i_s.charAt(3);
boolean same = a==b || a==c || a==d || b==c || b==d || c==d;

// Comment this line out if we're allowing repeats
if(same) continue;

char[] i_ia = i_s.toCharArray();

}

// Pick the first guess randomly
char[] firstg = ok.get(rand.nextInt(ok.size()));
char[] guess = null;

int nguesses = 1;

// Question answer cycle until we get it right
while(true){

// Ask for user response
if(nguesses > 1){
String ans = scan.nextLine();
int A = 0;
int B = 0;
for(char cc : ans.toCharArray()){
if(cc == 'a') A++;
if(cc == 'b') B++;
}

if(A==4) return;

// For each one check to see if it still fits
List<char[]> ok_ = new ArrayList<char[]>(ok.size());
for(char[] zhe : ok){
if(fits(zhe, guess, A, B))
}
ok = ok_;
}

char[] nextguess = null;
if(nguesses == 1)
nextguess = firstg;
else nextguess = ok.get(rand.nextInt(ok.size()));

System.out.println("Guess " + nguesses + ": " + new String(nextguess)
+ ". Score: " + ok.size());

// we win!
if(ok.size() == 1)
return;

guess = nextguess;
nguesses++;
}

}
}


## Calculating the Plane Angles of Platonic Solids

October 11, 2011

What is the angle between two planes of a tetrahedron?

The angle between any two edges of the tetrahedron is $60^\circ$, so it’s easy to (falsely) conclude that the angle between two faces must also be $60^\circ$.

But this isn’t the case: the plane angle is defined as the angle between two lines on the two planes that are both perpendicular to the edge. None of the edges in a tetrahedron is perpendicular to any other, so the answer of $60^\circ$ is invalid.

We can try to compute the angle using regular Euclidean solid geometry, but things tend to get messy. A different way to approach the problem is by using vector geometry: using vector methods we can easily calculate the plane angle of the tetrahedron (as well as the icosahedron and the dodecahedron).

Assume symmetry. We represent three concurrent edges of the polyhedron as three vectors beginning at the same point: $\vec a$, $\vec b$, and $\vec c$; let $\alpha$ and $\beta$ be the angles between the vectors (by symmetry we’re assuming that the two alpha’s are equal):
(in case my poor drawing skills does not make this apparent, vectors a and b form one face of the polyhedron and c and b form another face)

For simplicity, let’s also say the lengths of each of the three vectors is 1.

We want to compute the angle between the plane formed by $\vec a$ and $\vec c$, and the plane formed by $\vec b$ and $\vec c$. Hence let $\vec x$ and $\vec y$ be the perpendiculars to $\vec a$ and $\vec b$ respectively each ending at the same point as their respective vectors:

For any two vectors, the dot product is defined $\vec a \cdot \vec b = |\vec a| |\vec b| \cos \theta$ with $\theta$ being the angle between the vectors. Given that the lengths of the vectors are all 1, we have:

$\vec a \cdot \vec c = \vec b \cdot \vec c = \cos \alpha$

$\vec a \cdot \vec b = \cos \beta$

Also, by vector addition:

$\vec c \cos \alpha + \vec x = \vec a$

$\vec c \cos \alpha + \vec y = \vec b$

Hence $\vec x = \vec a - \vec c \cos \alpha$ and $\vec y = \vec b - \vec c \cos \alpha$.

We want to find the angle between $\vec x$ and $\vec y$ — call this angle $\theta$. Then

$\vec x \cdot \vec y = |\vec x| |\vec y| \cos \theta$

The dot product of vectors x and y is simply:

$\begin{array}{l} (\vec a - \vec c \cos \alpha) \cdot (\vec b - \vec c \cos \alpha) \\ = (\vec a - \vec c (\vec a \cdot \vec c)) \cdot (\vec b - \vec c (\vec b \cdot \vec c)) \\ = \vec a \cdot \vec b - (\vec a \cdot \vec c) (\vec b \cdot \vec c) \\ = \cos \beta - \cos^2 \alpha \end{array}$

Additionally $|\vec x| = |\vec y| = \sin \alpha$. Hence the cosine of the angle is:

$\cos \theta = \frac{\vec x \cdot \vec y}{|\vec x| |\vec y|} = \frac{\cos \beta - \cos^2 \alpha}{\sin^2 \alpha}$

We can now use this newly derived formula to calculate plane angles! For example…

### Tetrahedron

In the tetrahedron, both $\alpha$ and $\beta$ are 60:
So $\cos \theta = \frac{\cos 60 - \cos^2 60}{\sin^2 60} = \frac{1}{2}$ and $\theta = \arccos \frac{1}{3} = 70.8^\circ$.

Icosahedron

In the icosahedron, $\alpha = 60$ but $\beta = 108$:
The top ‘cap’ is a regular pentagon, which has a vertex angle of 108; each side of the pentagon constitutes a side of an equilateral triangle. Since $\cos 108 = \frac{1}{4} (1-\sqrt{5})$, $\cos \theta = \frac{\cos 108 - \cos^2 60}{\sin^2 60} = -\frac{\sqrt{5}}{3}$, and $\theta = \arccos (-\frac{\sqrt{5}}{3}) = 138.2^\circ$.

### Dodecahedron

Computing angles for the dodecahedron works a bit differently from the tetrahedron and icosahedron. Instead of using existing edges as vectors, we construct an equilateral triangle by connecting three vertices:

So $\alpha = 36$ (since it’s part of a regular pentagon) and $\beta = 60$. Then $\cos \theta = \frac{\cos^2 60 - \cos^2 36}{\sin^2 36}$ and $\theta = 116.6^\circ$.