INMO Mock Paper 1: 6 Questions and Solutions

Write $a_{ij}$ for the entry in row $i$, column $j$. For a permitted choice, let $\pi(i)$ be the column chosen in row $i$. The list $\pi(1),\ldots,\pi(10)$ uses each column number once, so it is a permutation of $1,\ldots,10$.

Each permitted choice corresponds to a permutation $\pi$, with sum $S_\pi=\sum_i a_{i,\pi(i)}$. Each entry appears in exactly $9!$ of these sums: after fixing its row and column, the remaining nine columns may be assigned bijectively to the remaining nine rows in $9!$ ways. Hence $\sum_\pi S_\pi=9!\sum_{i,j}a_{ij}=0$.

Suppose all these sums were zero. For distinct rows $i,k$ and distinct columns $j,l$, compare a permutation using $(i,j),(k,l)$ with the permutation obtained by swapping just those columns. The other eight entries can be chosen bijectively from the remaining rows and columns. Subtraction gives $a_{ij}+a_{kl}=a_{il}+a_{kj}$. Fixing row 1 and column 1 yields $a_{ij}=a_{i1}+a_{1j}-a_{11}$, also valid if $i=1$ or $j=1$. Summing over the ten values of $j$ gives $0=10a_{i1}+0-10a_{11}$, since row $i$ and row 1 both sum to zero. Thus $a_{i1}=a_{11}$. The first-column sum is then $10a_{11}=0$, so $a_{11}=0$. The entry relation reduces to $a_{ij}=a_{1j}$. Column $j$ therefore has sum $10a_{1j}=0$, giving $a_{1j}=0$ and hence every entry zero, contrary to the hypothesis.

Thus not all $S_\pi$ are zero. Their total is zero, so at least one is positive and at least one negative.

Answer / conclusion: There are permitted sums of both signs.

Review the idea: Permutations and arrangements · Proof methods

Tool: order modulo a prime. If a prime $p$ does not divide an integer $a$, the order of $a$ modulo $p$ is the smallest positive integer $d$ for which $a^d\equiv1\pmod p$. Such a $d$ exists because Fermat gives $a^{p-1}\equiv1$. If $a^N\equiv1$, divide the exponent as $N=kd+r$, $0\le r<d$. Then $a^N\equiv(a^d)^ka^r\equiv a^r$, so $a^r\equiv1$. Minimality forces $r=0$. Thus $d$ divides every exponent giving residue 1, including $p-1$.

The integers 1 and 3 work. Suppose $n>1$ satisfies $n^2\mid2^n+1$. It is odd: an even $n$ would make $n^2$ even, whereas $2^n+1$ is odd. Let $p$ be the least prime divisor of $n$, and let $d$ be the order of 2 modulo $p$. Since $2^n\equiv-1\pmod p$, we have $d\mid2n$, but $d\nmid n$. Also $d\mid p-1$. Every prime divisor of $n$ is at least $p$, whereas every prime divisor of $p-1$ is smaller than $p$. Hence $\gcd(n,p-1)=1$. Because $n$ is odd and $p-1$ is even, $\gcd(2n,p-1)=2$, so $d\mid2$. We cannot have $d=1$, because $2^n$ is $-1$, not 1, modulo the odd prime $p$. Thus $d=2$, giving $p\mid2^2-1=3$, so $p=3$.

Write $n=3^s m$, where $m$ is odd and not divisible by 3. Here “exactly $s$ factors of 3” means divisibility by $3^s$ but not $3^{s+1}$. Since $m\equiv1$ or 5 modulo 6, the period-six powers of 2 modulo 9 show that $2^m+1$ has exactly one factor of 3. If $A\equiv-1\pmod3$, write $A=-1+3t$. Then $A^2-A+1=3(1-3t+3t^2)$, which has exactly one factor of 3. Applying $A^3+1=(A+1)(A^2-A+1)$ successively $s$ times proves that $2^n+1$ has exactly $s+1$ factors of 3. Divisibility by $n^2$ requires $2s\le s+1$; since $3\mid n$, we obtain $s=1$.

