Competition problem — Number theory

Library / /286 of 520

Number theory Difficulty 6.8 National olympiad Find the answer

5.39 It can be proven that for any given positive integer $n$ , every complex number of the form $r + s i (r, s$ both integers) can be expressed as a polynomial in $(-n+i)$ , and the coefficients of the polynomial all belong to $\{0,1,2, \cdots, n^{2}\}$ .

That is, the equation
$r+s i=a_{m}(-n+i)^{m}+a_{m-1}(-n+i)^{m-1}+\cdots+a_{1}(-n+i)+$
$a_{0}$
holds, where $m$ is a uniquely determined non-negative integer, and $a_{0}, a_{1}, \cdots, a_{m}$ are a unique set of numbers chosen from $\{0,1, 2, \cdots, n^{2}\}$ , with $a_{m} \neq 0$ .

We call this equation the expansion of $r+s i$ with base $-n+i$ , and write it briefly as
$r+s i=\left(a_{m} a_{m-1} \cdots a_{1} a_{0}\right)_{-n+i} .$

It is known that only a finite number of integers $k+0 i$ can be expanded as
$k=\left(a_{3} a_{2} a_{1} a_{0}\right)_{-3+i}, a_{3} \neq 0$

Find the sum of all such $k$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

【Solution】From the given conditions, we have
$\begin{aligned} k & =a_{3}(-3+i)^{3}+a_{2}(-3+i)^{2}+a_{1}(-3+i)+a_{0} \\ & =\left(-18 a_{3}+8 a_{2}-3 a_{1}+a_{0}\right)+\left(26 a_{3}-6 a_{2}+a_{1}\right) i \end{aligned}$

where $a_{1}, a_{2}, a_{3}$ are chosen from $\{0,1,2, \cdots, 9\}$ .
By comparing the imaginary parts on both sides of the equation, we get
$\begin{array}{l} 26 a_{3}-6 a_{2}+a_{1}=0 \\ a_{1}=2\left(3 a_{2}-13 a_{3}\right) \end{array}$

Therefore, $a_{1}$ is an even number.
If $a_{1}=0$ , then $3 a_{2}-13 a_{3}=0$ . Hence, $a_{2}$ is a multiple of 13, and the only possible value is $a_{2}=0$ , which leads to $a_{3}=0$ , a contradiction.

If $a_{1}=2$ , then $3 a_{2}-13 a_{3}=1$ , solving this gives $a_{2}=9, a_{3}=2$ . In this case, $a_{0}$ can take any value from $\{0,1,2, \cdots, 9\}$ .

If $a_{1}=4$ , then $3 a_{2}-13 a_{3}=2$ . Solving this gives $a_{2}=5, a_{3}=1$ . In this case, $a_{0}$ can also take any value from $\{0,1,2, \cdots, 9\}$ .

If $a_{1}=6$ , then $3 a_{2}-13 a_{3}=3$ , which has no solution in $\{0,1,2, \cdots, 9\}$ .
If $a_{1}=8$ , then $3 a_{2}-13 a_{3}=4$ , which also has no solution in $\{0,1,2, \cdots, 9\}$ .
Substituting these 20 solutions into
$k=-18 a_{3}+8 a_{2}-3 a_{1}+a_{0}$

and summing them up, we get
$\begin{aligned} \sum k= & 10[(-18) \times 2+8 \times 9-3 \times 2]+(0+1+2+\cdots+9) \\ & +10[(-18) \times 1+8 \times 5-3 \times 4]+(0+1+2+\cdots+9) \\ = & 490 \end{aligned}$

Therefore, the sum of all such $k$ is 490.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.