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

The terms are positive and strictly increasing from $u_1=1,u_2=3$: if $u_{j+1}>u_j\ge0$, then $u_{j+2}=2u_{j+1}+(u_{j+1}-u_j)>u_{j+1}$. Also $\gcd(u_{j+1},u_j)=\gcd(u_j,u_{j-1})$ by the recurrence. Repeatedly reducing gives $\gcd(u_{j+1},u_j)=\gcd(1,0)=1$.

For fixed $m\ge1$, we claim $$\begin{gathered}u_{m+n}=u_m u_{n+1}-u_{m-1}u_n\\(n\ge0).\end{gathered}$$ For $n=0$ it reads $u_m=u_m$. For $n=1$ it is the recurrence $u_{m+1}=3u_m-u_{m-1}$. Both sides, as sequences in $n$, satisfy the same recurrence; knowing two successive values proves all later values by induction.

Reducing this identity modulo $u_m$, and using $\gcd(u_m,u_{m-1})=1$, gives $$\gcd(u_m,u_{m+n})=\gcd(u_m,u_n).$$ The cancellation is legitimate: a common divisor of $u_m$ and $u_{m-1}u_n$ divides $u_n$, by Bézout’s identity for $u_m,u_{m-1}$.

Consequently, subtracting the smaller index from the larger leaves the gcd of the terms unchanged. Repeating these Euclidean-algorithm steps ends at indices $d,0$, where $d=\gcd(m,n)$. Thus $\gcd(u_m,u_n)=\gcd(u_d,u_0)=u_d$.

Now $u_m\mid u_n$ is equivalent to $u_d=u_m$. Strict increase on the positive indices makes this equivalent to $d=m$, or $m\mid n$. This also covers $m=1$, since $u_1=1$.

Conclusion: The gcd follows the gcd of the indices; uₘ divides uₙ exactly when m divides n.

Review the idea: Second order recurrences · Greatest common divisor · Mathematical induction the first principle

Difference bridge. If a polynomial has degree $j$ and leading coefficient $a$, then $P(x+1)-P(x)$ has degree $j-1$ and leading coefficient $ja$: the degree-$j$ terms cancel, and the next term in $(x+1)^j-x^j$ is $jx^{j-1}$.

If $D$ divides every integer value of $P$, it also divides every integer value of $\Delta P$, because each is a difference of two multiples of $D$. Apply this observation successively $d$ times. Since the original leading coefficient is 1, the constant polynomial $\Delta^dP$ is $d!$. Hence $D\mid d!$.

For sharpness use $$Q(x)=x(x-1)\cdots(x-d+1).$$ This is monic of degree $d$. If an integer $k\ge d$, then $Q(k)=d!\binom{k}{d}$, so it is divisible by $d!$. For $0\le k<d$, one factor is zero. If $k=-t<0$, then $$Q(k)=(-1)^d t(t+1)\cdots(t+d-1)=(-1)^d d!\binom{t+d-1}{d},$$ again a multiple of $d!$.

Thus $d!$ divides every integer value of $Q$. Conversely $Q(d)=d!$, so no larger common divisor is possible. Its values have greatest common divisor exactly $d!$.

Conclusion: Every common divisor divides d!, and the falling-factorial polynomial attains d!.

Review the idea: Polynomial functions · Binomial expansions and generating functions · Factorials

Write $x=FA,y=FB,z=FC$, all positive. Choose perpendicular coordinates with $F=(0,0)$, $A=(x,0)$, $B=(-y/2,\sqrt3y/2)$, and $C=(-z/2,-\sqrt3z/2)$. The angle assumptions justify these coordinates, after reflecting the picture if necessary.

Projection bridge. If $r^2+s^2=1$, then $ru+sv\le\sqrt{u^2+v^2}$, because $(u^2+v^2)-(ru+sv)^2=(su-rv)^2\ge0$. This remains true when the projection on the left is negative.

For $Q=(u,v)$, project the displacement from $Q$ to each vertex along the corresponding ray from $F$. We obtain $$\begin{gathered}QA\ge x-u,\\ QB\ge y+\frac u2-\frac{\sqrt3v}{2},\\ QC\ge z+\frac u2+\frac{\sqrt3v}{2}.\end{gathered}$$ Adding gives $QA+QB+QC\ge x+y+z$. For equality in the first bound, $v=0$. With $v=0$, equality in the second projection bound forces $u=0$, since its perpendicular component is $\sqrt3u/2$. Thus equality is possible only at $Q=F$, where it does hold. This proves strict minimality elsewhere.

