MO Landesrunde Klasse 9 Mock Paper 3: Questions, Hints and Solutions

Assume such an n exists. Since $2^n-1$ is odd, n is odd. Let p be its smallest prime divisor, so p is odd. Multiplication by 2 permutes the nonzero residues 1,…,p−1 modulo the odd prime p. Multiplying this list before and after the permutation, and cancelling its invertible product, gives Fermat’s congruence $2^{p-1}\equiv1\pmod p$; thus a least positive exponent d with $2^d\equiv1\pmod p$ exists. Whenever $2^k\equiv1\pmod p$, division $k=qd+r$, with $0\le r\lt d$, gives $2^r\equiv1\pmod p$, hence r=0 by minimality. Applying this to k=n and k=p−1 shows d divides both n and p−1. If d were greater than 1, a prime divisor of d would divide n but be at most d≤p−1, contradicting the minimality of p. Therefore d=1. This would give $2\equiv1\pmod p$, impossible. The contradiction proves the claim.

Conclusion: There is no such integer n greater than 1.

Review the idea: Number theory theorems · Greatest common divisor

The expression is unchanged by permuting x,y,z, so assume x≤y≤z. Put u=y−x≥0, v=z−y≥0 and L=u+v=z−x≤1. The expression becomes $u^2v^2L^2$. From $(u-v)^2\ge0$, $uv\le L^2/4$, hence the product is at most $L^6/16\le1/16$. Equality requires L=1 and u=v=1/2, forcing x=0,y=1/2,z=1 in the ordered case. All permutations of (0,1/2,1) attain 1/16, and there are no other equality cases.

Conclusion: Maximum 1/16, at permutations of (0,1/2,1).

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

Consider the transformation centred at G that doubles every distance and reverses its direction. It sends each line to a parallel line, because differences of point coordinates are multiplied by −2. The centroid has coordinate average $G=(A+B+C)/3$, while $M=(B+C)/2$. Hence $A-G=-2(M-G)$, which is the centroid ratio AG:GM=2:1 and shows that it sends the midpoint M of BC to A. Define H′ as the image of O. The line OM is perpendicular to BC because O is the circumcentre and M is the chord midpoint. Its image AH′ is parallel to OM, so AH′ is an altitude. Repeating for the other two side midpoints shows that H′ lies on all three altitudes, hence H′=H. By construction $\overrightarrow{GH}=-2\overrightarrow{GO}$, establishing collinearity and OH=3OG. If O=G, the construction gives H=G as well and the same formulas hold.

Conclusion: G lies on OH with GH=2OG and OH=3OG, including the coincident-centre case.

Review the idea: Concurrency and collinearity · The midpoint theorem

Fix one of the m positions. There are $2^{m-1}$ words with 0 there and the same number with 1. Choosing one of each gives $2^{2m-2}$ unordered pairs differing at this position; there is no division by 2 because the zero-word and one-word play distinct roles. Summing over all m positions counts each pair exactly as many times as its distance. Thus the required sum is $m2^{2m-2}$. The formula also gives 1 when m=1, as it should.

Conclusion: The sum is $m2^{2m-2}$.

Review the idea: Counting

List the $\varphi(m)$ reduced residues as $r_1,\ldots,r_t$, where t=φ(m). Each $ar_i$ is still coprime to m. If $ar_i\equiv ar_j\pmod m$, cancellation using gcd(a,m)=1 gives $r_i\equiv r_j$, so all the classes are distinct. Thus multiplication by a permutes the list. Multiplying the residues of the whole list gives $a^t r_1\cdots r_t\equiv r_1\cdots r_t\pmod m$. The product of reduced residues is coprime to m and has a multiplicative inverse modulo m, by Bézout’s identity. Cancelling it proves $a^t\equiv1\pmod m$, as required.

Conclusion: Euler’s congruence follows from a permutation of reduced residues.

Review the idea: Complete and reduced residue systems · Greatest common divisor

The equations are x²+c=y and y²+c=x. Subtracting gives $(x-y)(x+y)=-(x-y)$. Since x≠y, division yields x+y=−1. Substituting y=−1−x gives $x^2+x+c+1=0$. This quadratic has two distinct real roots exactly when its discriminant $1-4(c+1)=-4c-3$ is positive, or c<−3/4. The roots sum to −1, so the ordered pairs are the two orders of $(-1+\sqrt{-4c-3})/2$ and $(-1-\sqrt{-4c-3})/2$. They satisfy both original equations because each root t obeys t²+c=−1−t. At equality of the discriminant they coincide and are excluded.

Conclusion: Exactly c<−3/4; the pair consists of the two roots of x²+x+c+1=0 in either order.

Review the idea: Equations and quadratics · Functions inverses and composition