Balkan MO 2018 – Questions 2,3,4

The Balkan Mathematical Olympiad is a competition for secondary school students organised annually by eleven countries in Eastern Europe on a rotating basis. The 2018 edition was held near Belgrade, Serbia over 7-12 May 2018. The UK was grateful to be invited as a guest nation.

A full account of the competition can be found in this report and this blog report. This blog post concerns the three non-geometry questions on the paper. For typical able British schoolchildren, the order of the questions might not be ideal, and so this post talks about the problems in a non-standard order. A post about the geometry Q1, and a discussion of some of the background, including an introduction to harmonic ranges may be found here.

Problem Three

Alice and Bob play the following game. They start with two non-empty piles of coins. Taking turns, with Alice playing first, each player chooses a pile with an even number of coins and moves half of the coins of this pile to the other pile. The game ends if a player cannot move, in which case the other player wins.

Determine all pairs (a,b) of positive integers such that if initially the two piles have a and b coins, respectively, then Bob has a winning strategy.

Clearly, the game ends when both piles are odd. If one pile a is odd, and the other b is even, then only one move is possible, namely ending up a+b/2 and b/2. It’s not possible that both of these are odd, so further analysis would be required. However, we might notice from this that if a is even, and b is 2 modulo 4, then there are two possible moves, but at least one of them ends up with both piles now being odd.

So when the official solution starts with the sentence ‘let v_2(a) be the exponent of the largest power of two dividing (this is often called a valuation, and is a useful property to consider in many contexts.) a‘, this is not magic, but a natural response to a preliminary investigation along the lines of the previous paragraph.

One should then consider some cases. It is clear that Bob wins if (a,b) are both odd, that is v_2(a)=v_2(b)=0, and in our preliminary exploration we established that Alice wins if a\equiv b\equiv 2 modulo 4, that is v_2(a)=v_2(b)=1. It’s not too hard to establish from here that if v_2(a)=v_2(b), then Bob wins iff this common valuation is even, and Alice wins when it’s odd. It’s also worth noting that this holds irrespective of the players’ choices of moves.

To finish the problem, we now have to classify the remaining cases, and prove what happens in these cases. From the final preliminary observation, we know that Alice wins if v_2(a)=1 and v_2(b)\ge 1, but it seems like the game might go on for ever if both players aim to avoid losing when starting from v_2(a)=0 and v_2(b)\ge 1. One can try some more small examples, or move straight to a conjecture, but the parity (That is, whether a number is odd or even) of \min(v_2(a),v_2(b)) determines the outcome. In neither case does Bob win, but Alice wins when this minimal valuation is odd, and the game continues forever if it’s even, and if you haven’t already, you should try proving this by considering how the valuations could change on any move.

As a slight alternative, especially once you know the answer and have observed that the outcome is invariant under multiplying both a,b by four (and so v_2(a)\mapsto v_2(a)+2), one could attempt the following argument. Introduce the notation (a_t,b_t) for the pile sizes at time t\ge 0, so (a,b)=(a_0,b_0). We know the outcomes in all cases where \min(v_2(a),v_2(b))\le 2. So if we start the original game G from a pair (a,b) satisfying \min(v_2(a),v_2(b))\ge 2, we could consider an alternative game G’ whose rule for winning instead says that we wait for the first time t such that Alice is to move and \min(v_2(a_t),v_2(b_t))\le 2. Then we declare the winner (or non-winner) to be the outcome of the original game G started from (a_t,b_t). While the outcome profile is obviously the same as the original game G, we can claim that playing G from (a,b) is the same as playing G’ from (4a,4b), and thus derive the entire outcome profile by induction.

The details required to establish this claim are easy but numerous, and certainly need to be present in a full solution, which explains Alex’s unfortunate mark for this problem despite having this sophisticated and workable idea. Finishing the details would be an excellent exercise for anyone aiming to tighten up their combinatorial clarity at this level.

Problem Two

Let q be a positive rational number. Two ants are initially at the same point X in the plane. In the n-th minute (n=1,2, … ) each of them chooses whether to walk due north, east, south, or west, and then walks q^n metres in this direction. After a whole number of minutes, they are at the same point in the plane (not necessarily X), but have not taken exactly the same route within that time. Determine all possible values of q.

