The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. In the two weeks leading up to the contest, I plan to take a look at some of the problems from the senior paper from 2018.

The first problem from the 2018 South African Mathematics Olympiad was

One hundred empty glasses are arranged in a $10 \times 10$ array. Now we pick $a$ of the rows and pour blue liquid into all glasses in these rows, so that they are half full. The remaining rows are filled halfway with yellow liquid. Afterwards, we pick $b$ of the columns and fill them up with blue liquid. The remaining columns are filled with yellow liquid. The mixture of blue and yellow liquid turns green. If both halves have the same colour, then that colour remains as is.

1. Determine all possible combinations of values for $a$ and $b$ so that exactly half of the glasses contain green liquid at the end.
2. Is it possible that precisely one quarter of the glasses contain green liquid at the end?

In order to find under what conditions half of the glasses contain green liquid at the end, it would be very helpful to know how many glasses (in terms of $a$ and $b$) contain green liquid, so that we can set up an equation to solve for $a$ and $b$.

We note that glasses containing green liquid occur at the intersection of a blue row and a yellow column, or at the intersection of a yellow row and a blue column. To calculate the number of glasses at the intersection of a blue row and a yellow column, we note that there are $a$ options for which row the glass is in, and $10 - b$ options for which column it is in. There are thus $a(10 - b)$ such glasses. Similarly, there are $b(10 - a)$ glasses at the intersection of a yellow row and a blue column. Since a glass must be in either a yellow row or a blue row, and can not be in both, we see that this accounts for each of the green glasses exactly once. There are thus $a(10 - b) + b(10 - a)$ glasses of green liquid in total.

We see that to determine the combinations of $a$ and $b$ such that exactly half of the glasses contain green liquid, we want to solve the equation

$\displaystyle a(10 - b) + b(10 - a) = 50.$

This can be manipulated to become

$\displaystyle (a - 5)(b - 5) = 0$

and so we see that exactly half of the glasses contain green liquid if and only if either $a = 5$, or $b = 5$!

Does this make sense? Is filling half of the rows (or columns) with blue liquid really enough to ensure that half of the glasses will contain green liquid? Suppose that half of the rows are filled with blue liquid. For each column, we note that if the column is filled with blue liquid, then a glass in that column will be green at the end precisely when it lies in a yellow row. By assumption, this is true for half of the rows, and so half of this column will end up green. Similarly, if the column is filled with yellow liquid, then it is in precisely the $5$ rows in which we find blue liquid that there will be a green glass at the end. Again we see that half of the column will end up green. Since half of every column turns out to be green, exactly half of the glasses will be green.

Let us consider the second question that was posed. Is it possible that exactly one quarter of the glasses contain green liquid at the end? In this case, we want to solve the equation

$\displaystyle a(10 - b) + b(10 - a) = 25$

which simplifies to

$\displaystyle 10a + 10b - 2ab = 25.$

This has no solutions in whole numbers, because for whole number values of $a$ and $b$, the left hand side of the equation will always be even, but $25$ is an odd number.

The reader may be interested to know that there is in fact a general method to solve equations of the type

$\displaystyle axy + bx + cy = d$

for given values $a, b, c, d$, and where we wish to find integer values for $x$ and $y$.

As we did for the first part of the SAMO problem, the general approach is to try to factorise the given expression in the form

$\displaystyle (px + q)(ry + t) = n.$

If we’re lucky, $n$ turns out to be $0$, and we can conclude that the only solutions are those where $x = -q/p$, or $y = -t/r$.

The case where $n \neq 0$ does not actually pose a problem, however. We did not see it arise when looking at the SAMO problem, but it is far more common. In this case, we know that each of the terms on the left hand side of the equation must be factors of $n$. The integer $n$ only has finitely many factors, and so we can find all solutions by setting $(px + q)$ to be equal to each one of these factors in turn. We find that all solutions in this case are given by

$\displaystyle x = \frac{d - q}{p} \quad \text{and} \quad y = \frac{n - dt}{dr}$

where $d$ is one of the finitely many divisors of $n$.

Is it always possible to find a factorisation of the desired form? Yes, we can check that the given equation is in fact equivalent to

$\displaystyle (ax + c)(ay + b) = ad + bc.$

At this point, we can note that if $\gcd(a, b) \gcd(a, c)$ does not divide $ad + bc$, then the equation has no integer solutions. (I leave it to the reader to explain why $\gcd(a, c)$ is always a divisor of $ad + bc$. This is why we consider the product of both of the $\gcd$‘s.) If we had applied this method to the second part of the SAMO problem, the factorised version of the equation would have been

$\displaystyle (-2a + 10)(-2b + 10) = 50.$

Since $4$ is not a divisor of $50$, we again see that there are no solutions. The reader is cautioned, however, that there may be other obstacles to the existence of a solution. Even if $\gcd(a, b) \gcd(a, c)$ is a divisor of $ad + bc$, not all factors of $n = ad + bc$ will yield integer solutions when applying the above method.

If the reader would like to put this method into practice, it can be applied to the first problem from the 2018 Putnam Mathematics Competition:

Find all ordered pairs $(a, b)$ of positive integers for which

$\displaystyle \frac{1}{a} + \frac{1}{b} = \frac{3}{2018}.$

 How clear is this post?