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

If $n=\prod p^a$, counting the integers not divisible by any prime factor gives $\varphi(n)=n\prod(1-1/p)=\prod p^{a-1}(p-1)$. This formula follows by inclusion–exclusion, since for each product of distinct prime divisors exactly n divided by that product of the numbers 1,…,n are multiples. To justify the subtraction in inclusion–exclusion, an integer divisible by r of the relevant distinct primes contributes total weight $\sum_{j=0}^r(-1)^j\binom rj=(1-1)^r$: it is counted once when r=0 and zero times otherwise. Thus precisely the coprime integers remain. Each factor p−1 must divide 12, so p is one of 2,3,5,7,13. A factor 13 contributes 12; it can occur only to exponent 1, and the only optional additional prime factor is a single 2, whose totient contribution is 1. This gives 13,26. A factor 7 contributes 6 and also has exponent 1. The remaining contribution 2 comes either from $2^{2}$ or from 3; in the latter case an optional single 2 is allowed. This gives 28,21,42. A factor 5 contributes 4, leaving contribution 3. No product of the remaining allowed prime-power contributions is 3: 3 contributes an even number, and powers of 2 contribute powers of 2. So 5 cannot occur. Finally use only 2 and 3. A factor 3 in the target requires exponent 2 on 3, contributing 6; the remaining factor 2 forces exponent 2 on 2. This gives 36. Substitution in the product formula verifies all six numbers.

Conclusion: Exactly 13,21,26,28,36,42.

Review the idea: Counting and summing divisors · Complete and reduced residue systems

Put c=f(1)−1, an integer. Taking n=1 in the given equation yields $$f(m+1)-f(m)=f(m)-f(m-1)+2.$$ Thus the first differences increase by 2. Starting from f(0)=0 and f(1)=1+c, induction gives $f(m)=m^2+cm$ for every nonnegative integer m: the next difference is 2m+1+c. Taking m=0 in the original equation gives $f(n)+f(-n)=2n^2$, which extends the same formula to negative n. Nonnegativity at 1 and −1 gives 1+c≥0 and 1−c≥0. Because c is an integer, c is −1,0 or 1. Conversely the three functions $n^2-n,n^2,n^2+n$ are nonnegative at every integer, since the first and third are products of consecutive integers. Expanding their values verifies the given equation. Hence all three and only those three functions work.

Conclusion: $f(n)=n^2-n$, $f(n)=n^2$, or $f(n)=n^2+n$.

Review the idea: Solving functional equations · First order linear recurrences

Use coordinates with A as origin. For a vector X, write |X| for its length, and for $X=(x_1,x_2)$, $Y=(y_1,y_2)$ define the dot product $X\cdot Y=x_1y_1+x_2y_2$. Every point X among B,C,D is nonzero, so define $X^{\prime}=X/|X|^2$. Expansion gives $$\begin{aligned}|X^{\prime}-Y^{\prime}|^2&=\frac1{|X|^2}+\frac1{|Y|^2}-\frac{2X\cdot Y}{|X|^2|Y|^2}\\&=\frac{|X-Y|^2}{|X|^2|Y|^2}.\end{aligned}$$ Taking nonnegative square roots yields the identity suggested in the hint. The usual triangle inequality for B′,C′,D′ now gives $$\frac{BD}{AB\cdot AD}\le\frac{BC}{AB\cdot AC}+\frac{CD}{AC\cdot AD}.$$ Multiply by the positive product AB·AC·AD to obtain the requested inequality. For a square ABCD of side s>0 in boundary order, both diagonals have length s√2. The left side is 2$s^{2}$ and the right side is $s^{2}$+$s^{2}$, so equality is attained. This proof applies regardless of whether the original four points form a convex quadrilateral.

Conclusion: The inequality always holds; a square gives equality.

Review the idea: Triangle inequalities · Pythagoras and stewart

Let e be the number of edges, and let $d_1,\ldots,d_n$ be the vertex degrees. If u,v are adjacent, their neighbour sets are disjoint: a common neighbour would form a triangle. Those two sets lie among the n vertices, so d(u)+d(v)≤n. Summing over all edges yields $\sum_i d_i^2\le ne$, because vertex i contributes its degree once for each of its $d_i$ incident edges. Also $\sum_i d_i=2e$, since every edge has two ends. The identity $$n\sum_i d_i^2-\left(\sum_i d_i\right)^2=\sum_{i\lt j}(d_i-d_j)^2\ge0$$ therefore gives 4$e^{2}$≤$n^{2}$e. If e=0 the bound is immediate; otherwise divide by e to obtain e≤$n^{2}$/4 and take the integer part. For attainment, split the vertices into groups of sizes floor(n/2) and ceiling(n/2), join every pair from different groups, and join none within a group. Three vertices always include two in the same group, so no triangle occurs. The edge count is their product, floor($n^{2}$/4).

Conclusion: The maximum is floor($n^{2}$/4), attained by two balanced groups joined across.

Review the idea: Counting · Sum of squares

The b=1 case has both sides zero. Suppose b>1. Coprimality implies b does not divide ak for 1≤k≤b−1, so ak/b is not an integer. For any noninteger real t and integer a, $\lfloor t\rfloor+\lfloor a-t\rfloor=a-1$: writing t as its integer part plus a fractional part strictly between 0 and 1 proves this directly. Apply it to t=ak/b. Since a−ak/b=a(b−k)/b, we get $$\left\lfloor\frac{ak}{b}\right\rfloor+\left\lfloor\frac{a(b-k)}b\right\rfloor=a-1.$$ Sum over all k from 1 to b−1. The map k↦b−k permutes these indices, so the left side is twice the original sum, even if an index pairs with itself. Thus 2S=(a−1)(b−1), as required.

Conclusion: The sum is (a−1)(b−1)/2.

Review the idea: Floor and ceiling functions · Greatest common divisor

If x≥3, then y≥x≥3 and xyz≥9z, while x+y+z+2≤3z+2<9z for positive z. This is impossible. If x=1, the equation becomes yz=y+z+3, hence $(y-1)(z-1)=4$. Its factors are positive and ordered, so they are (1,4) or (2,2). This gives (1,2,5) and (1,3,3). If x=2, the equation is 2yz=y+z+4, and multiplying by 2 and completing the product gives $(2y-1)(2z-1)=9$. Because y,z≥2, both factors are at least 3, so both equal 3. This gives (2,2,2). Each of the three triples satisfies the original equation, proving completeness.

Conclusion: Exactly $(1,2,5),(1,3,3),(2,2,2)$.

Review the idea: Factorisation integer solutions · Inequality rules and signs