The answer is that only q=1 is possible, and the majority of approaches will eliminate all but a finite number of potential values first, then study the cases q=2 and q=1/2 separately. Even though it might seem obvious, remember that you have to provide an example for q=1 too!

This is really a question about polynomials, where the variable is q. So for example, if ant A follows the path NNESWN, then its coordinates after the sixth minute are

(x^6_A,y^6_A)=\left(q^3-q^5,\, q+q^2-q^4+q^6\right).

So if we want to prove it’s impossible for (x^n_A,y^n_A)=(x^n_B,y^n_B) for some different length-n paths, we could first focus on just one coordinate, say the x-coordinate. But note that x_A^n-x_B^n is a polynomial in q with degree at most n, where all the coefficients are {-2,-1,0,1,2}. So if the ants are in the same place at time n, then q is a root of this polynomial.

Insisting on converting q into \frac{a}{b} at an early stage is a sort of intellectual comfort blanket that’s probably going to distract from the main insight. But at this stage, we do need to introduce this, and argue that if q=\frac{a}{b} in lowest terms, then q cannot be a root of such a polynomial if either a or b is at least 3. Proving this yourself is definitely a worthwhile exercise. Remember to use that a and b are coprime! (With an additional idea, you can reduce instead to a polynomial with coefficients in {-1,0,+1}, from which you can finish even faster.)

To reduce the number of cases left, we can show that there are examples for q iff there are examples for 1/q, arguing either via the polynomial description (much easier with q rather than \frac{a}{b} again here), or more combinatorially in terms of reversed ant paths.

To finish the problem we have to eliminate one of the possibilities q=1/2 and q=2 (as one follows from the other by the previous paragraph). For q=2, we should study the first time at which the ants diverge, but life will be easier if we argue that we may assume that this happens on the first step. Now, we study the first couple of moves.

  • If one ant moves horizontally and the other moves vertically on the first move, then what can you say about the parity of each ant’s coordinates after the first step, and indeed after all future steps? This will show that they cannot ever meet.
  • Otherwise, assume that both ants move horizontally, one East, one West. Since we can’t use parity, but powers of two are deeply involved, it makes sense to consider using congruence modulo 4. Indeed, after this first step, the ants’ x-coordinates are not congruent modulo 4 (since one is 1 and the other is -1).
    • If they both move vertically on the second step, or both move horizontally on the second step, this remains the case. (One should check both options for the horizontal case.) Thereafter, all moves have length divisible by 4, and so this property holds forever, and so the ants do not meet.
    • If one moves horizontally, and one moves vertically on the second step, what can you say about the ants’ y-coordinates modulo something relevant?

If you want to study q=1/2 instead, you might observe by trying some examples that if the ants head off in different directions, there is a real sense that they become too far apart to get back together using the future allowed moves. This motivates considering some sort of distance argument. The interplay between the coordinates is not really suited to standard Euclidean distance, since the ants can’t walk in a diagonal direction (which is what will mostly determine the Euclidean distance). Instead, it’s worth studying d_n(A,B):=|x^n_A - x^n_B| + |y^n_A-y^n_B| (which is sometimes called \ell_1-distance, or Manhattan distance or taxicab distance.) What is d_1(A,B), and can you control d_n(A,B)-d_{n-1}(A,B) strongly enough to show that d_n(A,B) is always strictly positive? If you can, perhaps you can draw an analogy with the argument for q=2 as a final insight into the workings of this interesting question?

Problem Four

Find all primes p and q such that 3p^{q-1}+1 divides 11^p+17^p.

None of the UK students solved this problem during the competition, but several managed it during some free time the following morning. Nathan’s solution, lightly paraphrased, will follow shortly.

In a question like this, you don’t know how many of the details will be crucial. Is the choice of {3,11,17} going to be important? How will we use the fact that q is prime? You probably can’t answer these meta-questions immediately. It also looks like standard motifs of subtracting multiples of 3p^{q-1}+1 from 11^p+17^p is not going to make life easier. Nathan’s approach is to study the possible factors of 11^p+17^p, focusing on prime power factors. Once he has a rich enough understanding of potential such factors, he can then study whether they combine to form 3p^{q-1}+1, which turns out to be very restrictive, leaving only a handful of cases to eliminate by hand.

