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

Repeated difference of squares gives $$\begin{gathered}F_0F_1\cdots F_{j-1}=2^{2^j}-1=F_j-2\\(j\ge1).\end{gathered}$$ One may also prove this by induction: multiplying $2^{2^j}-1$ by $2^{2^j}+1$ produces $2^{2^{j+1}}-1$. If $i<j$, a common divisor of $F_i,F_j$ therefore divides 2. Both numbers are odd, so their gcd is 1.

Let a prime $q\mid F_j$. It is odd, and $2^{2^j}\equiv-1\pmod q$. Thus $2^{2^{j+1}}\equiv1$, while $2^{2^j}\not\equiv1$. Let $d$ be the smallest positive exponent giving residue 1. Dividing any such exponent by $d$ with remainder shows that the remainder must be 0, by minimality. Hence $d\mid2^{j+1}$. All divisors of this number are powers of 2, and $d\nmid2^j$; consequently $d=2^{j+1}$.

Why the order divides $q-1$. Multiplication by 2 permutes the nonzero residues modulo $q$. Multiplying all those residues and cancelling $(q-1)!$, which is coprime to $q$, gives $2^{q-1}\equiv1\pmod q$. The same division-with-remainder argument yields $d\mid q-1$. Hence $q\equiv1\pmod{2^{j+1}}$.

For any $k\ge1$, the integer $F_{k-1}>1$ has a prime divisor. That divisor is 1 modulo $2^k$, proving the final assertion. The pairwise coprimality also shows that prime divisors chosen from different $F_j$ are distinct.

Conclusion: The Fermat numbers are pairwise coprime, and their prime divisors have the stated congruence.

Review the idea: Complete and reduced residue systems · Algebraic identities · Prime numbers

Let $H(x)=\sum w_i/(x-a_i)$, defined away from the $a_i$. If $x<y$ lie in the same interval between consecutive poles, then $$\begin{gathered}(x-a_i)(y-a_i)>0,\\\frac1{x-a_i}-\frac1{y-a_i}=\frac{y-x}{(x-a_i)(y-a_i)}>0.\end{gathered}$$ Thus $H$ is strictly decreasing on each such interval, including the two unbounded outer intervals.

In $(a_i,a_{i+1})$, its values approach $+\infty$ at the left and $-\infty$ at the right. Because the rational expression is continuous there, it crosses the level $c$; strict decrease makes this crossing unique. This gives $n-1$ solutions. The continuity fact used here is that a continuous function taking values on both sides of a level must take that level in between.

On $(a_n,\infty)$, $H$ decreases from $+\infty$ to 0 through positive values, giving exactly one further solution if $c>0$, and none if $c<0$. On $(-\infty,a_1)$, it decreases from 0 to $-\infty$ through negative values, giving exactly one further solution if $c<0$. There are therefore exactly $n$ solutions in the claimed intervals.

They are roots of $$Q(x)=c\prod_{i=1}^n(x-a_i)-\sum_{i=1}^n w_i\prod_{j\ne i}(x-a_j).$$ No pole is a root: $Q(a_i)=-w_i\prod_{j\ne i}(a_i-a_j)\ne0$. The leading coefficient is $c$, and the next coefficient is $-c\sum a_i-\sum w_i$. Expanding $c\prod(x-r_i)$, where the $r_i$ are the $n$ solutions, therefore gives $$\sum r_i=\sum a_i+\frac{\sum w_i}{c}.$$

Conclusion: One solution in each inner gap and one in the outer interval with the sign of c; sum Σaᵢ+(Σwᵢ)/c.

Review the idea: Polynomial roots and multiplicity · Vietas formulas · Inequality rules and signs

Squared-distance bridge. For fixed points $U,V$ and a point $W$ on their line, the locus of points $T$ satisfying $TU^2-TV^2=WU^2-WV^2$ is the perpendicular to $UV$ through $W$. To see this, use coordinates $U=(0,0),V=(L,0),W=(s,0),T=(h,k)$. The equality becomes $2Lh-L^2=2Ls-L^2$, hence $h=s$, exactly that perpendicular line.

If the three perpendiculars meet at $T$, this bridge gives $$\begin{gathered}TB^2-TC^2=BD^2-DC^2,\\ TC^2-TA^2=CE^2-EA^2,\\ TA^2-TB^2=AF^2-FB^2.\end{gathered}$$ Adding cancels all distances from $T$ and proves the required condition.

Conversely, let $T$ be the intersection of the perpendiculars through $D$ and $E$. They are not parallel because $BC$ and $CA$ are not parallel. The first two identities hold. Their sum, together with the assumed condition, implies $TA^2-TB^2=AF^2-FB^2$. The bridge therefore places $T$ on the third perpendicular, proving sufficiency.

