INMO Mock Paper 5: 6 Questions and Solutions

Because n is odd, the integers $1,\ldots,n-1$ split into $(n-1)/2$ pairs $k,n-k$. The binomial theorem gives $$(n-k)^n=(-k)^n+n\cdot n(-k)^{n-1}+\sum_{j=2}^n\binom nj n^j(-k)^{n-j}.$$ Every term after the first is divisible by $n^2$. Since n is odd, the first term is $-k^n$. Thus $k^n+(n-k)^n\equiv0\pmod{n^2}$ for each pair, and summing proves the divisibility. For n=3 the sum is $1^3+2^3=9$, which is not divisible by $3^3=27$. Therefore no universal replacement of the exponent 2 by 3 is possible.

Answer / conclusion: n² always divides the sum; n=3 disproves a universal n³ claim.

Review the idea: Binomial expansions and generating functions · Divisibility

Write $P(x)=x^2+ax+b$, with integers a,b. Polynomial division by a monic integer polynomial keeps integer coefficients. The notation $F(x)\equiv G(x)\pmod P$ means that $F-G$ is a polynomial multiple of $P$; the two polynomials therefore have the same remainder on division by $P$. Since $x^2\equiv-ax-b\pmod P$, replacing $x^2$ by $-ax-b$ gives $$x^4\equiv(-ax-b)^2=a^2x^2+2abx+b^2\equiv(-a^3+2ab)x+b^2-a^2b.$$ Adding the remainder of $ax^2+b$ gives the remainder of $P(x^2)=x^4+ax^2+b$, namely $$a(-a^2-a+2b)x+b(b-a^2-a+1).$$ Call it $Ax+B$, so $P(x^2)=Q(x)P(x)+Ax+B$, where $Q$ has integer coefficients. Evaluate at an integer $n$. The first term $Q(n)P(n)$ is already an integer multiple of $P(n)$; the hypothesis therefore implies $P(n)\mid An+B$ whenever $P(n)\ne0$. For all sufficiently large positive n, $|An+B|<|P(n)|$, because the right side is quadratic and the left linear. A nonzero integer multiple of $P(n)$ has absolute value at least $|P(n)|$. Hence the smaller divisible remainder must be zero: $An+B=0$ for all such $n$. A linear polynomial vanishing at infinitely many inputs is zero, so $A=B=0$.

If a=0, then $b(b+1)=0$, giving $x^2,x^2-1$. If $a\ne0$, then $2b=a^2+a$. When b=0 this gives a=−1, hence $x^2-x$. When b≠0, the second equation gives $b=a^2+a-1$; combining gives $a^2+a=2$, so $(a,b)=(1,1),(-2,1)$. The remaining polynomials are $x^2+x+1$ and $(x-1)^2$. For each of the five candidates the remainder is identically zero, so $P(x)$ divides $P(x^2)$ as an integer polynomial. Evaluation proves the required integer divisibility wherever the divisor is nonzero.

Answer / conclusion: x², x²−1, x²−x, x²+x+1, (x−1)².

Review the idea: Polynomial division · Factorisation integer solutions

In angle expressions, write $A,B,C$ for the angles at the corresponding triangle vertices, so $A+B+C=180^\circ$. Let $D$ be the midpoint of the arc $BC$ not containing $A$. Equal arcs $BD,DC$ subtend equal angles $BAD,DAC$; thus $AD$ is the internal bisector, which passes through $I$. Since $I$ lies inside the circumcircle, the points occur in the order $A,I,D$. The chord formula from the extended sine rule gives $DB=2R\sin\angle DAB=2R\sin(A/2)$.

Angles $CBD$ and $CAD$ both subtend chord $CD$, so $\angle CBD=A/2$. Since $BI$ bisects angle $B$, $\angle IBC=B/2$. These angles add to give $\angle IBD=(A+B)/2=90^\circ-C/2$. In triangle $AIB$, the angles at $A,B$ are $A/2,B/2$, hence $\angle AIB=180^\circ-(A+B)/2=90^\circ+C/2$. The ray $ID$ points oppositely to $IA$, so $\angle BID=180^\circ-\angle BIA=90^\circ-C/2$. Therefore $\angle IBD=\angle BID$, making triangle $BID$ isosceles with $ID=DB$.

If T is the perpendicular foot from I to AB, then $IT=r$ and right triangle AIT gives $AI=r/\sin(A/2)$. Therefore $AI\cdot ID=2Rr$. The point I is inside the circumcircle, so its power is $-AI\cdot ID=OI^2-R^2$. Rearranging yields $OI^2=R^2-2Rr$.

