IMO 2018 Day 2

Day 2 had a bunch of really nice problems with more advanced techniques required to solve them. Problem 6 is also hard and I will be writing it up at a later time.

Problem 4: A site is any point (x, y) in the plane such that x and y are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to \sqrt{5}. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance fromany other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest K such that Amy can ensure that she places at least K red stones, no matter how Ben places his blue stones.

Solution 4: The given condition is equivalent to placing knights on a chessboard, with one party blocking a space every other turn. It is well known that on a 2n \times 2n chessboard, you can place 2n^2 knights by placing n knights in the n black squares in the 2n rows, and this is easily discoverable by playing around with placements a for a bit. Thus, if Ben blocks a placement every other turn, we can only place pieces on half of the squares described above, so for the case in a 20 \times 20 board, we conjecture that K = 100.

It remains to show that K > 100 is indeed impossible. To do this, we show that K \leq 100, or that Ben can play in a way such that Amy can only place at most 100 stones. To do this, we study the 4 \times 4 grid (tiled 25 times) as 4 distinct 4-cycles as follows:

p4 grid

If Amy places a stone in X, Ben will place his stone in the opposite corner of X. This ensures that Amy can no longer place any more stones in X. Since there are 4 regions per grid, Amy can only place 4 stones per grid. Thus, Amy can place at maximum of 100 stones if Bob plays in this manner and we are done.

Problem 5: Let a_1, a_2, \dots be an infinite sequence of positive integers. Suppose that there is an integer N > 1 such that for each n \geq N, the number

    \[ \frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n - 1}}{a_n} + \frac{a_n}{a_1} \]

is an integer. Prove that there is a positive integer M such that a_m = a_{m + 1} for all m \geq M.

Solution 5: The key to this problem is to use a size argument on p-adic valuations to guarantee convergence of the a_i. We consider two consecutive sums, whose difference

    \[ \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} - \frac{a_n}{a_1} \]

must be an integer because the two sums are integers. Let \nu_p \left( \dfrac{a}{b} \right) = e_a - e_b where e_x are defined as p^{e_x} \mid x but p^{e_x + 1} \nmid x. This is the standard p-adic valuation. Note that because this difference is an integer, its p-adic valuation must be non-negative. This is a fact that will used repeatedly.

Now for all primes p, consider

  • p \nmid a_1. Then \nu_p(a_n}) \geq \nu_p(a_{n + 1}) for all n > N. Else the difference cannot be integral, which can be seen from the inequality \nu_p \left( \dfrac{a_n}{a_{n + 1}} + \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \leq \min \left( \nu_p(a_n) - \nu_p(a_{n + 1}), \nu_p \left( \dfrac{a_{n + 1}}{a_1} - \dfrac{a_n}{a_1} \right) \right). We have equality when the two things inside the \min are unequal, and the second element is most definitely non-negative whereas if the first element is negative then they are clearly not equal.
  • p \mid a_1. In this case we claim \nu_p(a_n) eventually becomes constant. There are a few cases to consider here.

    • Suppose \nu_p(a_k) \geq \nu_p(a_1) > 0 for some k > N. We claim that \nu_p(a_1) \leq \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all n \geq k, or that \nu_p(a_n) is eventually non-increasing and bounded below by \nu_p(a_1) so it must eventually be constant.

      For this case, we have \nu_p \left( \dfrac{a_n}{a_1} \right) \geq 0, meaning that the remaining terms in the difference must also satisfy

          \[ \nu_p \left( \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} \right) \geq 0. \]

      The trick here is to figure out where \nu_p(a_{n + 1}) goes. If \nu_p(a_{n + 1}) < \nu_p(a_1) \leq \nu_p (a_n), then \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) < 0 which is bad because \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) \geq 0. Else if \nu_p(a_{1}) \leq \nu_p(a_n) < \nu_p(a_{n + 1}), then \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) < 0 which is also bad because \nu_p \left( \dfrac{a_{n + 1}}{a_1} \right) \geq 0. We start at the base case n = k and inductively go onwards to show this for all n \geq k.

    • Suppose the opposite and that \nu_p(a_k) < \nu_p(a_1) for all k > N. Then for any n > N, we have

          \[ \nu_p \left( \frac{a_{n + 1}}{a_1} \right) < 0 \]


          \[ \nu_p \left( \frac{a_n}{a_1} \right) < 0. \]

      We also wish to rank \nu_p(a_{n + 1}) somewhere between \nu_p(a_1) and \nu_p(a_n) to get eventual constant-ness. We claim that

          \[ \nu_p(a_n) \leq \nu_p(a_{n + 1}) < \nu_p(a_1). \]

      Clearly \nu_p(a_{n + 1}) \geq \nu_p(a_1) is impossible by assumption, so we wish to invalidate the case \nu_p(a_{n + 1}) < \nu_p(a_n). In this case, we have \nu_p \left( \dfrac{a_n}{a_{n + 1}} \right) > 0 so in order for the \nu_p of the difference to be non-negative, the \nu_p of the other two terms must agree, or

          \[ \nu_p \left( \frac{a_n}{a_1} \right) = \nu_p \left( \frac{a_{n + 1}}{a_1} \right) \implies \nu_p(a_n) = \nu_p(a_{n + 1}), \]

      a contradiction. Thus by induction (again) we have shown that \nu_p(a_n) is eventually constant.

    • Combining both these claims yields the desired result. For each of the finitely many primes dividing a_1, \nu_p(a_n) eventually becomes constant. That COMBINED WITH the fact \nu_p(a_{n + 1}) \leq \nu_p(a_n) for all p \nmid a_1 implies a_{n + 1} \mid a_n for all n eventually and because of this, must be constant.

      A caveat as noted by v_Enhance, we need the non-increasing condition in the first claim because otherwise setting b_n = p_n a_n where a_n is a good sequence and p_n is the n-th prime causes a contradiction!

This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *