INMO Mock Paper 3: 6 Questions and Solutions

Put $c=f(1)>0$. Setting $n=1$ and cancelling $f(m)$ gives $f(m+1)=c(1+f(m))$. Therefore $f(2)=c^2+c$, $f(3)=c^3+c^2+c$, and $f(4)=c^4+c^3+c^2+c$. The equation at $m=n=2$ says $2f(4)=2f(2)+f(2)^2$. Substitution and simplification give $c^4-c^2=0$. Since c is a positive integer, $c=1$. The recurrence now reads $f(m+1)=f(m)+1$, and induction from $f(1)=1$ gives $f(m)=m$ for every positive integer. Finally, substituting this function into the original equation gives $m+n+mn=m+n+mn$. Thus it is the unique solution.

Answer / conclusion: f(n)=n for every positive integer n.

Review the idea: Solving functional equations · Recursive sequences

A parametrisation is a formula that assigns a solution to each permitted parameter. To show completeness, we must also explain why every rational solution is produced, apart from any explicitly listed exception.

If $x=1$, the equation gives $y=\pm1$. For any other rational solution, the line through it and $(1,1)$ has rational slope $t=(y-1)/(x-1)$. Substitute $y=1+t(x-1)$. Direct expansion and factorisation give $$x^2+2[1+t(x-1)]^2-3=(x-1)\bigl((1+2t^2)x+1+4t-2t^2\bigr).$$ For $x\ne1$, the second factor must be zero. Solving it for $x$, then substituting that value in $y=1+t(x-1)$, gives $$x=\frac{2t^2-4t-1}{1+2t^2},\qquad y=\frac{1-2t-2t^2}{1+2t^2}.$$ The denominator is positive for every rational t, and substitution verifies that these are rational solutions.

Every rational solution with $x\ne1$ arises from its slope t. The point $(1,1)$ is also included: take $t=-1/2$, as direct substitution confirms. The point $(1,-1)$ is not included, because setting the displayed x equal to 1 forces $t=-1/2$, which gives y=1. Thus the full answer is the displayed family for all rational t, together with the single point $(1,-1)$.

Answer / conclusion: The stated rational one-parameter family, plus (1,−1).

Review the idea: Factorisation integer solutions · Equations and quadratics

Complex-plane tool box. Identify the point $(x,y)$ with the complex number $z=x+iy$, where $i^2=-1$. Its modulus $|z|=\sqrt{x^2+y^2}$ is its distance from the origin, and $|z-w|$ is the distance between two points. The conjugate $\overline z=x-iy$ reflects the point across the horizontal axis, and $z\overline z=|z|^2$. Multiplying by $\cos\theta+i\sin\theta$ sends coordinates to $(x\cos\theta-y\sin\theta,x\sin\theta+y\cos\theta)$, so it is a rotation. Multiplication by any nonzero complex number is a rotation followed by uniform scaling. Translation, rotation and uniform scaling preserve reflection, perpendicularity and collinearity. We may therefore translate the circumcentre to the origin and scale its radius to 1.

Write the resulting vertex coordinates as unit complex numbers $a,b,c,p$; “unit” means modulus 1. Then $\overline a=1/a$, and the same holds for $b,c,p$. For ordinary coordinate arrows $(s,t),(u,v)$, their dot product is $su+tv$; it is zero exactly when nonzero arrows are perpendicular, by the cosine formula for the angle between them. The orthocentre is $h=a+b+c$: the arrow $h-a=b+c$ is perpendicular to $c-b$, since their dot product is $|c|^2-|b|^2=0$. Thus it lies on the altitude from $A$, and the other two altitudes follow in the same way.

We derive reflection in $BC$. Translate $B$ to zero and rotate/scale $BC$ to the real axis by the map $w\mapsto(w-b)/(c-b)$. Reflect there by conjugation, then undo the map. The reflected coordinate is $$w'=b+(c-b)\overline{\frac{w-b}{c-b}}.$$ Since $\overline b=1/b$ and $\overline c=1/c$, we have $$(c-b)/(\overline c-\overline b)=(c-b)/(1/c-1/b)=-bc.$$ Consequently $w'=b-bc(\overline w-\overline b)=b+c-bc\overline w$. Taking $w=p$, we obtain $x=b+c-bc/p$, so $x-h=-a-bc/p$. Conjugating gives $$\overline{x-h}=-\frac1a-\frac p{bc}=\frac p{abc}(x-h).$$ The analogous reflections in $CA$ and $AB$ give exactly the same relation for $y-h$ and $z-h$.

If nonzero complex numbers $U,V$ satisfy $\overline U=\lambda U$ and $\overline V=\lambda V$, then $\overline{U/V}=U/V$. A complex number equal to its conjugate is real, so $U/V$ is real. Thus $U$ is a real multiple of $V$; the corresponding displacement arrows lie on one line. Any zero difference already represents the point $H$.

Finally, the differences cannot all be zero. In fact $X\ne Y$: if their common value differed from $P$, the two distinct lines $BC,CA$ would both be the perpendicular bisector of the same nonzero segment $PX$, impossible. If the common value were $P$, that point would lie on both side-lines and equal $C$, which is excluded. At least one displacement is therefore nonzero, and the common conjugate ratio proves that $X,Y,Z,H$ all lie on its line.

Answer / conclusion: The three reflected points lie on a line through H.

Review the idea: Complex numbers · Triangle congruence · Circles and power of a point · Trigonometry in geometry

Graph language. Draw one point for each vertex and join adjacent vertices by line segments called edges. The degree $d(v)$ is the number of edges meeting $v$; its neighbours are the vertices joined to it. A triangle consists of three pairwise joined vertices. A complete bipartite graph divides the vertices into two groups, includes every edge between the groups, and includes none within either group.

Let e be the number of edges and $d(v)$ the degree of vertex v. For an edge uv, no vertex is adjacent to both endpoints, because that would form a triangle. Their neighbourhoods are disjoint subsets of the 20 vertices, so $d(u)+d(v)\le20$. When we sum $d(u)+d(v)$ over all edges, the number $d(v)$ occurs once for each edge meeting $v$, namely $d(v)$ times. Its total contribution is therefore $d(v)^2$, giving $\sum_v d(v)^2\le20e$. Also $\sum_v d(v)=2e$, because every edge has exactly two endpoints. Apply Cauchy–Schwarz to the twenty degrees and twenty numbers all equal to 1: $(2e)^2\le20\sum_v d(v)^2\le400e$. Thus e=0 or $e\le100$.

The complete bipartite graph with parts of size 10 has $10\cdot10=100$ edges and no triangles: among three vertices, two must lie in the same group and are not joined. The schematic below illustrates its cross-group connection pattern; each actual group has ten vertices, although only three representatives are drawn.

If equality holds, Cauchy equality forces all degrees to equal 10. Pick a vertex v and let A be its ten neighbours. No two vertices of A are adjacent. Let B be the other ten vertices, including v. Every vertex of A has all ten of its neighbours in B, so all edges between A and B are present. Every vertex of B already has degree 10 from these edges; there can be no edge within B. The graph is therefore exactly the stated complete bipartite graph.

Answer / conclusion: 100 edges; equality precisely for K₁₀,₁₀.

Review the idea: Counting · Cauchy schwarz inequality

Set $a=2+x,b=2+y,c=2+z$. The constraints become $x+y+z=0$ and $x^2+y^2+z^2=2$. Squaring the zero sum gives $xy+yz+zx=-1$, so $$abc=8+2(xy+yz+zx)+xyz=6+xyz.$$ We will bound $xyz$ using only squares and factorisation.

Because $y+z=-x$ and $y^2+z^2=2-x^2$, subtracting these equations after squaring the first gives $yz=x^2-1$. Hence $(y-z)^2=4-3x^2\ge0$, so $-2/\sqrt3\le x\le2/\sqrt3$. Put $h=1/\sqrt3$. We have $xyz=x(x^2-1)=x^3-x$. Since $3h^2=1$, direct multiplication gives $$2h^3-(x^3-x)=(2h-x)(x+h)^2,\qquad 2h^3+(x^3-x)=(x+2h)(x-h)^2.$$ Both right sides are nonnegative for $-2h\le x\le2h$. Therefore $-2h^3\le xyz\le2h^3$, or $|xyz|\le2/(3\sqrt3)$.

For the maximum, the first factorisation must vanish, so $x=2h$ or $x=-h$. If $x=2h$, then $y+z=-2h$ and $yz=h^2$, forcing $y=z=-h$. If $x=-h$, the sum and product give $y,z=2h,-h$ in either order. Thus the maximum deviations are exactly the permutations of $(2h,-h,-h)$. The second factorisation similarly gives the minimum deviations as the permutations of $(-2h,h,h)$: when $x=-2h$, the other two are h,h; when $x=h$, they are $-2h,h$.

Adding 2 back to each variable, the maximum of $abc$ is $6+2/(3\sqrt3)$, attained exactly at permutations of $(2+2/\sqrt3,2-1/\sqrt3,2-1/\sqrt3)$. The minimum is $6-2/(3\sqrt3)$, attained exactly at permutations of $(2-2/\sqrt3,2+1/\sqrt3,2+1/\sqrt3)$. All these entries are positive, since $2-2/\sqrt3>0$, and direct substitution verifies both original constraints.

Answer / conclusion: Minimum 6−2/(3√3); maximum 6+2/(3√3), with stated permutations.

Review the idea: Symmetric polynomials · Sum of squares

Let $g=\gcd(2^a-1,2^b+1)$, an odd integer. Put $u=a/d,v=b/d$, so $\gcd(u,v)=1$. Modulo g, $2^a\equiv1$ and $2^b\equiv-1$. If u is odd, the equal exponents av=bu give $1\equiv(-1)^u=-1$, so g divides 2. Since g is odd, g=1.

If u is even, v is odd. Bézout’s identity says that coprime $u,v$ admit integers $r,s$ with $ru+sv=1$. By adding a sufficiently large multiple of $u$ to the coefficient $s$, we can choose $s>0$ such that $vs=1+ku$ for an integer $k\ge0$. Since $u$ is even and $v$ is odd, this equality shows that $s$ is odd. Put $x=2^d$. We know $x^u\equiv1$ and $x^v\equiv-1\pmod g$. Using only nonnegative powers, $$x^{vs}=(x^v)^s\equiv-1\pmod g,\qquad x^{1+ku}=x(x^u)^k\equiv x\pmod g.$$ The exponents $vs$ and $1+ku$ are equal, so $x=2^d\equiv-1\pmod g$. Thus g divides $2^d+1$. Conversely, modulo $2^d+1$, we have $2^a=(2^d)^u\equiv1$ and $2^b=(2^d)^v\equiv-1$. Hence $2^d+1$ divides both original numbers, establishing equality.

Answer / conclusion: The two-case gcd formula holds.

Review the idea: Greatest common divisor · Number theory theorems