Nathan writes: We can quickly eliminate the possibility that p=2, and so now assume we have a solution where p is odd.

Claim I: None of 8, 49 or 11 divide 3p^{q-1}+1.

Proof: It’s enough to show that they do not divide 11^p+7^p. The non-divisibility of 11 is clear. For 8, note that 11^p\equiv 1,3 and 17^p\equiv 1 modulo 8, and so 11^p+17^p\equiv 2,4 \not\equiv 0.

To handle 49, we rewrite 11^p+17^p as 11^p-(-17)^p and we have the valuation v_7(11 - (-17))=v_7(28)=1. So when we lift the exponent (see later), we find

v_7\left(11^p-(-17)^p\right) = 1+v_7(p).

So if 49\mid 11^p+17^p, then the LHS is at least two, and so v_7(p)\ge 1. But then p=7 is the only option, for which certainly 49\nmid 3p^{q-1}+1. The claim is now proved.

So we may now write

3p^{q-1}+1 = 2^a7^b \prod r_i^{e_i}, (1)

where r_i are primes not equal to {2,7,11}, and a\in\{1,2\},\, b\in\{0,1\}.

Claim II: each r_i\equiv 1 modulo p.

Proof: As before r_i\mid 11^p-(-17)^p, and since r_i\ne 11, 11 has a multiplicative inverse modulo r_i, and so indeed there exists t such that 11t \equiv -17 modulo r_i. Using this in the divisibility relation:

r_i\mid 11^p-(-17)^p \equiv 11^p - (11t)t^p \equiv 11^p(1-t^p) \quad\iff\quad r_i\mid 1-t^p.

The order of t modulo r_i then divides p, so is either 1 or p. If this order is 1, then t\equiv 1, but then, modulo r_i, 11\equiv -17, so r_i\mid 28, which we have excluded already. So the order is p, and thus p\mid r_i-1, as we claimed.

Going back to (1), we have

1\equiv 3p^{q-1}+1 = 2^a7^b\prod r_i^{e_i} \equiv 2^a 7^b\quad \mod p,

and so p\mid 2^a7^b-1. But remember that a\in\{1,2\} and b\in\{0,1\}, so there are only a handful of cases to check. Each of the other cases requires a line or two to eliminate, so do try this yourself! In the end, though, we see that (a,b)=(2,0) or (2,1), both leading to p=3 are the only possibilities. Returning to the original question, we just have to check possible solutions to 3^q+1 \mid 11^3+17^3=2^2\cdot 7\cdot 223, which we can do manually (for example by checking all prime q\le 7), to find that the only solution is (p,q)=(3,3).

Dominic: As part of this solution, Nathan uses the lifting the exponent lemma to control v_7(11^p-(-17)^p). This example is simple enough that it’s probably easiest to go directly. Since p is odd, we can factorise

11^p+17^p= 28\cdot \left( 11^{p-1}- 11^{p-2}\cdot 17 + 11^{p-3}\cdot 17^2-\ldots + 17^{p-1}\right).

Can you come up with an argument for why 7 cannot divide the second factor? Some of the notation Nathan used elsewhere in his solution may be useful! If you can, then you’ve shown that v_7(11^p+17^p)=1.

The general statement of the lemma relates v_p(x^n-y^n) to v_p(n) and v_p(x-y), which explains why Nathan converts +17^p to -(-17)^p, though it makes little difference to the proof. You can find statements of this lemma, which has become relatively well-known recently in this community (and which is sometimes attributed to Mihai Manea), in many places on the internet and in modern books. The proof is very similar in the general case to the special case discussed previously. It’s worth remembering that the case p=2 always requires extra care (and indeed a different statement). This distinction comes from the fact that the simultaneous congruence equations x+y\equiv 0 and x-y\equiv 0 modulo $n$ have two pairs of solutions when 2\mid n.

It’s worth noting also that in a solution like Nathan’s where different ranges of options are excluded one after the other, this clear organisation into claims is of huge benefit to the reader, irrespective of how much text is or isn’t included as a prelude.


1 thought on “Balkan MO 2018 – Questions 2,3,4

  1. Pingback: Harmonic ranges and Balkan MO 2018 Q1 | Eventually Almost Everywhere

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s