Finally, if all three ratios equal $t$, then $$BD^2-DC^2=\frac{t-1}{t+1}BC^2,$$ with analogous formulas on the other sides. The condition becomes $\frac{t-1}{t+1}(BC^2+CA^2+AB^2)=0$. Since the sum of squares is positive and $t+1>0$, it holds exactly when $t=1$. In that case the perpendiculars are the perpendicular bisectors and do concur.

Conclusion: Concurrence is equivalent to the squared-length identity; equal cyclic ratios require t=1.

Review the idea: Pythagoras and stewart · Geometry foundations · Concurrency and collinearity

Every move removes at least one cell, so the game is finite and has no draw. Working backwards from positions with only the poisoned cell shows that every position is either winning or losing for the player whose turn it is: a position is winning if there is a safe move to a losing position, and otherwise it is losing.

Suppose the first player removes only the far corner $(m,n)$. This move is safe. If it leaves the opponent a losing position, it is already a winning first move. Otherwise the opponent has a winning reply, say choosing a remaining safe cell $(i,j)$. A winning reply cannot remove the poison, because doing so loses immediately.

Now compare with a different first move from the untouched rectangle: choose that same cell $(i,j)$ immediately. Its removed upper-right rectangle already contains $(m,n)$, since $m\ge i$ and $n\ge j$. Hence the board left after this alternative first move is exactly the board left after the two moves in the previous paragraph.

The assumed winning reply left a losing position for its next player. Our alternative first move leaves precisely that position for the opponent. It is therefore a winning first move. In either case a winning first move exists.

This argument proves existence by analysing an opponent’s possible reply; it does not claim that removing the far corner is always the correct winning move.

Conclusion: The first player always has a winning strategy on every stated rectangle.

Review the idea: Strong induction · Proof methods

Parity bridge. Exchanging two labels changes inversion parity. For adjacent positions only their mutual order changes, so the inversion count changes by 1. A swap of positions $i<j$ can be achieved by $2(j-i)-1$ adjacent swaps: move the first label right to position $j$, then move the other left to position $i$. This is an odd number, proving the claim for every exchange.

A rotation of three positions is two exchanges, so it preserves inversion parity. The initial order has zero inversions; hence every reachable permutation has even inversion count.

Conversely, make the target permutation by a finite sequence of exchanges: place its first required label, then its second, and so on. If the target is even, the number of exchanges in this sequence is even, by the parity claim. Group the exchanges in consecutive pairs.

Two identical exchanges cancel. Two different exchanges sharing one position compose to a three-position rotation. If two exchanges use four distinct positions, write them as swaps $(a,b)$ and $(c,d)$. Insert the same swap $(b,c)$ twice between them, which changes nothing. The four-swap sequence now groups as $[(a,b),(b,c)]$ followed by $[(b,c),(c,d)]$; each bracket is a rotation of three positions. Thus every paired exchange can be performed with allowed moves. The target is reachable.

Finally, swapping the first two positions is a bijection between even and odd permutations, because it toggles parity and is its own inverse. Exactly half of the $n!$ permutations are even. Hence the number reachable is $n!/2$.

Conclusion: Exactly the even permutations are reachable; their number is n!/2.

Review the idea: Permutations and arrangements · Parity · Proof methods

The root is reduced. If $\gcd(a,b)=1$, then $\gcd(a,a+b)=\gcd(a+b,b)=1$, so both children remain reduced. They are positive, with the left child below 1 and the right child above 1.

Take any reduced positive fraction $a/b\ne1$. If $a<b$, it can only be a left child and its parent must be $a/(b-a)$. If $a>b$, it can only be a right child and its parent must be $(a-b)/b$. These parents are positive and reduced, and their numerator-plus-denominator is smaller. Repeating must terminate; the only reduced fraction with equal numerator and denominator is $1/1$. Reversing this unique sequence of parents constructs the fraction in the tree. The uniqueness of each parent and of its left/right type also proves that it cannot occur at two different nodes.

There are $2^n$ nodes at level $n$. Each level is unchanged by taking reciprocals: this holds at the root, and the reciprocals of the two children of $a/b$ are the two children of $b/a$, in opposite order. Therefore, across level $n$, $$\sum\frac{a}{a+b}=\sum\frac{b}{a+b}=2^{n-1}.$$ This formula also holds for level 0, where each sum is $1/2$.

If $S_n$ is the sum at level $n$, the right children sum to $\sum(1+a/b)=2^n+S_n$, and the left children sum to $2^{n-1}$. Hence $S_{n+1}=S_n+3\cdot2^{n-1}$. Starting from $S_0=1$ and summing the increments gives $$\boxed{S_n=1+\frac32(2^n-1)=\frac{3\cdot2^n-1}{2}.}$$

Conclusion: Every positive rational occurs once; the level-n sum is (3·2ⁿ−1)/2.

Review the idea: Greatest common divisor · Counting with recurrences · Sequences and sums