AIMO Initial Selection Mock Paper 4: Questions, Hints and Solutions

First let $n=p$ be prime. Each nonzero residue modulo $p$ has a unique inverse. The only residues equal to their own inverse satisfy $x^2=1$, so $p\mid(x-1)(x+1)$, forcing $x=1$ or $-1$. All other residues pair with a different inverse and contribute product 1. Therefore $(p-1)!\equiv-1\pmod p$.

Pairing instead $j$ with $p-j$, for $1\le j\le m$, gives $(p-1)!\equiv(-1)^m(m!)^2\pmod p$. Combining the two evaluations yields $(m!)^2\equiv(-1)^{m+1}\pmod p$.

Conversely, suppose the displayed congruence holds and $n$ is composite. Choose a prime divisor $q$ of $n$ with $q\le\sqrt n$. Since $n$ is odd, writing $n=qv$ gives $v\ge3$, and thus $q\le n/3\le(n-1)/2=m$. Hence $q\mid m!$. Reducing the assumed congruence modulo $q$ gives $0\equiv1$ or $0\equiv-1$, both impossible. Thus $n$ must be prime.

Conclusion: The congruence holds exactly for odd primes.

Review the idea: Complete and reduced residue systems · Unique prime factorisation · Factorials

Multiplicativity at 1 gives $f(1)=0$ or 1. If $f(1)=0$, the translation rule gives $f(0)=-1$, contradicting $f(0)=f(0)^2$. Hence $f(1)=1$ and $f(0)=0$. For $x\ne0$, $f(x)f(1/x)=1$, so $f(x)\ne0$.

For $x\ne0$, $$f(x+y)=f(x)f(1+y/x)=f(x)\bigl(1+f(y/x)\bigr)=f(x)+f(y).$$ The case $x=0$ is immediate. Thus $f$ is additive.

Why no continuity assumption is needed. If $t>0$, write $t=s^2$ with $s\ne0$. Then $f(t)=f(s)^2>0$. For $y>x$, additivity gives $f(y)-f(x)=f(y-x)>0$; therefore $f$ is strictly increasing.

Additivity and $f(1)=1$ give $f(k)=k$ for all integers, including negatives. For positive $q$, multiplicativity gives $qf(p/q)=f(p)=p$, so $f(r)=r$ for every rational $r$.

If $f(x)>x$, choose a rational $r$ strictly between them. Then $x<r$ forces $f(x)<f(r)=r$, a contradiction. If $f(x)<x$, choose a rational between these two numbers and argue the same way. Rationals exist between any two reals by choosing a sufficiently fine grid of fractions with one common denominator. Thus $f(x)=x$ for every real $x$. Direct substitution verifies this function.

Conclusion: The unique solution is f(x)=x.

Review the idea: Solving functional equations · Functions inverses and composition · Inequality rules and signs

Put $g=OG$. First suppose $g>0$, and take perpendicular coordinates with $O=(0,0)$, $G=(g,0)$. Write the vertex coordinates as $(a_1,a_2),(b_1,b_2),(c_1,c_2)$. The point whose coordinates are the vertex averages lies on every median: if M is the midpoint of BC, that candidate equals one third of A plus two thirds of M, coordinate by coordinate. It is therefore the intersection of the medians, namely G. Therefore $a_1+b_1+c_1=3g$ and $a_2+b_2+c_2=0$.

For $P=(u,v)$ on the circle, $u^2+v^2=R^2$. Each vertex also has squared distance $R^2$ from the origin. Expanding and adding yields $$PA^2+PB^2+PC^2=6R^2-2u(3g)-2v(0)=6R^2-6gu.$$ On the circle, $-R\le u\le R$. Thus the minimum is $6R^2-6Rg$, attained only at $P=(R,0)$, and the maximum is $6R^2+6Rg$, attained only at $P=(-R,0)$. These are the two intersections of line $OG$ with the circle, with the minimum on the ray $OG$.

If $G=O$, use any perpendicular axes. Both coordinate sums vanish, so the same expansion gives the constant value $6R^2$ at every point $P$. In that case every circle point attains both extrema.

Conclusion: Minimum 6R²−6R·OG and maximum 6R²+6R·OG; if O=G the value is constant.

Review the idea: The midpoint theorem · Pythagoras and stewart · Geometry foundations

At any vertex the $N-1$ incident edges need different colours, so at least $N-1$ colours are necessary. When $N=2n+1$, a colour can contain at most $n$ pairwise disjoint edges. There are $n(2n+1)$ edges altogether, so at least $2n+1$ colours are needed.

