The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. I have been writing about some of the problems from the senior paper from 2018. A list of all of the problems can be found here.

Today we will look at the sixth and final problem from the 2018 South African Mathematics Olympiad:

Let n be a positive integer, and let x_1, x_2, \dots, x_n be distinct positive integers with x_1 = 1. Construct an n \times 3 table where the entries of the k-th row are x_k, 2x_k, 3x_k for k = 1, 2, \dots, n. Now follow a procedure where, in each step, two identical entries are removed from the table. This continues until there are no more identical entries in the table.

  1. Prove that at least three entries remain at the end of the procedure.
  2. Prove that there are infinitely many possible choices for n and x_1, x_2, \dots, x_n such that only three entries remain,

There are some heuristics that are often helpful when solving a problem, such as

  • Looking at small cases:

    This helps us to understand the problem and how the various pieces in the problem relate to each other. It also helps us to spot patterns that we could try to prove hold in general, or to find ways to build larger solutions from smaller ones.

  • Building up larger solutions from smaller ones (recursion)

    Sometimes, such as in this problem, we are asked to find multiple solutions to some problem, and so being able to build larger solutions from smaller ones would be invaluable.

    Sometimes we want to count in how many ways certain things can be done. If every solution to a problem can be built from a smaller one, and we know how many solutions there are in the smallest case, this will allow us to establish a recurrence relation.

    Trying to build larger solutions from smaller ones also helps to give us more intuition for how the problem works.

  • The Extremal Principle:

    Often being the largest or smallest item in some set places additional constraints on that item that makes it easier to reason about, or limits how it is able to interact with other items in the set. More examples of using this principle can be found on Brilliant.org.

  • Review the solution:

    Does the result make sense? Are there other ways to prove the same result? This doesn’t help us that much in solving the current problem, but does give us confidence that our solution is correct, and may help us in solving similar problems in the future.

The first thing that we should notice about this problem is that the order in which we perform the operations is largely irrelevant. A number will remain at the end if and only if it appears an odd number of times in the table. The only thing that the order of deletions can affect is the positions of the numbers at the end, but it can not affect how many of them there are.

In this problem, by far the simplest case is when n = 1 and x_1 = 1. In this case, our table is simply

x_k 2x_k 3x_k
1 2 3

In this case, exactly three numbers remain. Perhaps if we can find larger examples where exactly three numbers remain, we can try to extract a pattern. It may be the case that the three numbers that remain are precisely the three that are forced to remain in all situations, and so this will give us some insight into how we might go about the proof for the first part of the problem. It will also help us to see how to construct larger examples, which may help us with the second part of the problem.

To build a larger example, we need to duplicate some of the numbers so that they will be crossed out. Since the number 1 can only appear in the first column, and since the x_i must be distinct, we can not create a duplicate of the number 1, and so the number 1 will always remain.

This is already a valuable piece of insight. We have already identified one of the three numbers that will always remain. Perhaps we can try to generalise what sorts of numbers will always remain. In this case, 1 happens to also be the smallest number in the table, and so this is an example of the extremal principle. The smallest number in the table must appear in the first column, and since the x_i are unique, the smallest number can only appear once. A similar argument shows that the largest number in the table must remain at the end because it can only appear in the third column. We could generalise this argument even further: any number which can only appear in one of the three columns must only appear in the table only once.

With this insight stored securely in our arsenal, let us continue trying to build larger examples where only three numbers remain. The next candidate for a number to duplicate is the number $latex2$. This already appears in the second column, and can not appear in the third column, and so let’s make x_2 = 2 so that it appears in the first column. Now our table looks as follows:

x_k 2x_k 3x_k
1 2 3
2 4 6

where black cells indicate numbers which have been removed because they are duplicates.

Duplicating the 3 will also get rid of the 6 which we have now created. We could try to remove other numbers, but in each of the other cases, we would remove one number but gain two. Setting x_3 = 3 gives us

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9

