Balkan MO 2018 – Questions 2,3,4 | Eventually Almost Everywhere

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”

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

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Balkan MO 2018 – Questions 2,3,4

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

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

Leave a Reply Cancel reply