China National Maths. Olympiad 2016 – 17

  1. Define sequence u_0 = u_1 =1, u_n =2u_{n-1}-3u_{n-2} for n \ge 2. Define v_0 = a, v_1 =b, v_2 =c, v_n = v_{n-1}-3v_{n-2}+27v_{n-3} for n \ge 3. Suppose that there exists N \in \mathbb N^+ such that \forall n \ge N, u_n | v_n. (In particular this implies v_n \texttt{'}s are integers for large enough n.) Show that 3a = 2b +c.
  2. In scalene \triangle ABC , I is the incentre. (I.e. centre of incircle.) The tangents at B and C to the circumcircle of \triangle ABC intersect at L. The incircle touches the side BC at D. Drop perpendicular from A to BC, intersecting BC at Y. AO intersects BC at X. Let line OI intersect the circumcircle of \triangle ABC at P,Q. Show that: A,D,L are colinear if and only if P,Q, X, Y are con-cyclic.
  3. Let \mathcal R be a closed rectangle. Let \mathcal R be dissected into 2016 smaller rectangles, whose sides are parallel to either side of \mathcal R. The vertices of the smaller rectangles are called ‘nodes‘. A segment (which must be part of the partition) joining two nodes is called a basic segment if it contains no nodes other than its two endpoints. Find the maximum number and minimum number of basic segments across all dissecting configurations.
  4. Let integer n \ge 2. For two permutations of \{1,2, ..., n\}: \alpha = (a_1, a_2, ..., a_n) and \beta = (b_1, b_2, ... , b_n), we call them turnings of each other, if there exists positive integer k \le n such that \\ b_i = a_{k+1-i} \,\,\,\,\, 1\le i \le k; \\ b_i = a_i\,\,\,\,\, k < i \le n  \,. Prove:It is possible to arrange all permutations of \{1,2,...,n\} into a sequence P_1, P_2, ... P_{n!} such that for all i = 1,2, ..., n!, P_i and P_{i+1} are turnings of each other. Here we let P_{n!+1}=P_1.
  5. Let \mathcal {D}_n denote the set of all positive integral divisors of positive integer n. Find all positive integer n such that \mathcal {D}_n can be written as the union of two DISJOINT subsets \mathcal {A} and \mathcal G, which satisfy : |\mathcal A| \ge 3, |\mathcal G|\ge 3, the elements of \mathcal A can be arranged into an arithmetic progression, and the elements of \mathcal G can be arranged into a geometric progression.
  6. Let n\ge 2 be a given integer. Let a,b be two given positive numbers with a<b. Suppose real numbers x_1, x_2, ... x_n \in [a,b], find the maximum value of

\displaystyle \frac {\frac{x_1^2}{x_2}+\frac{x_2^2}{x_3}+ ... +\frac{x_{n-1}^2}{x_n}+\frac{x_n^2}{x_1}}{x_1 + x_2 + ... + x_{n-1}+x_n} .

Q1. My friend Jongmin Lim sent me the following solution. I have been working on it for a a rather extended period, but I constrained myself into a suboptimal approach that proved ultimately unsuccessful.

BTW this Jongmin dude did the IMO at some point in his life. Got 23/42, i.e. barely passed. But the IMO, currently being inundated with people from scrub countries, has a compromised awarding scheme, in which someone who did slightly better than barely passed can be awarded a silver medal; and upon the OP, who, despite his friendship with Jongmin, is consistently scrub-like in Olympiad problem solving, and who almost hit the 50% line but, notwithstanding the maximal effort from Team Leader and Deputy Leader which earned him marks that the OP is not sure whether he would have received without being from an Anglophone country with a respectable Leader, did not quite, a bronze medal is bestowed to signify that fact that he could solve the easiest problems and did not black out on the problems that are more becoming of the IMO’s prestige.

So the problem gave us recursions, linear recursions which we can actually solve. Whenever such thing comes around, solving it is never a bad idea because it doesn’t take up much time and it can be illuminating.

\displaystyle u_n=\frac{(1+\sqrt 2 i)^n+ (1-\sqrt 2 i)^n}{2}, v_n = \alpha 3^n + \beta (-1+2\sqrt 2 i)^n+\gamma(-1-2\sqrt 2 i)^n .

Okay… We see that, if we denote \lambda = 1+\sqrt 2 i, \bar \lambda = 1-\sqrt 2 i, we have \lambda ^2 = -1+2 \sqrt 2 i, \bar \lambda ^2 = -1-2\sqrt 2 i, \lambda \bar \lambda = 3. Thus the two recursions are related in such a superficial way.

Since we have constructed three new parameters, we can express a,b, and c in terms of them. The conclusion, in new parameters, read: 3(\alpha + \beta + \gamma) = 2(3\alpha + (-1+2\sqrt 2 i)\beta + (-1-2\sqrt 2 i)\gamma)+ 9 \alpha + (-7 - 4 \sqrt 2 i)\beta + (-7 + 4\sqrt 2 i)\gamma \implies \alpha = \beta + \gamma. This looks a lot nicer.

The ‘eventually integer’ condition says a lot. We wish to exploit it.

\displaystyle \frac{v_n}{u_n}= \frac {2(\alpha - \beta -\gamma)3^n}{\lambda ^n + \bar \lambda ^n}+ 2(\beta \lambda ^n + \gamma \bar \lambda ^n). This transformation is crucial: it mimics the long division algorithm and  permits separate treatment of the remainder from the main part of the quotient.

We of course wish to have 2(\beta \lambda ^n +\gamma \bar \lambda ^n) is an integer and the other term, the remainder, to be disallowed from being an integer for very large n and thus to establish that the remainder is zero always. But that is not easy: how are we going to establish that the main part is an integer at all? It does indeed remind us of the v_n recursion itself, but the 3^n \alpha term is not at all easy to deal with.

Well, we shall have a closer look at the v_n because we have not really used the integer condition yet. We have that v_n \in \mathbb Z for all large n, from which we wish to recover, at least, the rationality of \alpha, \beta, \gamma.

So we let n be large and choose three consecutive values of n to start with.

3^n \alpha + \lambda ^{2n} \beta + \bar \lambda ^{2n} \gamma \in \mathbb Z; \\  3^{n+1} \alpha + \lambda ^{2n+2} \beta + \bar \lambda ^{2n+2} \gamma \in \mathbb Z; \\  3^{n+2} \alpha + \lambda ^{2n+4}\beta + \bar \lambda ^{2n+4} \gamma \in \mathbb Z.

No matter what the RHS is, we have a linear system in [\alpha, \beta, \gamma] with coefficients in \mathbb Z [\sqrt {-2}]. We thus wish to make further compromise and settle to prove that \alpha, \beta, \gamma \in \mathbb Q [\sqrt{-2}].

To do that, we only have to show that the coefficient matrix has non-zero determinant.

But a matrix with the first column 3^n[1,3,3^2]^T, second column \lambda ^{2n}[1,\lambda ^2, (\lambda^2)^2]^T, third column \bar \lambda^{2n} [1, \bar \lambda ^2, (\bar \lambda ^2)^2]^T has its determinant the form of a Vandermonde matrix, which vanishes if and only if the common ratios of two of its geometric progressions are equal. In this case we thus have a non-zero determinant and thus \alpha, \beta, \gamma \in \mathbb Q [\sqrt{-2}].

That wasn’t too bad. But how to proceed?

Key insight: the denominator of the rational number \displaystyle \frac{3^n (\alpha - \beta -\gamma)}{u_n} is unbounded. This is because: 3\not | u_n, \forall n. This is because, modulo 3, u_{n+1}\equiv -u_n. Now, since u_0 = u_1 = 1, u_n is never a multiple of 3. We need to show that u_n is unbounded. We will do that at the end of the proof. This is how we wish to establish the remainder is non-integer after all. Therefore it only remains to show that \beta \lambda ^{2n} + \gamma \bar \lambda ^{2n} has bounded denominator when written in simplest form to finish off the problem. (This is where I made the mistake, I strove to demonstrate that it is an integer, but bounded denominator suffices.)

Since \beta and \gamma are both in \mathbb Q [\sqrt{-2}], and \lambda, \bar \lambda \in \mathbb Z [\sqrt{-2}], we actually have that happening. Explicitly, for r+q\sqrt{2} i, where r,q \in \mathbb Q, r= \frac {\sigma_1}{\zeta_1}, q = \frac {\sigma_2}{\zeta_2} are called simplest form if |\sigma|+|\zeta| is minimised. We write it in simplest form, and define f(r+q\sqrt 2 i) = \textnormal{lcm} (\zeta _1, \zeta _2). It is easy to verify that multiplying an element in \mathbb Q [\sqrt {-2}] by an element in \mathbb Z [\sqrt{-2}] does not increase its f -value. Thus the f value of 2\beta \lambda ^n + 2\gamma \bar \lambda ^n is bounded. We are done, as for large value of n, \frac {v_n}{u_n}, has one component whose denominator is very large, thus not an integer.

Wait! I promised to show that u_n is unbounded, now it is time to actualise my promise. \displaystyle u_n = \Re ((1+\sqrt 2 i)^n) = \cos (\arg ((\frac{1}{\sqrt 3}+\frac{\sqrt 2}{\sqrt 3} i)^n))(\sqrt 3 )^n = (\sqrt 3)^n \cos (n\arccos (\frac {1}{\sqrt 3})). Therefore it suffices for the problem to show that there exists a sequence y_n \in \mathbb N^+ such that \displaystyle |\cos (\arccos (\frac {1}{\sqrt 3})y_n)| is lower bounded. That can be accomplished by showing the existence of infinitely many y_n such that \displaystyle \arccos{\frac{1}{\sqrt 3}}y_n, when divided by 2\pi, gives off a remainder that is within the interval \displaystyle [0, \arccos (\frac{1}{\sqrt 3})].

Suppose that \displaystyle \frac {\arccos (\frac {1}{\sqrt 3})}{2\pi} \in \mathbb Q, \displaystyle 2\pi |\arccos (\frac{1}{\sqrt 3}) y_n happens for y_n in an arithmetic progression. Suppose that  \displaystyle \frac {\arccos (\frac {1}{\sqrt 3})}{2\pi}= \eta is an irrational number, the sequence \{\eta n\} is dense in [0,1), where \{x\} denotes the fractional part of x. In particular, this shows the existence of infinitely many y_n \in \mathbb N^+ such that \displaystyle \{\frac {\arccos (\frac{1}{\sqrt 3})y_n}{2\pi} \}\in [0,\frac {\arccos (\frac{1}{\sqrt 3})}{2\pi}], or, \displaystyle \cos (\arccos (\frac{1}{\sqrt 3})y_n) \in [\frac {1}{\sqrt 3}, 1]. This shows that u_{y_n} \ge (\sqrt 3)^{y_n-1} which goes to infinity for large y_n.

Q5. This is all my own work, and I started writing this up as soon as I finished solving this problem by brute force base bash. I believe that while it might not be the most economical method, it is instructive to write up the most natural instinct when the problem is encountered. There are problems — e.g. IMO 2015 Q2, proposed by Dusan Djukic — for which no quick or enlightening methods exist. In such cases, as one is generally never informed of whether the problem he encounters is of this class, it is important to be able to bash. If any improvement on the bash method can be proposed, I will also include it as an alternative. For papers like IMO 15′ day 1, the contestants are discriminated by their ability to finish off bashing work efficiently and correctly. Many well-trained, talented contestants could not perform the bashing perfectly and got 6/7.