INMO Mock Paper 4: 6 Questions and Solutions

At zero, $P(0)$ is 0 or 1. Constant polynomials cannot satisfy the equation. If $P(0)=0$, let $kx^m$ be its lowest nonzero term. For $m>1$, the term $-2x^2$ on the right cannot be matched, so m=1. Comparing coefficients of $x^2$ gives $k=k^2-2$, hence k=2 or $-1$. Write $P=kx+Q$. If Q is nonzero with lowest degree $r\ge2$, cancellation of the known identity for kx gives $Q(x^2)=2kxQ(x)+Q(x)^2$. The lowest degree is $2r$ on the left but $r+1<2r$ on the right, impossible. Thus $P=2x$ or $-x$.

If $P(0)=1$, its lowest nonconstant degree cannot be 1, since the right side would have a nonzero linear term. It cannot exceed 2, since $-2x^2$ would then be unmatched. Thus the lowest term is $kx^2$, and comparison at degree 2 gives $2k-2=0$, so k=1. Write $P=x^2+1+Q$, with Q either zero or of lowest degree $r>2$. The polynomial $x^2+1$ already satisfies the identity, so $Q(x^2)=2(x^2+1)Q+Q^2$. The lowest degrees would be $2r$ and r, a contradiction. Hence $P=x^2+1$. Substitution verifies all three candidates.

Answer / conclusion: P(x)=2x, P(x)=−x, or P(x)=x²+1.

Review the idea: Polynomial functions · Polynomial roots and multiplicity

Counting copies of a prime. In a factorial, each multiple of $p$ contributes at least one factor $p$, each multiple of $p^2$ contributes another, and so on. For example, the number of factors 2 in $15!$ is $\lfloor15/2\rfloor+\lfloor15/4\rfloor+\lfloor15/8\rfloor=7+3+1=11$. To prove $n^2\mid(n-1)!$, we must show that for every prime power $p^a$ exactly dividing $n$, the factorial contains at least $2a$ factors of $p$.

We will use simple growing lower bounds $B_a=Cp^{a-1}-1$. For $p\ge2$, $B_{a+1}=pB_a+(p-1)\ge2B_a+1$. Once $B_a\ge2a$ holds at a base case $a\ge1$, the next value is at least $4a+1\ge2(a+1)$. Thus a single base check proves the bound for all higher exponents. The five base checks needed below are $$2\cdot3^{2-1}-1=5\ge4,\quad3\cdot2^{2-1}-1=5\ge4,\quad5^{2-1}-1=4,\quad3^{3-1}-1=8\ge6,\quad2^{5-1}-1=15\ge10.$$ Increasing $p$ only increases these lower bounds.

Every prime n fails, because $(n-1)!$ contains no factor n. If $n=2p$ for a prime p, then for odd p the factorial contains just one multiple of p, whereas $n^2$ needs two; n=4 also fails. Directly, n=8 fails because $7!$ has only four factors of 2, rather than six, and n=9 fails because $8!$ has only two factors of 3, rather than four.

We prove that there are no other failures. Let $p^a$ exactly divide a remaining composite n. If a=1, write $n=pm$. Since n is neither prime nor twice a prime, $m\ge3$, so among $1,\ldots,n-1$ there are $m-1\ge2$ multiples of p. If $a\ge2$ and $n=mp^a$ with $m>1$, then for odd p the number of multiples of p is $mp^{a-1}-1\ge2p^{a-1}-1\ge2a$. The last inequality holds at a=2,p=3 and is preserved as a increases. For p=2, m is odd and at least 3, giving $m2^{a-1}-1\ge3\cdot2^{a-1}-1\ge2a$.

It remains to consider $n=p^a$, $a\ge2$. For $p\ge5$, the $p^{a-1}-1$ multiples of p already number at least $2a$, starting at a=2 and increasing thereafter. For p=3, a=2 is the excluded 9, while a≥3 gives $3^{a-1}-1\ge2a$. For p=2, a=2,3 are the excluded 4,8. At a=4, $15!$ has $7+3+1=11\ge8$ factors of 2. For a≥5, $2^{a-1}-1\ge2a$. Thus in every remaining case the factorial contains at least $2a$ factors of each prime p dividing n. Therefore it is divisible by $n^2$.

The complete list of failures is every prime, twice every prime, and the two additional integers 8 and 9. The integer 4 is already included as twice the prime 2.

Answer / conclusion: Exactly primes, twice a prime, 8 and 9.

Review the idea: Factorials · Unique prime factorisation

Complex-distance tool. The complex number $z=x+iy$ represents the point $(x,y)$, and $|z|=\sqrt{x^2+y^2}$. Thus $|a-b|$ is the distance $AB$. Also $|zw|=|z||w|$: squaring both sides reduces this to $(zw)\overline{(zw)}=(z\overline z)(w\overline w)$. Finally $|z+w|\le|z|+|w|$ is the ordinary triangle inequality for two displacement arrows placed successively; their combined arrow is $z+w$.

Represent the four vertices by complex numbers $a,b,c,d$. Direct expansion gives $$(a-c)(b-d)=(a-b)(c-d)+(a-d)(b-c).$$ Taking moduli, using the product rule and then the triangle inequality, gives $$AC\cdot BD\le AB\cdot CD+AD\cdot BC=3\cdot5+6\cdot4=39.$$

