RMO Mock Paper 4: 6 Questions and Solutions

Factor $n^5+5n^3-6n=n(n^2-1)(n^2+6)$. One of $n-1,n,n+1$ is divisible by 3. For divisibility by 4, if $n$ is odd then $n^2-1$ is divisible by 8. If $n$ is divisible by 4, use its own factor. If $n\equiv2\pmod4$, both $n$ and $n^2+6$ are even, providing a factor 4. Modulo 5, $n^5\equiv n$ by checking the five residues, so the original expression is $n-6n\equiv0$. As 3,4,5 are pairwise coprime, 60 divides every value.

At $n=2$, the value is $32+40-12=60$. Any universal divisor must divide this value, hence cannot exceed 60. The required greatest divisor is 60.

Answer / conclusion: 60.

Review the idea: Divisibility · Remainders

Squaring $x+y+z=0$ gives $xy+yz+zx=-7$. Therefore $$(t-x)(t-y)(t-z)=t^3-7t-6=(t-3)(t+1)(t+2).$$ The roots of the left side, with multiplicities, are exactly $x,y,z$. The right side has the three distinct roots $3,-1,-2$, so the triple is a permutation of $(3,-1,-2)$. Conversely this triple has sum 0, square sum $9+1+4=14$, and product 6. All six permutations therefore work, and there are no others.

Answer / conclusion: All six permutations of (3,−1,−2).

Review the idea: Vietas formulas · Symmetric polynomials

Let $O$ be the circle’s centre and let the diagonals meet at $P$. Use the four arcs $AB,BC,CD,DA$ between consecutive vertices; their measures sum to $360^\circ$. We first derive the needed angle relation from the inscribed-angle theorem. Since $P$ is on $AC$ and $BD$, $$\angle PAB=\angle CAB=\tfrac12\operatorname{arc}(BC),\qquad \angle PBA=\angle DBA=\tfrac12\operatorname{arc}(DA).$$ The angle sum in triangle $APB$ therefore gives $$\angle APB=180^\circ-\frac{\operatorname{arc}(BC)+\operatorname{arc}(DA)}2=\frac{\operatorname{arc}(AB)+\operatorname{arc}(CD)}2.$$

The diagonals are perpendicular, so $\angle APB=90^\circ$. Hence the two arcs $AB,CD$ have total measure $180^\circ$. Let their half-measures be $u,v$, respectively. Both are positive and $u+v=90^\circ$. A chord whose central angle is $2u$ has length $2R\sin u$: bisect the isosceles triangle formed by the chord and its two radii, and use sine in either right half. Applying this to the two chords gives $$AB=2R\sin u,\qquad CD=2R\sin v=2R\cos u.$$ Therefore $$AB^2+CD^2=4R^2(\sin^2u+\cos^2u)=4R^2.$$ For $AB=5$, $CD=12$, this gives $4R^2=25+144=169$, so $R=13/2$.

Answer / conclusion: R=13/2 for side lengths 5 and 12.

Review the idea: Circles and power of a point · Trigonometry in geometry

A monochromatic triangle has all three edges of the same colour. At vertex $i$, let $d_i$ be its red degree, meaning the number of red edges meeting it. Of its six incident edges, $6-d_i$ are blue. To choose two incident edges of different colours, choose one of the $d_i$ red edges and one of the $6-d_i$ blue edges. This gives $d_i(6-d_i)$ choices. Since $$d_i(6-d_i)=9-(d_i-3)^2\le9,$$ the total over seven vertices is at most 63.

Each such mixed pair determines a triangle, because the other two endpoints are joined by an edge. A triangle with two red edges and one blue edge contributes exactly two mixed pairs, one at each endpoint of its blue edge; the remaining vertex has two red edges. A triangle with two blue edges and one red edge is counted twice in the same way. A monochromatic triangle contributes no mixed pair. Thus, if $T$ is the number of non-monochromatic triangles, $$2T=\sum_{i=0}^{6}d_i(6-d_i)\le63.$$ Since $T$ is an integer, $T\le31$. There are $\binom73=35$ triangles altogether, so at least $35-31=4$ are monochromatic.

To attain four, label the vertices $0,1,\ldots,6$. Colour red the seven cycle edges $01,12,23,34,45,56,60$, together with $03,15,26$. Colour every other edge blue.

Each cycle vertex has two red neighbours. The three additional red edges have six different endpoints, so vertices $0,1,2,3,5,6$ have red degree 3, while vertex 4 has red degree 2. The exact counting identity now gives $$2T=6(3\cdot3)+2\cdot4=62,\qquad T=31.$$ Hence this colouring has exactly $35-31=4$ monochromatic triangles, proving the bound is attainable.

