Find all natural numbers $N$ consisting of exactly $1112$ digits (in decimal notation) such that: (a) The sum of the digits of $N$ is divisible by $2000$; (b) The sum of the digits of $N+1$ is divisible by $2000$; (c) $1$ is a digit of $N$.
Problem
Source: PAMO 2007 Q1
Tags: modular arithmetic, number theory unsolved, number theory
10.12.2013 15:35
Such a number $N$ must end in exactly $889$ digits $9$; then it's trivial.
11.01.2014 12:56
Denote $s(N)$ the sum of the digits of $N$. Let $N$ end in exactly $k$ digits $9$. Then $N+1$ has the same digits as $N$ does with the exception of the last $k$, which are zero, and the digit right before these, which increases by $1$. For instance, $1999+1=2000$. Hence $s(N+1)=s(N)-9k+1$. Since $s(N+1)$ and $s(N)$ are both multiples of $2000$, $9k\equiv 1\pmod {2000}$. Multiplying this by $222$, we get $1998k\equiv 222\pmod{2000}$, dividing then by $2$ gives $999k\equiv 111\pmod{1000}$, or $k\equiv 889\pmod{1000}$. Since $0\le k\le 1112$, only $k=889$ is possible. Let the sum of the first $1112-k=223$ digits be $s'$. Clearly, $s'\le 223\cdot 9=2007$, and $2000|s(n)=s'+9\cdot 889$ implies $2000|s'+1$. Therefore only $s'=1999$ is possible. There is a $1$ amongst the first $223$ digits of $N$. The sum of all the other $222$ digits is $1999-1=1998=222\cdot 9$. This can only happen when all these digits are $9$'s. But because $N$ ends in exactly $889$ digits $9$, the $1$ must be the $223^{\text{rd}}$ digit. Hence, $N$ is the $1112$-digit integer with only digits $9$, except for the $223^{\text{rd}}$ digit $1$. (This $N$ does satisfy the conditions.)