If $n$ has another prime divisor, let $q$ be the smallest one other than 3, and let $e$ be the order of 2 modulo $q$. Again $e\mid2n$ and $e\mid q-1$, while $e\nmid n$. Every prime divisor of $e$ is smaller than $q$, so among prime divisors of $2n$ only 2 and 3 are possible. Moreover $e\mid2n$, so it has at most one factor 2 and one factor 3. It cannot be odd: any odd divisor of $2n$ divides $n$. Therefore $e=2$ or 6. If $e=2$, then $2\equiv-1\pmod q$, so $2^3\equiv-1$. If $e=6$, put $z=2^3$. We have $(z-1)(z+1)\equiv0\pmod q$, and $z\not\equiv1$, since that would give order at most 3. A prime dividing a product divides one factor, so $z\equiv-1$. In either case $q\mid2^3+1=9$, a contradiction. Thus $n=3$. Including the earlier case $n=1$, the complete answer is $1,3$.

Answer / conclusion: n=1 or 3.

Review the idea: Number theory theorems · Unique prime factorisation

Coordinate tool. Put $A=(0,0)$, $B=(b,0)$, $C=(u,v)$, where $b>0$ and $v\ne0$. A circle through the origin has an equation $x^2+y^2=\alpha x+\beta y$. Indeed, if its centre is $(h,k)$, expand $(x-h)^2+(y-k)^2=h^2+k^2$; then $\alpha=2h$, $\beta=2k$. We will determine these two coefficients from two further points on each circle.

Let $s=u^2+v^2=AC^2>0$. The side ratios give $E=(tu,tv)$, $F=(tb,0)$. Substituting $B,E$ in the first circle equation and $C,F$ in the second gives, respectively, $$x^2+y^2=bx+\frac{ts-bu}{v}y,\qquad x^2+y^2=tbx+\frac{s-tbu}{v}y.$$ Subtract the equations and divide by $1-t\ne0$. Every common point lies on the line $$L:\quad bvx=(s+bu)y.$$

We also verify that the second common point is distinct from $A$. Points on $L$ can be written $(x,y)=\lambda(s+bu,bv)$. Substituting in the first circle gives $$\lambda^2\bigl((s+bu)^2+b^2v^2\bigr)=\lambda b(1+t)s.$$ The quadratic coefficient is positive, and $b(1+t)s>0$. Besides $\lambda=0$, there is therefore the nonzero root $\lambda=b(1+t)s/((s+bu)^2+b^2v^2)$. This point also satisfies the second circle equation, because it lies on their difference line. Thus the line $AP$ is exactly $L$.

A point on $BC$ has coordinates $D=(b+\rho(u-b),\rho v)$. When $0<\rho<1$, this means moving the fraction $\rho=BD/BC$ of the way from $B$ to $C$. Substitution in $L$ gives $b^2=\rho(s+b^2)$, so $\rho=b^2/(s+b^2)$, which is strictly between 0 and 1. Consequently $$\frac{BD}{DC}=\frac{\rho}{1-\rho}=\frac{b^2}{s}=\frac{AB^2}{AC^2}.$$ The equation of $L$, and hence the line $AP$, contains no $t$. This proves the requested independence.

Answer / conclusion: The stated squared-side ratio, independent of t.

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

Put $s=a+b+c$ and $D=(a-b)^2+(b-c)^2+(c-a)^2$. Cauchy–Schwarz in the form $\sum U_i^2/V_i\ge(\sum U_i)^2/\sum V_i$ gives a lower bound $$\frac{D^2}{(a+b)^2+(b+c)^2+(c+a)^2}.$$ The denominator equals $s^2+a^2+b^2+c^2<2s^2$, since $ab+bc+ca>0$. Thus $K=1/2$ works. If $D>0$, the final comparison is strict; if $D=0$, all variables are equal and both sides are zero.

To show that a larger constant fails, use $(a,b,c)=(1,t,t)$, with $t>0,t\ne1$. The ratio of the left side to $D^2/s^2$ is $(1+2t)^2/[2(1+t)^2]$, which tends to $1/2$ as $t\to0^+$. Any larger $K$ exceeds this ratio for sufficiently small positive $t$. Therefore the best constant is $1/2$, with equality precisely at $a=b=c$.

Answer / conclusion: Best K=1/2; equality exactly at a=b=c.

Review the idea: Cauchy schwarz inequality · Inequality rules and signs

The constant solutions are 0 and 1. Let P be a nonconstant solution of degree n with leading coefficient c. Comparing the coefficients of the highest power $x^{2n}$ gives $c^2=c$, so c=1: P is monic. Also $P(1)\ne0$. Otherwise, a positive root r would produce the larger root $r^2+r+1$ by the given equation; starting at r=1 would give infinitely many distinct roots, impossible for a nonzero polynomial. At x=0 we therefore get $P(0)P(1)=P(1)$, hence $P(0)=1$.

