Maths Olympiad Prep

Library / /38 of 45

Algebra Difficulty 6.4 National olympiad Prove it Romania

For any integer n2n \ge 2 denote by AnA_n the set of solutions of the equation
x=x2+x3++xn. x = \lfloor \frac{x}{2} \rfloor + \lfloor \frac{x}{3} \rfloor + \dots + \lfloor \frac{x}{n} \rfloor.
a) Determine the set A2A3A_2 \cup A_3.
b) Prove that the set A=n2AnA = \bigcup_{n \ge 2} A_n is finite and find maxA\max A.

Solution

Notice that AnZA_n \subset \mathbb{Z} for all nNn \in \mathbb{N}, n2n \ge 2.

a) The elements of A2A_2 satisfy the inequalities x2<2xxx - 2 < 2x \leq x. By inspection, we obtain A2={1,0}A_2 = \{-1, 0\}. The elements of A3A_3 satisfy the inequalities 5x12<6x5x5x - 12 < 6x \leq 5x. By inspection, we have A3={7,5,4,3,2,0}A_3 = \{-7, -5, -4, -3, -2, 0\}, so A2A3={7,5,4,3,2,1,0}A_2 \cup A_3 = \{-7, -5, -4, -3, -2, -1, 0\}.

b) For n4n \ge 4 and xAnx \in A_n we have x(12+13++1n)xx \le \left(\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\right) x.
From 12+13++1n>1\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} > 1 we obtain x0x \ge 0.
For x,nZx, n \in \mathbb{Z} and n2n \ge 2 we get xnx(n1)n\lfloor \frac{x}{n} \rfloor \ge \frac{x - (n - 1)}{n}. Therefore, if n4n \ge 4 and xAnx \in A_n, then
xx2+x3+x4x12+x23+x34, x \ge \lfloor \frac{x}{2} \rfloor + \lfloor \frac{x}{3} \rfloor + \lfloor \frac{x}{4} \rfloor \ge \frac{x-1}{2} + \frac{x-2}{3} + \frac{x-3}{4},
implying x23x \le 23. Hence the set AA is upper bounded.
Because A{5,4,,23}A \subset \{-5, -4, \dots, 23\} and 23A423 \in A_4, then maxA=23\max A = 23.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.