Answer / conclusion: At least four, and four is attainable.

Review the idea: Counting · Combinations and binomial coefficients

Because $a+b+c=1$, the required difference between right and left sides can be written as $$(a+b+c)^3+9abc-4(a+b+c)(ab+bc+ca).$$ Expanding and collecting terms shows that this is $$a(a-b)(a-c)+b(b-c)(b-a)+c(c-a)(c-b).$$ The original expression is symmetric, so relabelling the variables does not change it. We may therefore assume $a\ge b\ge c\ge0$.

In the second term, use $b-a=-(a-b)$; in the last term, reverse both signs, so $(c-a)(c-b)=(a-c)(b-c)$. Factoring the first two terms then gives $$(a-b)\bigl(a(a-c)-b(b-c)\bigr)+c(a-c)(b-c).$$ The bracket simplifies as follows: $$a(a-c)-b(b-c)=a^2-b^2-c(a-b)=(a-b)(a+b-c).$$ Thus the difference is $$(a-b)^2(a+b-c)+c(a-c)(b-c)\ge0.$$ Both terms are nonnegative: $a+b-c\ge a\ge0$, and $c,a-c,b-c$ are all nonnegative. This proves the inequality.

If $a>b$, then $(a-b)^2>0$ and $a+b-c\ge a>0$, so the first term is positive. Equality therefore requires $a=b$. The second term becomes $c(a-c)^2$, which is zero precisely when $c=0$ or $c=a$. Together with $a+b+c=1$, these give $(a,b,c)=(1/2,1/2,0)$ or $(1/3,1/3,1/3)$ in the chosen ordering. Restoring all orders, the equality cases are the permutations of $(1/2,1/2,0)$ and the equal triple $(1/3,1/3,1/3)$. Substitution verifies each.

Answer / conclusion: Equality at (1/3,1/3,1/3) and permutations of (1/2,1/2,0).

Review the idea: Symmetric polynomials · Sum of squares

Let $p$ be the smallest prime divisor of $n$. Since $n>1$ is odd, $p\ge3$. The assumption gives $2^n\equiv-1\pmod p$, and squaring gives $2^{2n}\equiv1\pmod p$. By Fermat’s little theorem, $2^{p-1}\equiv1\pmod p$, because $p$ is an odd prime. Thus at least one positive exponent gives residue 1. Let $d$ be the least such exponent.

We need a small divisibility fact about $d$. If $2^m\equiv1\pmod p$, divide $m$ by $d$, writing $m=qd+r$ with $0\le r<d$. Then $$2^m=(2^d)^q2^r\equiv2^r\pmod p.$$ Hence $2^r\equiv1\pmod p$. A positive $r<d$ would contradict the minimality of $d$, so $r=0$. This proves $d\mid m$. Applying the fact twice, we have $d\mid2n$ and $d\mid p-1$.

Also, $\gcd(n,p-1)=1$: any common prime divisor would be a prime divisor of $n$, so at least $p$, but it would divide the smaller positive number $p-1$, which is impossible. Therefore $2n$ and $p-1$ can have no common odd prime factor. Since $n$ is odd, $2n$ contains only one factor of 2. It follows that $\gcd(2n,p-1)\le2$. As $d$ divides both numbers, $d\le2$. We cannot have $d=1$, since $2\not\equiv1\pmod p$. Thus $d=2$, so $p\mid2^2-1=3$, forcing $p=3$. In particular, $3\mid n$.

For infinitely many examples, we prove by induction that $$3^{k+1}\mid2^{3^k}+1\qquad(k\ge0).$$ At $k=0$, this says $3\mid3$. For the induction step put $A=2^{3^k}$. The induction hypothesis says that $A+1$ contains a factor $3^{k+1}$; it also gives $A\equiv-1\pmod3$. Consequently $A^2-A+1\equiv1+1+1\equiv0\pmod3$. Factoring, $$2^{3^{k+1}}+1=A^3+1=(A+1)(A^2-A+1).$$ The first factor is divisible by $3^{k+1}$, and the second supplies another factor of 3. Their product is therefore divisible by $3^{k+2}$, completing the induction. For every $k\ge1$, taking $n=3^k$ gives an odd integer greater than 1 with $n\mid2^n+1$. These infinitely many distinct values prove the second claim.

Answer / conclusion: 3 divides n; every positive power of 3 is an example.

Review the idea: Number theory theorems · Unique prime factorisation · Mathematical induction the first principle