The input $x^2+x+1$ is unchanged when x is replaced by $-x-1$. Put $Q(x)=(-1)^nP(-x)$, which is also monic of degree n. The two equations imply $P(x)P(x+1)=Q(x)Q(x+1)$. Replacing $x$ by $x+1$ also gives $P(x+1)P(x+2)=Q(x+1)Q(x+2)$. Multiply the first equation by $Q(x+2)$ and the second by $Q(x)$. Their right sides are identical. Subtraction therefore gives $$P(x+1)\bigl(P(x)Q(x+2)-Q(x)P(x+2)\bigr)=0.$$ This is a polynomial identity. A product of two nonzero polynomials is nonzero, because its leading coefficient is the product of their nonzero leading coefficients. Since $P(x+1)$ is nonzero, the bracket must vanish: $$P(x)Q(x+2)=Q(x)P(x+2).$$

We now show Q=P. If $R=Q-P$ were nonzero, its degree d would be less than n, since their leading terms cancel. Write its leading coefficient as k. The last identity becomes $P(x)R(x+2)=R(x)P(x+2)$. Write $P(x)=x^n+ax^{n-1}+\text{lower terms}$ and, when $d\ge1$, $R(x)=kx^d+bx^{d-1}+\text{lower terms}$. If $d=0$, simply write $R(x)=k$ and take $b=0$ in the calculation below. The binomial expansion starts $(x+2)^j=x^j+2jx^{j-1}+\text{lower terms}$. Thus the coefficient of $x^{n+d-1}$ in $P(x)R(x+2)$ is $ak+2dk+b$, while that in $R(x)P(x+2)$ is $ak+2nk+b$. Equality would give $2k(d-n)=0$, impossible since k is nonzero and d<n. Therefore Q=P.

Evaluating $P(-x)=(-1)^nP(x)$ at zero, where P(0)=1, shows n is even; write n=2m. The polynomial $H(x)=(x^2+1)^m$ satisfies the original identity because $$(x^2+1)((x+1)^2+1)=(x^2+x+1)^2+1.$$ Suppose $R=P-H$ were nonzero of degree d<n and leading coefficient k. Subtracting the equations for P and H gives $$R(x)H(x+1)+H(x)R(x+1)+R(x)R(x+1)=R(x^2+x+1).$$ The left side has degree n+d and leading coefficient 2k; the last product has smaller degree 2d. The right side has degree 2d. Since n+d>2d, this is impossible. Hence P=H. Together with the constants, the answer is P=0 or $P(x)=(x^2+1)^m$ for any integer m≥0.

Answer / conclusion: $P=0$ or $P(x)=(x^2+1)^m$, where $m$ is a nonnegative integer.

Review the idea: Polynomial functions · Polynomial roots and multiplicity

After an arbitrary cut, let $S_0=0$ and let $S_j$ be the sum of the first $j$ cards. Then $S_{15}=3$. A start immediately after position $i$ has partial sum $S_j-S_i$ when it ends at a later position $j>i$. If it passes position 15 and ends at $j\le i$, its partial sum is $(S_{15}-S_i)+S_j=3+S_j-S_i$. Hence the start is good exactly when all its later heights $S_j$ and wrapped heights $S_j+3$ exceed $S_i$. Put $m=\min(S_0,\ldots,S_{14})$, so $m\le0$. Since steps are $\pm1$ and the path finishes at 3, each level $m,m+1,m+2$ occurs before the final step. For each level $r$, let $i$ be its last occurrence before position 15, meaning the largest index in $0,\ldots,14$ at which $S_i=r$. Every later prefix through $S_{15}$ is greater than $r$; otherwise the unit-step path would revisit $r$ before reaching 3. On wrapping around, the corresponding prefixes are $S_j+3\ge m+3>r$. Thus starting immediately after $i$ is good.

Conversely, suppose the start after $i$ is good, and set $r=S_i$. It must be the last occurrence of level $r$, or a later partial sum would be zero. Also $r<m+3$: if an occurrence of the minimum is after $i$, it immediately violates positivity; if all minimum occurrences are before or at $i$, their wrapped level $m+3$ would violate positivity when $r\ge m+3$. Since $r\ge m$, the only choices are $m,m+1,m+2$. Their last occurrences are distinct, so exactly three starts are good.

Answer / conclusion: Exactly three good starting positions.

Review the idea: Counting with bijections · Pigeonhole principle · Sequences and sums