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

Bridge: fractions in a congruence. If a denominator is coprime to a modulus, it has an inverse modulo that modulus: Bézout’s identity supplies integers $u,v$ with $bu+mv=1$. In a congruence, $a/b$ means $au$. Ordinary addition and multiplication remain valid after multiplying through by the denominators.

Put $H=\sum_{k=1}^{p-1}1/k$. Its reduced denominator $B$ is not divisible by $p$, since a common denominator is $(p-1)!$. Let $T=\sum_{k=1}^{p-1}k^{-2}\pmod p$. Multiplication by 2 permutes the nonzero residues, so $T=\sum(2k)^{-2}=4^{-1}T$. Consequently $3T=0\pmod p$. As $p\ne3$, this gives $T=0\pmod p$.

Reindex one copy of $H$ by $p-k$: $$2H=\sum_{k=1}^{p-1}\left(\frac1k+\frac1{p-k}\right)=p\sum_{k=1}^{p-1}\frac1{k(p-k)}.$$ Modulo $p$, the final sum is $-T=0$. Multiplication by $p$ therefore makes it zero modulo $p^2$. Thus $2H=0\pmod{p^2}$. The integer 2 is invertible modulo the odd number $p^2$, giving $H=0\pmod{p^2}$. Finally, multiply $A/B=0\pmod{p^2}$ by the invertible denominator $B$: $A=0\pmod{p^2}$, as required.

Conclusion: The reduced numerator is divisible by p².

Review the idea: Complete and reduced residue systems · Greatest common divisor

Call a column a neighbour of a row when their intersection entry is positive. For a set $S$ of rows, write $N(S)$ for all its neighbouring columns. Its entries sum to $r|S|$. These entries lie in $N(S)$, whose full columns sum to $r|N(S)|$. Nonnegativity gives $r|S|\le r|N(S)|$, hence $|N(S)|\ge|S|$.

Bridge: why this counting condition gives a selection. We prove this for any equal numbers of rows and columns by induction on their number. One row is immediate. Suppose first that a nonempty proper row set $S$ has exactly $|S|$ neighbours. The condition holds inside these rows and columns, so induction matches them. For rows $T$ outside $S$, the condition applied to $S\cup T$ gives $|N(S\cup T)|\ge|S|+|T|$. After removing the $|S|$ columns of $N(S)$, at least $|T|$ neighbours of $T$ remain. Induction matches all remaining rows to the remaining columns.

In the other case every nonempty proper row set has at least one more neighbour than its size. Choose any row and one of its neighbours, match them, and delete this row and column. A nonempty set $T$ of remaining rows was a proper set originally, so it had at least $|T|+1$ neighbours. Deleting one column leaves at least $|T|$. Induction therefore matches the remaining rows too.

Both cases complete the matching proof. Applying it to the array selects one positive entry in every row, in distinct columns. Since there are $n$ selected columns among $n$, every column is used exactly once.

Conclusion: Such a selection always exists.

Review the idea: Pigeonhole principle · Proof methods

Equal tangent lengths from each vertex give the stated positive numbers $x,y,z$. The two segments $AD$ and $BE$ meet inside the triangle: each joins a vertex to an interior point of the opposite side, and their endpoints alternate around the boundary. Denote their intersection by $P$.

Area-ratio bridge. Triangles $ABD$ and $ACD$ share their altitude from $A$ to $BC$, so their area ratio is $BD/DC$. Replacing $D$ by $P$ on the segment $AD$ scales both areas by $AP/AD$; therefore $[PAB]/[PCA]=BD/DC=y/z$. Applying the same argument along $BE$ yields $[PBC]/[PAB]=CE/EA=z/x$.

Thus $$[PBC]:[PCA]:[PAB]=yz:xz:xy.$$ Let the ray $CP$ meet $AB$ at $F'$. The same area-ratio rule gives $AF'/F'B=[PCA]/[PBC]=x/y$. There is exactly one point of $AB$ dividing it in this positive ratio; the contact point $F$ has that ratio. Hence $F'=F$, proving the third cevian also passes through $P$.

