MO Bundesrunde Klasse 9 Mock Paper 1: Questions, Hints and Solutions

Let $2^t$ be the greatest power of 2 dividing all three variables, and write $x=2^ta,y=2^tb,z=2^tc$. Here t is nonnegative, a,b,c are positive integers, and at least one of them is odd. Cancelling $2^{2t}$ gives $$a^2+b^2+c^2=2^{t+1}abc.$$ A square is 0 or 1 modulo 4 according as its base is even or odd. If t≥1, the right side is divisible by 4, whereas the left side is congruent to the number of odd members of a,b,c. That number is 1,2 or 3, a contradiction. If t=0 and not all a,b,c are odd, their product is even, so the same contradiction applies. If t=0 and all three are odd, the two sides are 3 and 2 modulo 4, respectively. All possibilities fail.

Conclusion: No positive integer triple exists.

Review the idea: Parity · Remainders

The expression is symmetric, so rename the variables so that a≥b≥c≥0. Expanding the difference of the two sides gives $$a(a-b)(a-c)+b(b-c)(b-a)+c(c-a)(c-b).$$ Combine the first two terms: $$(a-b)\bigl(a(a-c)-b(b-c)\bigr)=(a-b)^2(a+b-c).$$ The remaining term is $c(a-c)(b-c)$. Both are nonnegative, proving the inequality. If a+b−c=0 under the ordering, all three numbers are zero. Otherwise equality in the first term requires a=b. The second then becomes $c(a-c)^2$, which vanishes exactly when c=0 or c=a. Restoring arbitrary order, equality holds when all three numbers are equal, or when one is zero and the other two are equal. Direct substitution confirms each case.

Conclusion: Equality: all three equal, or a permutation of (t,t,0) with t≥0.

Review the idea: Sum of squares · Inequality rules and signs

Use directed angles between lines modulo 180 degrees, so reversing a ray does not change the angle. The feet give $\angle PXC=\angle PYC=90^\circ$, hence P,C,X,Y are concyclic. Similarly P,A,Y,Z are concyclic. Equal directed angles subtending a chord now give $$\begin{gathered}\angle XYP\equiv\angle XCP,\\ \angle PYZ\equiv\angle PAZ\pmod{180^\circ}.\end{gathered}$$ Therefore the line angle from YX to YZ is the sum of the line angles from CB to CP and from AP to AB. Because A,B,C,P lie on the original circle, $\angle BCP\equiv\angle BAP$. The two terms consequently add to $\angle BAP+\angle PAB\equiv0$. Thus lines YX and YZ are the same line, proving collinearity. The distinctness assumption ensures every circle and angle used here is defined; no position inside a side segment was assumed.

Conclusion: The three perpendicular feet are collinear.

Review the idea: Cyclic and tangential quadrilaterals · Angles

For every subset S of positions, count the permutations fixing all positions in S with sign $(-1)^{|S|}$. If S has k elements, there are $(n-k)!$ such permutations and $\binom nk$ choices of S. Consider how often one particular permutation is counted. If it has r fixed positions, the eligible S are exactly the subsets of those r positions, and its signed contribution is $\sum_{k=0}^r(-1)^k\binom rk=(1-1)^r$. This is 1 when r=0, including the empty subset, and 0 otherwise. The signed count therefore counts exactly the required permutations. It equals $$\sum_{k=0}^n(-1)^k\binom nk(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.$$ For exactly three fixed positions among eight, choose those positions in $\binom83=56$ ways and derange the remaining five labels. The formula gives $D_5=120-120+60-20+5-1=44$, so the answer is $56\cdot44=2464$.

Conclusion: $D_n=n!\sum_{k=0}^n(-1)^k/k!$; the requested count is 2464.

Review the idea: Inclusion exclusion · Permutations and arrangements

We first justify the root bound modulo a prime. If a polynomial vanishes at r, division by T−r writes it as $(T-r)Q(T)$. At any other root s, the nonzero residue s−r is invertible, so Q(s)=0 modulo p. Induction on degree proves that a nonzero degree-m polynomial has at most m roots. Since m<p−1, some c among 1,…,p−1 is not a root of $T^m-1$. Let S be the required sum modulo p. Multiplication by c permutes the nonzero residues: cancellation is valid because p is prime and c is nonzero modulo p. Hence $$S\equiv\sum_{k=1}^{p-1}(ck)^m\equiv c^mS\pmod p.$$ Since $c^m-1$ is nonzero modulo p, it has an inverse, and cancellation gives S≡0. The assumptions exclude p=2 automatically, so there is no omitted exponent in that case.

Conclusion: Every indicated power sum is divisible by p.

Review the idea: Remainders · Polynomial roots and multiplicity

The zero polynomial works. For a nonzero polynomial write $P(x)=x^rQ(x)$, where r≥0 is an integer and Q(0)≠0. Cancelling the polynomial factor $x^{2r}$ gives $Q(x^2)=Q(x)^2$. Substituting zero shows Q(0)=Q(0)², so Q(0)=1. Suppose Q is not constant, and let k≥1 be its smallest positive exponent with nonzero coefficient a. In Q(x)² the coefficient of $x^k$ is 2a: no product of two positive lower exponents contributes because their coefficients are zero. In Q($x^{2}$), that coefficient is zero. Indeed it is automatically zero if k is odd, while if k is even it comes from the coefficient of $x^{k/2}$ in Q, which is zero by minimality. This contradiction gives Q=1. Thus all solutions are P=0 and $P(x)=x^r$ for integers r≥0; substitution verifies them, with r=0 giving P=1.

Conclusion: Exactly P=0 and $P(x)=x^r$, where r is a nonnegative integer.

Review the idea: Polynomial functions