Number theoryDifficulty 7.7National Olympiad, round 2Prove itBulgaria
For a positive integer n, denote with b(n) the smallest positive integer k, such that there exist integers a1,a2,…,ak, satisfying n=a133+a233+⋯+ak33. Determine whether the set of positive integers n is finite or infinite, which satisfy: a) b(n)=12;b) b(n)=121212.
Solution
a) From Fermat's theorem and y2≡1(mod67)⇔y≡±1(mod67) it follows that any student number gives a remainder of 0, 1 or 66 when divided by 67. Let us consider the numbers 1266k+1, where k∈N. They are presented as the sum of 12 student numbers. Furthermore, by Fermat's theorem 1266k+1≡12(mod67). This shows that b(1266k+1)=12 for every k∈N. Therefore, the set here is infinite.
b) For P∈Z[X] let us set Δ(P)(x)=P(x+1)−P(x). It is clear that if P is of degree d with leading coefficient a, then Δ(P)∈Z[X] is a polynomial of degree d−1 with leading coefficient ad. Consider the series of polynomials P1(x)=x33, Pk+1=Δ(Pk) for k∈N. It is easy to see by induction on k that for each x∈Z, k∈N the number Pk(x) is a sum of 2k−1 student numbers. Furthermore, we have that P33(x)=33!x+b for some b∈Z. Since 1 and −1 are student numbers, each integer is the sum of at most 232+33!<121212 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.