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

If n is prime, none of the factors 1,…,n−1 is divisible by n, so their product is not divisible by n. Let n be composite. If $n=ab$ with $2\le a\lt b\lt n$, both distinct factors occur in (n−1)!, so n divides it. It remains to consider composites with no such unequal factorisation. Such a number must be a square of a prime: if its least prime divisor is p and n/p≠p, those two factors are unequal; if they are equal, n=$p^{2}$. For p≥3, the distinct proper factors p and 2p occur in ($p^{2}$−1)!, because 2p<$p^{2}$. Their product is 2$p^{2}$, divisible by n. Finally n=4 fails because 3!=6 is not divisible by 4. Therefore exactly the composite integers other than 4 satisfy the condition.

Conclusion: Exactly the composite integers other than 4.

Review the idea: Prime numbers · Factorials

Because P(0)−1=0, write P(x)−1=xR(x), where R has integer coefficients. Setting x=1 gives R(1)=0, so R(x)=(x−1)Q(x), again with integer coefficients. Thus $$P(x)=1+x(x-1)Q(x).$$ If an integer r were a root, then $r(r-1)Q(r)=-1$. But r(r−1) is always an even integer, including zero, because one of two consecutive integers is even. The left side is therefore even and cannot equal −1. This contradiction rules out every integer root. Notice that the argument uses the integer-coefficient hypothesis to ensure Q(r) is an integer.

Conclusion: No integer root is possible.

Review the idea: Remainder and factor theorems · Parity

Write A,B,C for the triangle angles in this proof. The internal bisector from A meets the arc BC not containing A at its midpoint D; the equal inscribed angles BAD and DAC give equal chords BD and DC. Since $\angle IBD=B/2+\angle CBD=B/2+A/2$, while $\angle BID=180^\circ-\angle BIA=90^\circ-C/2=(A+B)/2$, triangle BID is isosceles and DI=DB. Here $\angle BIA=90^\circ+C/2$ follows from the angle sum in triangle ABI. In a right triangle, the sine of an acute angle is the opposite leg divided by the hypotenuse. The chord formula gives DB=2R sin(A/2); it follows by drawing a diameter through B and using the right triangle on that diameter. Dropping the perpendicular from I to AB gives AI=r/sin(A/2). Thus AI·ID=2Rr. Since I lies inside the circumcircle on secant AID, the power formula gives $$R^2-OI^2=AI\cdot ID=2Rr.$$ Rearranging proves the identity. Since $OI^2\ge0$ and R>0, R≥2r. Equality forces O=I. The three sides are then chords at the same distance r from O, hence have equal lengths by the right triangles from their midpoints. So the triangle is equilateral. Conversely its centres coincide and the identity gives equality.

Conclusion: The identity holds; R≥2r with equality exactly in the equilateral case.

Review the idea: Geometry foundations · Circles and power of a point

There are n! orderings of the underlying elements. For each ordering, consider its initial sets of sizes 0 through n. These sets are nested, so at most one can belong to the family. Count pairs consisting of an ordering and a family member that is one of its initial sets. A fixed member S with k elements occurs in exactly k!(n−k)! orderings: arrange its elements first, followed by the other elements. Therefore $$\begin{gathered}\sum_{S\in\mathcal F}|S|!(n-|S|)!\le n!,\\ \sum_{S\in\mathcal F}\frac1{\binom n{|S|}}\le1.\end{gathered}$$ The binomial coefficients are largest in the middle, because the ratio of consecutive ones is $(n-k)/(k+1)$, at least 1 up to the middle and at most 1 afterwards. Put $M=\binom n{\lfloor n/2\rfloor}$. Every term in the last sum is at least 1/M, so |F|/M≤1. All subsets of size floor(n/2) form an attaining family: two distinct equal-size finite sets cannot contain one another.

Conclusion: The maximum is the central binomial coefficient.

Review the idea: Combinations and binomial coefficients · Counting

At n=1 the smaller number is 1, so n>1. If n=ab with a,b>1, then $$2^n-1=(2^a-1)\bigl(1+2^a+\cdots+2^{a(b-1)}\bigr),$$ a product of integers greater than 1. Thus primality of the smaller number forces n to be prime. Now write n=$2^{t}$u, where u is odd. If u>1, put $X=2^{2^t}$. The identity $X^u+1=(X+1)(X^{u-1}-X^{u-2}+\cdots-X+1)$ gives a proper divisor X+1 of $2^{n}$+1; it is proper because u≥3 and X≥2 imply $X^{u}$+1>X+1. Therefore u=1 and n is a power of 2. The only number that is both prime and a power of 2 is n=2. It works, giving 3 and 5.

Conclusion: Only n=2.

Review the idea: Algebraic identities · Prime numbers

The case k=1 already meets the claim. Suppose k≥2. Put $d_i=x_{i+1}-x_i$, with cyclic indices; all are nonzero because cycle entries are distinct. Integer coefficients give $d_i\mid P(x_{i+1})-P(x_i)=d_{i+1}$. Going around the cycle shows $|d_0|\le|d_1|\le\cdots\le|d_{k-1}|\le|d_0|$, so every absolute difference equals a fixed positive integer d. Let M be the largest cycle entry. Its predecessor and successor are each distance d from M, and neither can exceed M. Thus both must equal M−d. If k≥3 these occupy distinct positions in the cycle, contrary to the distinctness of all entries. Therefore k=2. The polynomial P(x)=x gives a fixed point, and P(x)=1−x gives the two-cycle 0,1, so both permitted lengths occur.

Conclusion: Only cycles of length 1 or 2 occur.

Review the idea: Polynomial functions · Divisibility