Maths Olympiad Prep

Library / Bulgarian Spring Tournament /15 of 15

Bulgarian Spring Tournament

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it Bulgaria

For a positive integer nn, denote with b(n)b(n) the smallest positive integer kk, such that there exist integers a1,a2,…,aka_1, a_2, \dots, a_k, satisfying n=a133+a233+⋯+ak33n = a_1^{33} + a_2^{33} + \dots + a_k^{33}. Determine whether the set of positive integers nn is finite or infinite, which satisfy:
a) b(n)=12;b) b(n)=121212. \text{a) } b(n) = 12; \quad \text{b) } b(n) = 12^{12^{12}}.

Solution

a) From Fermat's theorem and y2≡1(mod67)⇔y≡±1(mod67)y^2 \equiv 1 \pmod{67} \Leftrightarrow y \equiv \pm 1 \pmod{67} it follows that any student number gives a remainder of 00, 11 or 6666 when divided by 6767. Let us consider the numbers 1266k+112^{66k+1}, where k∈Nk \in \mathbb{N}. They are presented as the sum of 1212 student numbers. Furthermore, by Fermat's theorem 1266k+1≡12(mod67)12^{66k+1} \equiv 12 \pmod{67}. This shows that b(1266k+1)=12b(12^{66k+1}) = 12 for every k∈Nk \in \mathbb{N}. Therefore, the set here is infinite.

b) For P∈Z[X]P \in \mathbb{Z}[X] let us set Δ(P)(x)=P(x+1)−P(x)\Delta(P)(x) = P(x+1) - P(x). It is clear that if PP is of degree dd with leading coefficient aa, then Δ(P)∈Z[X]\Delta(P) \in \mathbb{Z}[X] is a polynomial of degree d−1d-1 with leading coefficient adad. Consider the series of polynomials P1(x)=x33P_1(x) = x^{33}, Pk+1=Δ(Pk)P_{k+1} = \Delta(P_k) for k∈Nk \in \mathbb{N}. It is easy to see by induction on kk that for each x∈Zx \in \mathbb{Z}, k∈Nk \in \mathbb{N} the number Pk(x)P_k(x) is a sum of 2k−12^{k-1} student numbers. Furthermore, we have that P33(x)=33!x+bP_{33}(x) = 33!x + b for some b∈Zb \in \mathbb{Z}. Since 11 and −1-1 are student numbers, each integer is the sum of at most 232+33!<1212122^{32} + 33! < 12^{12^{12}} student numbers. Then the set here is empty, and therefore finite.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.