To prove attainability without assuming an equality case of this inequality, put $A=(0,0)$, $C=(L,0)$, where $L=\sqrt{1729}/7$, so $L^2=247/7$. The following explicit points give the required side lengths: $$B=\left(\frac{99}{\sqrt{1729}},\frac{24\sqrt{10}}{\sqrt{1729}}\right),\qquad D=\left(\frac{162}{\sqrt{1729}},-\frac{60\sqrt{10}}{\sqrt{1729}}\right).$$ For instance, $AB^2=(99^2+24^2\cdot10)/1729=9$; the same distance calculation gives $BC^2=16,CD^2=25,DA^2=36$. Both horizontal coordinates lie strictly between 0 and $L$, and $B,D$ are on opposite sides of $AC$. Therefore the segment $BD$ crosses the interior of $AC$, with the crossing also inside $BD$; the quadrilateral in the order $A,B,C,D$ is convex.

Its other diagonal satisfies $$BD^2=\frac{(162-99)^2+(60\sqrt{10}+24\sqrt{10})^2}{1729}=\frac{63^2+(84\sqrt{10})^2}{1729}=\frac{74529}{1729}=\frac{819}{19}.$$ Thus $(AC\cdot BD)^2=(247/7)(819/19)=1521=39^2$. The diagonal lengths are positive, so their product is 39. This attains the upper bound and proves the maximum.

Answer / conclusion: 39.

Review the idea: Complex numbers · Cyclic and tangential quadrilaterals · Triangle inequalities

Each of the $10!$ permutations supplies the nested chain consisting of its initial segments of sizes 0 through 10. The hypothesis permits at most one member of $\mathcal F$ on any such chain. A fixed subset S of size k is an initial segment in $k!(10-k)!$ permutations: order S first and its complement afterward. Counting pairs of a permutation and a member of $\mathcal F$ on its chain gives $$\sum_{S\in\mathcal F}|S|!(10-|S|)!\le10!,\quad\text{or}\quad\sum_{S\in\mathcal F}\frac1{\binom{10}{|S|}}\le1.$$

The binomial coefficient $\binom{10}{k}$ has its unique maximum $\binom{10}{5}=252$, as follows by comparing successive ratios $(10-k)/(k+1)$. Every summand is therefore at least $1/252$, so $|\mathcal F|\le252$. All 5-element subsets attain the bound. If a family has 252 members, every summand must equal $1/252$, so every member has size 5. There are only 252 such subsets, forcing the entire middle layer. This is the unique maximum family.

Answer / conclusion: 252; exactly the family of all 5-element subsets.

Review the idea: Permutations and arrangements · Combinations and binomial coefficients

Putting $x=0$ gives $f(0)^2=0$, so $f(0)=0$. With $y=0$, $f(x^2)=f(x)^2\ge0$. Every nonnegative t is a square, so the equation gives $f(t+y)=f(t)+f(y)$ for every $t\ge0$ and real y. Taking $y=-t$ gives $f(-t)=-f(t)$; for $t<0$, put $u=-t>0$. The known rule gives $f(y)=f(u+(y-u))=f(u)+f(y-u)$. Rearranging and using $f(-u)=-f(u)$ yields $f(y+t)=f(y)+f(t)$, as required for a negative first summand. Thus f is additive on all real numbers.

If $u\ge v$, then $f(u)-f(v)=f(u-v)\ge0$, so f is nondecreasing. Also $f(1)=f(1)^2$, hence $f(1)=0$ or 1. Additivity implies $f(q)=qf(1)$ for every rational q, including negative rationals, by multiplying by a positive denominator. Rational numbers exist between any two distinct real numbers. If $f(1)=0$, choose rationals $r<x<s$; monotonicity gives $0=f(r)\le f(x)\le f(s)=0$, hence $f(x)=0$. If $f(1)=1$ and $f(x)>x$, choose a rational $q$ strictly between $x$ and $f(x)$. Monotonicity would give $f(x)\le f(q)=q$, contradicting $q<f(x)$. If $f(x)<x$, choose a rational $q$ strictly between $f(x)$ and $x$; then $q=f(q)\le f(x)$, again a contradiction. Thus $f(x)=x$. This uses no continuity assumption. Both functions satisfy the original equation by direct substitution.

Answer / conclusion: f(x)=0 for all x, or f(x)=x for all x.

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

Write $n=2^a m$, where $a\ge1$ and m is odd. Every divisor is uniquely $2^j d$, with $0\le j\le a$ and d dividing m. Hence $(2^{a+1}-1)\sigma(m)=2^{a+1}m$. The odd factor $2^{a+1}-1$ is coprime to $2^{a+1}$, so it divides m. Write $m=(2^{a+1}-1)t$. The equation becomes $\sigma(m)=2^{a+1}t=m+t$.

If $t>1$, the three distinct positive divisors $1,t,m$ already have sum $1+t+m>t+m$, a contradiction. Thus t=1 and $\sigma(m)=m+1$, forcing m to be prime: otherwise it would have a divisor strictly between 1 and m. Put $p=a+1$. Then $m=2^p-1$ is prime. If p were composite, say $p=uv$ with $u,v>1$, then $2^u-1$ would be a proper nontrivial divisor of $2^p-1$, impossible. Thus p is prime.

Conversely, whenever $2^p-1$ is prime, the integer $n=2^{p-1}(2^p-1)$ has divisor sum $(2^p-1)(1+2^p-1)=2^p(2^p-1)=2n$. These, and only these, are the even solutions.

Answer / conclusion: $n=2^{p-1}(2^p-1)$, where $2^p-1$ is prime (and therefore $p$ is prime).

Review the idea: Counting and summing divisors · Unique prime factorisation