As $OI^2\ge0$ and R>0, $R\ge2r$. Equality is equivalent to O=I. In that case all three side-lines are distance r from O, so all three chords have the same length $2\sqrt{R^2-r^2}$; the triangle is equilateral. Conversely its centres coincide. Finally $r=2$, $OI^2=5$ give $R^2-4R-5=0$, whose only positive root is R=5.

Answer / conclusion: R≥2r; equality precisely for an equilateral triangle. Numerical R=5.

Review the idea: Circles and power of a point · Parallel lines and angle bisectors · Trigonometry in geometry

Draw one vertex for each player and an arrow $U\to V$ when $U$ defeated $V$. Between each pair there is exactly one arrow. A directed path follows the arrows. A directed cycle returns to its starting vertex without repeating another vertex. “Strongly connected” means that every vertex can reach every other by a directed path.

The game diagram is strongly connected. Otherwise, for some starting player, the set $S$ of reachable players would be a proper subset. No arrow leaves $S$, or its endpoint would also be reachable. Each player in $S$ has four outgoing arrows, all within $S$, so $|S|\ge5$. Every player outside $S$ must then defeat every player in $S$, giving at least five wins, a contradiction.

There is a directed cycle: repeatedly follow an outgoing arrow; finiteness forces a repeated vertex, and the segment from its first occurrence to its next one is a cycle. Choose a directed cycle $C$ of greatest length. For an outside vertex $v$, mark each cycle vertex “+” if it defeats $v$, and “−” if $v$ defeats it. If both signs occur, walking around the cyclic list must somewhere pass from “+” to “−”. The corresponding consecutive vertices satisfy $c_i\to v\to c_{i+1}$. Replacing their old edge by those two arrows inserts $v$, contradicting maximal length. Thus each outside vertex either defeats every vertex of $C$ (class $U$), or loses to every vertex of $C$ (class $V$).

If any vertex remained outside, both classes would be nonempty: with no $V$, no arrow could leave $C$; with no $U$, no outside path could enter $C$. Either case contradicts strong connectivity. There must also be an arrow $v\to u$ with $v\in V,u\in U$. Otherwise arrows out of $C$ lead only into $V$, and arrows out of $V$ never enter $U$; no path from $C$ could reach $U$, another contradiction.

Now replace any cycle edge $c_i\to c_{i+1}$ by $c_i\to v\to u\to c_{i+1}$, as in the schematic. These arrows exist by the definitions of $V,U$ and the chosen arrow $v\to u$. Both new vertices are outside the old cycle and distinct, so this is a longer directed cycle.

This contradicts the choice of $C$. Hence no vertex is outside it: it passes through all nine players, giving the required circular arrangement.

Answer / conclusion: A directed cycle through all nine players exists.

Review the idea: Counting · Proof methods

Pair $(a_1,a_2),(a_3,a_4),\ldots,(a_{19},a_{20})$, and set $d_j=a_{2j}-a_{2j-1}$, so $0\le d_j\le M$. Splitting one entry of every pair into each group ensures ten entries per group. The difference of group sums can be chosen as any signed sum $\sum_j\varepsilon_jd_j$, with $\varepsilon_j\in\{1,-1\}$.

Start with running sum 0. If the current sum is nonnegative, use the next sign −; if it is negative, use +. Whenever the old sum lies in $[-M,M]$, adding a number in $[0,M]$ toward zero leaves the new sum in the same interval. Induction therefore produces a final absolute difference at most M.

For sharpness, take nineteen zeros and one 1. Then M=1, and any two ten-entry groups have sums 0 and 1 in some order, so their difference is exactly M. No universal smaller coefficient can work.

Answer / conclusion: A split with difference at most M always exists; the coefficient 1 is sharp.

Review the idea: Proof methods · Absolute value inequalities

Choose an integer a with $c=P(a)\ne0$; such an a exists because a nonzero polynomial has only finitely many roots. Suppose the primes dividing nonzero integer values of P formed a finite list, with product M (take M=1 for an empty list). Expand $$Q(t)=\frac{P(a+cMt)}c.$$ The constant term is 1. Every higher coefficient is an integer multiple of M: in expanding each power of $a+cMt$, a term containing $t^j$, j≥1, includes $(cM)^j/c=c^{j-1}M^j$. Thus Q is a nonconstant integer polynomial and $Q(t)\equiv1\pmod M$ for every integer t.

For some integer t, $|Q(t)|>1$, since the highest-degree term eventually dominates the sum of the lower terms. Let q be a prime divisor of this nonzero integer. Because $Q(t)\equiv1\pmod M$, q does not divide M. But $P(a+cMt)=cQ(t)$ is nonzero and divisible by q, contradicting completeness of the list. Therefore infinitely many primes occur.

Answer / conclusion: Infinitely many distinct prime divisors occur among the nonzero values.

Review the idea: Polynomial functions · Prime numbers · Divisibility