For $N=2n+1$, label vertices $0,1,\ldots,2n$, working modulo $2n+1$. Colour $\{a,b\}$ by $a+b$ modulo $2n+1$. At a fixed vertex $a$, different neighbours $b$ produce different colours. This gives a valid colouring using at most $2n+1$ colours, matching the lower bound.

For $N=2n$, let $m=2n-1$, and use vertices $0,1,\ldots,m-1$ together with one extra vertex $\infty$. Use $m$ colours, labelled modulo $m$. Give each finite edge $\{a,b\}$ colour $a+b$, and give edge $\{\infty,a\}$ colour $2a$. At a finite vertex $a$, its finite neighbours yield every colour except $2a$, because the omitted neighbour is $a$ itself. The edge to $\infty$ fills precisely that missing colour. At $\infty$, the colours $2a$ are distinct, because $m$ is odd and multiplication by 2 is invertible modulo $m$. For $m=1$, there is simply one edge and one colour.

Thus the minima are $2n-1$ colours for $2n$ vertices and $2n+1$ colours for $2n+1$ vertices.

Conclusion: The minima are 2n−1 for 2n vertices, and 2n+1 for 2n+1 vertices.

Review the idea: Complete and reduced residue systems · Counting

For $j=0,\ldots,n$, define $$L_j(x)=\prod_{\substack{0\le k\le n\\k\ne j}}\frac{x-k}{j-k}.$$ This is 1 at $x=j$ and 0 at every other specified node. Consequently $P(x)=\sum_{j=0}^nP(j)L_j(x)$: the difference has degree at most $n$ and vanishes at $n+1$ distinct points, so it is the zero polynomial.

At the next integer, the numerator product is $(n+1)!/(n+1-j)$, while the denominator is $(-1)^{n-j}j!(n-j)!$. Therefore $$L_j(n+1)=(-1)^{n-j}\binom{n+1}{j}.$$ It follows that $$|P(n+1)|\le\sum_{j=0}^n\binom{n+1}{j}|P(j)|\le\sum_{j=0}^n\binom{n+1}{j}=2^{n+1}-1.$$

All the binomial coefficients are positive. Equality requires every $|P(j)|=1$, and all the signed terms $(-1)^{n-j}P(j)$ to have the same sign. Thus the only possible node values are $P(j)=\varepsilon(-1)^{n-j}$, with one common $\varepsilon\in\{1,-1\}$. They determine the two polynomials $$P(x)=\varepsilon\sum_{j=0}^n(-1)^{n-j}L_j(x).$$ These polynomials satisfy the node bounds and attain $|P(n+1)|=2^{n+1}-1$, proving both the maximum and the complete equality classification.

Conclusion: Maximum 2ⁿ⁺¹−1; exactly the two interpolants with alternating node values ±1 attain it.

Review the idea: Remainder and factor theorems · Combinations and binomial coefficients

Write $t=v_p(a-b)\ge1$. We first prove a one-step rule. Suppose $X-Y=p^sc$, where $s\ge1$, $p\nmid c$, and $p\nmid XY$. Expand $$(Y+p^sc)^p-Y^p=pY^{p-1}p^sc+\sum_{j=2}^{p-1}\binom pjY^{p-j}p^{sj}c^j+p^{sp}c^p.$$ The first term is divisible by $p^{s+1}$ but not $p^{s+2}$. Each middle binomial coefficient is divisible by $p$, because $p$ is prime and its denominator has no factor $p$. Hence every middle term is divisible by $p^{1+2s}$, which is at least $p^{s+2}$. The last term is also divisible by $p^{s+2}$, since $sp\ge s+2$ for odd $p$ and $s\ge1$. After division by $p^{s+1}$, only the first term is nonzero modulo $p$. Thus $v_p(X^p-Y^p)=s+1$.

Now write $n=p^ku$, where $p\nmid u$. Factoring gives $$\frac{a^u-b^u}{a-b}=a^{u-1}+a^{u-2}b+\cdots+b^{u-1}\equiv u b^{u-1}\not\equiv0\pmod p.$$ Therefore $v_p(a^u-b^u)=t$. Apply the one-step rule $k$ times, successively raising $a^u,b^u$ to their $p$-th powers. Their difference exponent increases by 1 each time, so its final value is $t+k$. This proves the formula.

For $a=8,b=1,p=7,n=7^k$, the initial difference is 7, of exponent 1. Thus $v_7(8^{7^k}-1)=k+1$: it is divisible by $7^{k+1}$ and not by $7^{k+2}$.

Conclusion: The exponent is vₚ(a−b)+vₚ(n); the exact power in the example is 7ᵏ⁺¹.

Review the idea: Unique prime factorisation · Binomial expansions and generating functions · Divisibility