This gives us our second example of a table with exactly three numbers remaining. We note that the fact that there is one number remaining in each column lends support to our earlier idea that a number which can only appear in one of the columns must only appear once in the table. We should try to identify what property of the numbers 1, 4, and 9 ensure that they only appear in one column. We already know that 1 and 9 remain because they are the smallest and largest numbers, respectively, but what is special about 4? We carry on.

If we duplicate the number 4, we obtain the table

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9
4 8 12

Working with the hypothesis that we only want one number to remain in each column, we should now try to remove the 9 or the 12. We also know that it is the largest number in the table that will remain in the third column, and since there are already numbers larger than 9 in the table, we should remove the 9. Placing 9 in the first column thus gives us

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9
4 8 12
9 18 27

The exact same argument now tells us that we should remove the 12. There are two ways in which this could be accomplished: we could place a 6 in the first column so that 12 appears in the second column, or we could place a 12 in the first column. I will save us from the trial and error that would ensue at this point by pointing out that a 6 placed in the first column could never be removed because then there is already a 6 in all three of the columns. We thus want to place a 12 in the first column. This gives us

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9
4 8 12
9 18 27
12 24 36

A similar argument to before tells us that we should remove the 27, which can only be done by adding a 27 in the first column.

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9
4 8 12
9 18 27
12 24 36
27 54 81

We could get rid of the 18, 36, and 54 in one fell swoop by placing a 18 in the first column. We then have to delete either the 8 or the 24 in the second column. Alternatively, we could delete both by placing a 8 in the first column. This turns out to be a better idea, because we then have…

x_k 2x_k 3x_k
1 2 3
2 4 6
3 6 9
4 8 12
9 18 27
12 24 36
27 54 81
18 36 54
8 16 24

…our third example of a table with only three numbers remaining!

We can’t really claim that this is evidence that there will always be one number remaining in each column, because we explicitly constructed the table with the goal of having one number remain in each column. Thus at best it is evidence that examples of such tables exist, and may help us in constructing larger examples in order to solve the second part of the problem. Let us disabuse ourselves of the notion that we are logical beings, however, and pretend that this table is, in fact, representative. What insights could we gain?

We already know that the smallest and largest number will always remain in the table because these can only possibly appear in the first and third column, respectively, so our goal is now to figure out what is special about the numbers that remain in the second column. These numbers were 2, 4, and 16. One thing that these have in common is that they are all powers of 2. It is not, however, the case that powers of 2 can only appear in the second column, because they could also appear in the first column. What, then, is special about the powers of 2 that appear in the second column? Either by being inspired by the fact that when other numbers remained in the table, it had something to do with their size, or through trial and error by looking at what happens when powers of 2 appear in the first column, we come to the realisation that it is the largest power of 2 which can only appear in the second column, since if a power of 2 appears in the first column, then a larger one appears in the second column in the same row!

We have thus succeeded in identifying the three numbers that always remain: 1, the largest power of 2, and the largest number in the table. In fact, in the cases where exactly three numbers remain, the largest number in the table happens to also be the largest power of 3 in the table, and so an equally valid description of the numbers that always remain would be 1, the largest power of 2, and the largest power of 3.

When we write a solution to the problem, we do not need to include all of the work that we did above. We could simply say that we will prove that 1, the largest power of 2, and the largest power of 3 will always remain, and then do so by proving that each of these numbers can only appear in one of the three columns and hence can not be duplicated because to do so would require two of the x_i to be the same. This is how most mathematics is written: we are given the final result without being shown how the author came up with the ideas in the solution. When reading mathematics, it is helpful to try to figure out why certain steps were taken, or what led the author to believe that they may work.

There are of course other ways in which we could come to the realisation that 1, the largest power of 2, and the largest power of 3 always remain. In our experimentation, we could have noticed, for example, that whenever we try to get rid of a power of 2, we just get a larger one in its place. It is thus impossible to eliminate all of the powers of 2 in the table, and so there will always be at least one which remains. We are more likely to notice this, however, if we already have the intuition that powers of 2 are important! When writing the solution, we don’t have to show that it is the largest of power of 2 that always remains. We could make the above argument more formal and use it to show that there will always be at least one power of 2!