Using the coordinates already chosen, $$a^2=BC^2=\frac{(y-z)^2}{4}+\frac{3(y+z)^2}{4}=y^2+yz+z^2.$$ The other two distance expansions similarly give $b^2=x^2+z^2+xz$ and $c^2=x^2+y^2+xy$. Triangle AFB has base FA=x and altitude $\sqrt3y/2$, so its area is $\sqrt3xy/4$. Rotating the same base-height calculation for the other two triangles and adding gives $\Delta=\sqrt3(xy+yz+zx)/4$. Hence $$a^2+b^2+c^2+4\sqrt3\Delta=2(x^2+y^2+z^2)+4(xy+yz+zx)=2(x+y+z)^2.$$ This is the second conclusion.

Conclusion: F uniquely minimises the distance sum, whose square is (a²+b²+c²+4√3Δ)/2.

Review the idea: Trigonometry in geometry · Triangle area ratios · Cauchy schwarz inequality

First the graph is connected. Indeed, a connected component containing a vertex must contain that vertex and all its at least $n/2$ neighbours, so it has more than $n/2$ vertices. There cannot be two such components.

Choose a longest path $v_1,v_2,\ldots,v_k$. Neither endpoint has a neighbour outside the path, since that neighbour would extend it. Within the index set $\{1,\ldots,k-1\}$, define $$\begin{gathered}I=\{i:v_1v_{i+1}\text{ is an edge}\},\\ J=\{i:v_iv_k\text{ is an edge}\}.\end{gathered}$$ These sets have sizes equal to the degrees of $v_1,v_k$, respectively. Thus $|I|+|J|\ge n\ge k$. Since there are only $k-1$ indices available, $I$ and $J$ overlap.

For an index $i$ in the overlap, follow $$v_1,v_2,\ldots,v_i,v_k,v_{k-1},\ldots,v_{i+1},v_1.$$ The two joining edges exist by the choice of $i$; every other edge is on the original path. This is a cycle containing all $k$ path vertices once. The notation also covers $i=1$ or $i=k-1$, where one of the intervening lists is empty.

If $k<n$, connectedness supplies an edge from a vertex outside this cycle to one on it: take the first edge entering the cycle along a path from any outside vertex. Start at the outside endpoint, cross that edge, and go around the cycle without closing it. This is a path with $k+1$ distinct vertices, contradicting maximality. Therefore $k=n$, and the cycle visits every vertex.

Conclusion: The graph has a cycle through all n vertices.

Review the idea: Pigeonhole principle · Proof methods

The identity $2\cos(2\theta)=(2\cos\theta)^2-2$ gives, by induction, $$P_n(2\cos\theta)=2\cos(2^n\theta).$$ Thus for $j=1,\ldots,2^n$, the numbers $$x_j=2\cos\left(\frac{(2j-1)\pi}{2^{n+1}}\right)$$ are roots.

Why this list is complete. The angles in the displayed formula are distinct and lie in $(0,\pi)$, where cosine is strictly decreasing. So the $2^n$ proposed roots are distinct. Squaring in the recurrence doubles the degree, and its leading coefficient remains 1; hence $P_n$ has degree $2^n$. A nonzero polynomial cannot have more distinct roots than its degree, so these are all roots and every one has multiplicity 1.

Put $d=2^n$. For $1\le j\le d/2$, the angle for $x_{j+d/2}$ is the angle for $x_j$ plus $\pi/2$. The identity $\cos(\theta+\pi/2)=-\sin\theta$ therefore gives $$x_j^2+x_{j+d/2}^2=4\cos^2\theta+4\sin^2\theta=4.$$ There are $d/2$ such pairs, so the sum of all squared roots is $2d=2^{n+1}$.

Conclusion: Roots: 2cos((2j−1)π/2ⁿ⁺¹), 1≤j≤2ⁿ; all simple, with square-sum 2ⁿ⁺¹.

Review the idea: Trigonometry foundations · Polynomial roots and multiplicity · Recursive sequences

The $k$ blocks $\{1,2,3\},\{4,5,6\},\ldots,\{3k-2,3k-1,3k\}$ each contribute at most two selected integers. Hence the size is at most $2k$. Omitting $3,6,\ldots,3k$ attains $2k$, so this is the maximum.

Now consider a maximum subset. In its 0–1 record, with 1 for selected and 0 for omitted, there are $2k$ ones and $k$ zeros. Read the record as $k+1$ runs of ones separated by the zeros, allowing an empty run at either end or between consecutive zeros. Let their lengths be $r_0,\ldots,r_k$. The condition is exactly $0\le r_i\le2$, and their sum is $2k$.

Set $d_i=2-r_i$. Then every $d_i$ is a nonnegative integer, and $d_0+\cdots+d_k=2$. Either one of the $k+1$ entries is 2, or two distinct entries are 1. The count is therefore $$(k+1)+\binom{k+1}{2}=\frac{(k+1)(k+2)}2.$$

Conversely, every such choice of deficiencies yields run lengths between 0 and 2 and hence exactly one permitted record of length $3k$. Thus no subset is missed or counted twice.

Conclusion: Maximum size 2k; exactly (k+1)(k+2)/2 maximum subsets.

Review the idea: Counting integer solutions · Combinations and binomial coefficients