The three small triangles partition $ABC$, so $$\boxed{\frac{[PBC]}{[ABC]}=\frac{yz}{xy+yz+zx}.}$$ All denominators are positive because the contact points lie on the side interiors.

Conclusion: The cevians concur, and the area ratio is yz/(xy+yz+zx).

Review the idea: Triangle area ratios · Circles and power of a point

Multiplicativity gives $f(1)=f(1)^2$; positivity forces $f(1)=1$. Fix $n\ge2$. For any positive integer $m$, choose the unique nonnegative integer $k$ for which $2^k\le n^m<2^{k+1}$. Such a $k$ exists because successive powers of 2 grow without bound.

By monotonicity and multiplicativity, $$4^k\le f(n^m)=f(n)^m<4^{k+1}.$$ Squaring the first comparison gives $4^k\le n^{2m}<4^{k+1}$. Dividing the two positive bounds therefore yields $$\begin{gathered}\frac14<\left(\frac{f(n)}{n^2}\right)^m<4\\(m\ge1).\end{gathered}$$

Bridge: bounded powers. A fixed positive number $t$ whose every positive integer power stays between $1/4$ and 4 must be 1. If $t=1+\varepsilon>1$, induction gives $t^m\ge1+m\varepsilon$, eventually exceeding 4. If $t<1$, apply the same argument to $1/t>1$, eventually forcing $t^m<1/4$.

Apply this to $t=f(n)/n^2$. It gives $f(n)=n^2$ for every $n\ge2$, and also for $n=1$. Conversely, $f(n)=n^2$ is positive, strictly increasing and multiplicative, and has $f(2)=4$. It is the unique solution.

Conclusion: f(n)=n² for every positive integer n.

Review the idea: Functions inverses and composition · Mathematical induction the first principle

For each $i$, the assumptions give $(M-x_i)(x_i-m)\ge0$. Dividing its expansion by the positive $x_i$ gives $x_i+mM/x_i\le M+m$. Multiply by $w_i$ and sum. With $A=\sum w_i x_i$ and $B=\sum w_i/x_i$, we obtain $A+mMB\le M+m$.

The square $(A-mMB)^2\ge0$ is equivalent to $4mMAB\le(A+mMB)^2$. Hence $$4mMAB\le(A+mMB)^2\le(M+m)^2,$$ which proves the required inequality.

For equality in the first summed bound, every positive-weight term must be an equality. Therefore each $x_i$ is either $m$ or $M$. Let $t$ be the total weight of the entries equal to $m$. Then $A=tm+(1-t)M$ and $mMB=tM+(1-t)m$. Equality in the square requires $(2t-1)(m-M)=0$, so $t=1/2$.

Conversely, if all entries are endpoints and the total weight at each endpoint is $1/2$, both inequalities are equalities. These are all equality cases. Choosing $n=2$, equal weights and $(x_1,x_2)=(m,M)$ attains the bound, so no smaller universal constant can replace it.

Conclusion: Equality exactly when all xᵢ are endpoints and each endpoint carries total weight 1/2.

Review the idea: Weighted means · Sum of squares

There are only $n!$ red-to-blue pairings, so at least one minimises the total length. Choose such a pairing. Suppose two of its segments $R_1B_1$ and $R_2B_2$ cross at an interior point $X$.

Replace these pairs by $R_1B_2$ and $R_2B_1$, keeping every other pair. This is still a valid pairing. The triangle inequality gives $$\begin{gathered}R_1B_2<R_1X+XB_2,\\ R_2B_1<R_2X+XB_1.\end{gathered}$$ The inequalities are strict: equality in either would put three of the original points on one line, contrary to the assumption. Adding, and using that $X$ lies on the two original segments, gives $$R_1B_2+R_2B_1<R_1B_1+R_2B_2.$$ This contradicts minimality.

Thus no two paired segments cross in their interiors. They cannot share endpoints because each point is used once. Nor can an endpoint of one lie inside another segment, because that would make three original points collinear. Collinear overlaps are excluded for the same reason. The minimum-length pairing therefore has the required complete absence of intersections.

Conclusion: A minimum-total-length red-to-blue pairing has no segment intersections.

Review the idea: Triangle inequalities · Proof methods