It is certainly interesting to try to think about other ways in which we could solve the problem or in which we could have come to realise which numbers always remain, but we still haven’t solved the second part of the problem. So far, we have mainly used trial and error to try to construct larger tables. We need a more systematic approach.

The key insight for creating larger tables from smaller ones turns out to be the following: If we multiply each of the x_i by some constant c, then this has the effect of multiplying every entry in the table by the same constant c. If two numbers in the table before were equal, then the numbers now in the same position would still be equal, and could still be deleted. Thus the same sequence of deletions could occur. We see that if the numbers that originally remained in the table were y_1, y_2, \dots, y_m, then the numbers that remain in the new table are cy_1, cy_2, \dots, cy_m.

This insight is clearly useful, and we will use it to construct larger tables, but it may be very difficult to come up with it ourselves. A certain amount of luck, and previous experience with sufficiently similar problems is necessary.

Suppose that we have a sequence x_1, x_2, \dots, x_n such that the numbers 2^a, and 3^b remain in the table at the end of our procedure. How could we create a table where a larger power of 2 remains at the end? We could just take the current table and add a row starting with 2^a. To get a larger power of 3, we could add a row starting with 3^b. We could then try to add more rows to this table to try to get rid of the numbers that we don’t want. In doing so, we may realise that the sequence of deletions that we perform are very similar to the ones we performed when constructing our starting table in the first place, or we might not. We could try to find a solution this way, but the problem becomes much easier if we instead embrace our previous insight right from the onset.

If we were to multiply each of the x_i by 2^s, for some s, then we know that we would obtain a table where the numbers that remain are 2^s, 2^{a + s}, and 2^s \cdot 3^b. Similarly, if we were to multiply each of the entries by 3^t instead, then we would obtain a table where the entries that remain are 3^t, 2^a \cdot 3^t, and 3^{b + t}. Thus if we combine all three of the tables, we have one large table, three times the size of the original, where there is some sequence of operations that can be performed such that nine numbers remain:

1 2^a 3^b
2^s 2^{a + s} 2^s \cdot 3^b
3^t 2^a \cdot 3^t 3^{b + t}

We would like for only three numbers to remain, so perhaps we can choose s and t such that some of these numbers are equal, and hence can be deleted. We note that the only number which can be equal to 2^s \cdot 3^b is 2^a \cdot 3^t. Thus we could at least remove these two numbers by taking s = a, and t = b. The nine numbers that remain are then

1 2^a 3^b
2^a 2^{2a} 2^a \cdot 3^b
3^b 2^a \cdot 3^b 3^{2b}

and after removing the duplicates, we are left with just 1, 2^{2a}, and 3^{2b}. We have thus constructed a larger table where only three numbers remain, and can construct infinitely many more by applying the same procedure to the new table, and the result of doing so, and so on. To be more formal, we should use mathematical induction, and should describe the new sequence x_1, x_2, \dots x_{3n} more explicitly. We also have to be careful, because one of the rows in the table where we multiplied the entries by 2^a could be equal to one of the rows in the table where we multiplied the entries by 3^b. In other word, we may now have duplicate x_i‘s in the combined table. This is not a problem, however, because we could simply exclude these rows entirely and not change the numbers that remain at the end of the procedure. Provided that we take care when writing up the solution, we have succeeded in solving the second part of the problem.

As a follow up, which is left as an exercise to the reader, we may wonder whether the tables that we constructed above are the only possible ones where precisely three numbers remain. i.e. We could ask ourselves to find all values of n, x_1, x_2, \dots, x_n such that only three numbers remain instead of “merely” finding infinitely many. I have not worked through this version of the problem, and so I do not know the answer, but I suspect that the answer is “yes”, and would be delighted to either see a proof, or to learn otherwise.

How clear is this post?