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

Let $L=\operatorname{lcm}(1,2,\ldots,n)$ and choose k so that $2^k\le n\lt2^{k+1}$. Since n≥2, k≥1 and L is even. The exact power of 2 dividing L is $2^k$. Among 1,…,n, the only number divisible by $2^k$ is $2^k$ itself: the next positive multiple is already greater than n. Consequently $L/2^k$ is odd, whereas $L/j$ is even for every other j in the sum. It follows that $$L\left(1+\frac12+\cdots+\frac1n\right)=\sum_{j=1}^n\frac Lj$$ is odd. If the harmonic sum were an integer, its product with the even integer L would be even. This contradiction proves nonintegrality.

Conclusion: The sum is not an integer for any n≥2.

Review the idea: Greatest common divisor · Parity

If a≥b+2 are two entries, replacing them by a−1,b+1 preserves positivity and their sum, while the square sum decreases by $a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1)\gt 0$. Thus a minimum cannot contain entries differing by at least 2. A minimum exists because only finitely many positive integer tuples sum to S. Write S=nq+r with 0≤r<n. The only possible entries in a minimizing tuple are q and q+1, and the sum forces exactly r entries q+1 and n−r entries q. Such a tuple exists, and all tuples failing this form can be improved. Hence the minimum is $(n-r)q^2+r(q+1)^2$, with equality exactly for permutations of that multiset.

Conclusion: If S=nq+r, the minimum is (n−r)q²+r(q+1)²; entries differ by at most 1.

Review the idea: Inequality rules and signs · Proof methods

There are finitely many lines determined by pairs of set points and finitely many set points. Noncollinearity provides at least one positive point-to-line distance. Choose a point P and a line ℓ through at least two set points for which that positive distance h is least. Let H be the perpendicular foot from P to ℓ. Suppose ℓ contained at least three set points. Two, called A and B, can be chosen on the same closed ray from H, with A closer to H than B; if one is H, it may serve as A. Then AB≤HB<PB. The area of triangle PAB computed using base AB is AB·h/2. Using base PB, its altitude from A is therefore $h^{\prime}=h\,AB/PB\lt h$. But PB is a line through two set points and A is a set point off it, contradicting minimality of h. Thus ℓ contains exactly two set points.

Conclusion: An ordinary line exists, by the minimum-positive-distance argument.

Review the idea: Triangle area ratios · Proof methods

There are $q^p$ labelled colourings, of which q are constant. A colouring fixed by a nonidentity rotation through j positions, with 1≤j<p, must be constant: repeated addition of j visits every position because gcd(j,p)=1. Thus every nonconstant colouring has p distinct rotations, and these rotation classes partition the $q^p-q$ nonconstant colourings. The necklace count is therefore $q+(q^p-q)/p=(q^p+(p-1)q)/p$. Since the number of nonconstant classes is an integer, p divides $q^p-q$. This also covers q=1.

Conclusion: The count is $(q^p+(p-1)q)/p$, and $p\mid q^p-q$.

Review the idea: Circular permutations · Counting with bijections

Every multiple of p contributes one factor p, every multiple of p² contributes one additional factor, and so on. Thus the exponent is $\sum_{j\ge1}\lfloor n/p^j\rfloor$, a finite sum. Write $n=\sum_{i=0}^r d_i p^i$ with digits 0≤$d_i$<p. Then $\lfloor n/p^j\rfloor=\sum_{i=j}^r d_i p^{i-j}$. Summing over j gives $$\begin{aligned}\sum_{i=1}^r d_i(1+p+\cdots+p^{i-1})&=\frac{\sum_{i=1}^r d_i(p^i-1)}{p-1}\\&=\frac{n-s_p(n)}{p-1}.\end{aligned}$$ For n=0 both numerator and factorial exponent are zero, so that case is included.

Conclusion: The exponent is (n−$s_p$(n))/(p−1).

Review the idea: Factorials · Number bases and digit problems

Angles here use radians, so $\pi$ radians means 180 degrees. We use $2\cos^2\theta=1+\cos(2\theta)$, the cosine double-angle identity, in reverse to halve an angle. At n=0 the proposed formula is 2cos(π/2)=0. If it holds for n, then $2+u_n=2+2\cos(\pi/2^{n+1})=4\cos^2(\pi/2^{n+2})$. The half-angle lies between 0 and π/2, so its cosine is positive and the nonnegative square root gives the next formula. For the estimate, induction from the recurrence gives 0≤$u_n$≤2. Rationalisation yields $2-u_{n+1}=(2-u_n)/(2+\sqrt{2+u_n})\le(2-u_n)/2$. Starting from 2−u₀=2 and iterating gives $0\le2-u_n\le2/2^n=2^{1-n}$.

Conclusion: $u_n=2\cos(\pi/2^{n+1})$; the error is at most $2^{1-n}$.

Review the idea: Trigonometry foundations · Recursive sequences