4
$\begingroup$

The question

I have attempted problem 3 from the Senior O-level Tournament of Towns paper, Fall 2020. The question is as follows:

A positive integer number N is divisible by 2020. All its digits are different and if any two of them are swapped, the resulting number is not divisible by 2020. How many digits can such a number N have?

Sergey Tokarev

My attempt

Let $n$ be the number of digits of $N$. I initially noticed that $4 \leq n \leq 10$, since for all digits of $N$ to be distinct we can have at most $10$ digits. This gave me the impression that this problem could be solved by investigating each of these cases.

Let us first write $N$ as $2020k = 2000k + 20k$. Let $2k$ have digits $d_1d_2\cdots d_m$, then $N = (d_1d_2\cdots d_m)000 + (d_1d_2\cdots d_m)0$.

Case n = 4: Then $2k = d_1$ and $N = d_1000 + d_10 = d_10d_10$, so $N$ must have a repeating digit.

Case n = 5: Then $2k = d_1d_2$ and $N =d_1d_1000 + d_1d_20 = d_1d_2d_1d_20$, so $N$ must have a repeating digit.

Case n = 6: Then $2k = d_1d_2d_3$ and $N = d_1d_2d_3000 + d_1d_2d_30 = d_1d_2(d_3 + d_1)d_2d_30$, so $N$ must have a repeating digit.

This argument no longer works for $n \geq 7$. But we do know that

  1. $d_m \in \{0, 2, 4, 6, 8\}$ since $2k = d_1d_2\cdots d_m$, and
  2. $N$ must end in $0$.

I used this to find numbers for $n = 7, 8, 9$ and $10$ with all distinct digits that are also divisible by $2020$ because they satisfy the observations listed above.

\begin{array}{|c|c|c|c|} \hline n & 7 & 8 & 9 & 10\ \\ \hline N & 4981320 & 64975320 & 869753420 & 2537618940 \\ \hline \end{array}

Claim: If $N$ is a multiple of $2020$ and has all distinct digits, then swapping any two digits results in a number $N'$ where $2020 \not \mid N'$.

proof. Let $N = a_na_{n-1}\cdots a_j\cdots a_i\cdots a_1$ and $N' = a_na_{n-1}\cdots a_i\cdots a_j\cdots a_1$ for any $i < j$. If $2020 \mid (N' - N)$ then $2020 \mid N'$. Suppose, WLOG, that $a_i > a_j$ so that $N' > N$, then $$N' - N = 10^{j - 1}(a_i - a_j) - 10^{i - 1}(a_i - a_j) = (a_i - a_j)(10^{j - 1} - 10^{i - 1})$$

So $N' - N$ must be a multiple of $10$. Therefore, for the claim to hold, $N'$ must not be a multiple of $4$ or $101$, since $2020 = 2^2 \times 5 \times 101$. We know that $1 \leq a_i - a_j \leq 9$, thus we can safely conclude that $N' - N$ is never a multiple of $101$. Therefore, $2020 \not \mid (N' - N)$.

Therefore, $N$ can have $7, 8, 9$ or $10$ digits and we are done.

I think my solution is correct, but I don't like that I had to manually find $N$'s for $7 \leq n \leq 10$. Is there a different way to argue for those cases or a more systematic way to find $N$'s for those cases? Or if you have a different way to solve the problem, I would also like to see it.

$\endgroup$
2
  • 1
    $\begingroup$ Note that $3981420$ is still a multiple of 2020, so your claim isn't true. Where it fails is that $10^4 - 10^0 = 9999$ is a multiple of 101, contradicting "$ N' - N$ is never a multiple of 101". $\endgroup$ – Calvin Lin Mar 4 at 23:52
  • 1
    $\begingroup$ Your argument for $n=6$ doesn't write hold. $d_2$ need not be a repeating digit if $ d_3 + d_1 \geq 10$. EG $2020\times 377 = 761540$ has distinct digits. $\endgroup$ – Calvin Lin Mar 5 at 0:06
1
$\begingroup$

The error in your logic is that $N' - N = (a_i - a_j) (10^{i-1} ) ( 10^{j-i } - 1 ) $ could be a multiple of 101 when $ j-i = 4, 8$.

This yields a multiple of 2020 if $(a_i - a_j) (10^{i-1} )$ is a multiple of 20.


If the number has 7 or more digits, then swapping the 1st and 5th digit yields a difference of $(a_n - a_{n-4}) \times 9999 \times 10^{n-5} $, which is a multiple of 2020.

Hence there are no solutions with 7 or more digits.


Your arguments for $n = 4, 5$ are correct.
However, it fails for $n=6$ in the event that $ d_3 + d_1 \geq 10$, as the carry over makes the second digit $d_2 + 1$, so it need not be a repeated digit with the other $d_2$. (It could still repeat with another digit though).
As an explicit example, $ 2020 \times 377 = 761540$ has distinct digits. I found it through trial and error.


If remains to find an example for $n=6$. If no such example can be found, then the answer to the question is "no digits" (which seems unlikely as an answer).

Suppose $N = a_6a_5a_4a_3a_2a_1$. Then, to ensure that the swap doesn't yield a difference that is a multiple of 2020,

  • In order to be a multiple of 101, we just need to concern ourselves with terms that are 4 apart.
  • We then need to check that $(a_6 - a_2)10$ and $(a_5 - a_1)$ are not multiples of 20.

These are satisfied by $761540$, so it is a valid example.

Hence the number must have 6 digits.


To find the counterexample without excessive trial and error, since (using OP's notation) $\overline{d_1d_2d_3} \times 1010 = \overline{d_1d_2(d_3+d_1)d_2d_30}$, then the conditions that we need are (I might have missed some):

  • $0, d_1, d_2, d_3 $ are distinct digits
  • $d_3$ is a multiple of 2
  • $d_1 - d_3$ is not a multiple of 2.
  • $d_2$ is not a multiple of 20.
  • $d_1 + d_3 \geq 11$ (cannot be 10 which leaves the digit of 0)
  • $d_2 + 1 \neq d_1, d_3, 10$
  • $d_1 + d_3 - 10 \neq d_2 $

These are satisfied by $ 754 = 377 \times 2$, which is why the example works. Smaller values include $348$, which yields $351480$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.