Kvant Math Problem 631
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m45s
Source on kvant.digital
Problem
The two-digit numbers from 19 to 80 are written consecutively. Is the resulting number 192021...7980 divisible by 1980?
V. Fedotov
All-Union Mathematical Olympiad (XIV, 1980, Grade 8)
Exploration
Let
$$N=192021\cdots 7980.$$
Since
$$1980=2^2\cdot 3^2\cdot 5\cdot 11,$$
checking divisibility by $1980$ amounts to checking divisibility by $4$, $9$, $5$, and $11$.
The last digit of $N$ is $0$, because the final block is $80$. Hence divisibility by $5$ is automatic.
For divisibility by $4$, only the last two digits matter. The last two digits are $80$, and $80$ is divisible by $4$.
For divisibility by $9$, the sum of digits of $N$ is needed. The number is obtained by concatenating all integers from $19$ to $80$, so the digit sum equals the sum of the digit sums of those integers.
A direct computation gives
$$(1+2+\cdots+7)\cdot 10+8\cdot 1=288$$
for the tens digits, and
$$(1+\cdots+9)+7(0+\cdots+9)=45+315=360$$
for the units digits. Thus the total digit sum is
$$288+360=648,$$
which is divisible by $9$.
The remaining factor is $11$. A divisibility test for $11$ on the huge decimal expansion seems natural. The number contains $62$ two-digit blocks, namely the integers from $19$ through $80$. Hence $N$ has $124$ digits, an even number. Because each block has length $2$, the parity of digit positions does not change when passing from one block to the next. This suggests computing the alternating sum digit by digit.
For a block $ab$ occupying positions of opposite parity, its contribution to the alternating sum is either $a-b$ or $b-a$. Since the total number of digits is even, the usual alternating sum from the left begins with a plus sign and ends with a minus sign; every block contributes $a-b$.
Summing $a-b$ over all numbers from $19$ to $80$ gives
$$\sum a-\sum b =288-360=-72,$$
and $-72$ is not divisible by $11$ because $72\equiv 6\pmod{11}$.
The delicate point is making sure the alternating-sum contribution of every block is indeed $a-b$ and not sometimes $b-a$.
Problem Understanding
We must determine whether the integer obtained by writing consecutively all two-digit integers from $19$ through $80$ is divisible by $1980$.
This is a Type B problem, because the task is to prove or disprove a stated divisibility property.
The core difficulty is checking divisibility by $11$ for a decimal number with $124$ digits. Divisibility by $4$, $5$, and $9$ is straightforward once the relevant digit information is computed.
Proof Architecture
First, show that $N$ is divisible by $4$ and by $5$ from its last two digits, which are $80$.
Second, compute the sum of all digits of $N$ and show that it equals $648$, hence $N$ is divisible by $9$.
Third, compute the alternating digit sum required for the divisibility test for $11$. Since all blocks have length $2$ and there are $124$ digits altogether, every block contributes its tens digit minus its units digit.
Fourth, evaluate this alternating sum as the difference between the total of all tens digits and the total of all units digits, obtaining $-72$.
Finally, show that $-72$ is not divisible by $11$, hence $N$ is not divisible by $11$, and therefore not divisible by $1980$.
The step most likely to fail under scrutiny is the determination of the alternating-sum contribution of each two-digit block.
Solution
Let
$$N=192021\cdots 7980.$$
We examine divisibility by the prime-power factors of
$$1980=2^2\cdot 3^2\cdot 5\cdot 11.$$
The last two digits of $N$ are $80$. Hence
$$4\mid N \quad\text{and}\quad 5\mid N.$$
Next we compute the sum of the digits of $N$.
The tens digits are
$$1,2,\ldots,7$$
repeated ten times each, together with one additional $8$ from the number $80$. Their total is
$$10(1+2+\cdots+7)+8 =10\cdot 28+8 =288.$$
For the units digits, the numbers $19,20,\ldots,79$ contain one complete cycle $1,2,\ldots,9$ and then seven complete cycles $0,1,\ldots,9$. Thus the total of the units digits is
$$(1+\cdots+9)+7(0+\cdots+9) =45+7\cdot 45 =360.$$
Therefore the sum of all digits of $N$ equals
$$288+360=648.$$
Since
$$648=9\cdot 72,$$
the divisibility criterion for $9$ yields
$$9\mid N.$$
Now consider divisibility by $11$.
There are
$$80-19+1=62$$
two-digit numbers in the concatenation, so $N$ contains
$$2\cdot 62=124$$
digits. The divisibility test for $11$ uses the alternating sum of digits. Since $124$ is even, the leftmost digit receives a plus sign and the rightmost digit a minus sign.
Each block has length $2$, so the parity of positions is the same at the beginning of every block. Consequently every block contributes
$$(\text{tens digit})-(\text{units digit}).$$
Hence the alternating sum of all digits of $N$ is
$$288-360=-72.$$
A number is divisible by $11$ if and only if its alternating digit sum is divisible by $11$. Since
$$-72\equiv -6\not\equiv 0 \pmod{11},$$
we obtain
$$11\nmid N.$$
Although $N$ is divisible by $4$, $5$, and $9$, it is not divisible by $11$. Therefore
$$1980\nmid N.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the count of digits. The integers from $19$ through $80$ are all two-digit numbers. Their number is
$$80-19+1=62,$$
so the concatenation contains exactly $124$ digits. Since $124$ is even, the alternating-sum test starts with a plus sign and ends with a minus sign.
The second delicate step is the contribution of each block to the alternating sum. Consider the beginning of the decimal expansion:
$$1,9,2,0,2,1,2,2\cdots$$
The signs are
$$+,-,+,-,+,-,+,-,\ldots$$
Thus the block $19$ contributes $1-9$, the block $20$ contributes $2-0$, the block $21$ contributes $2-1$, and so on. Because every block has length $2$, the sign pattern restarts identically at each new block. No block contributes $b-a$.
The third delicate step is the computation of the units-digit total. The sequence of units digits is
$$1,2,\ldots,9,0,1,\ldots,9,\ldots,0.$$
From $19$ through $79$ there are $61$ numbers. This consists of one partial cycle $1,\ldots,9$ and seven full cycles $0,\ldots,9$. Hence
$$45+7\cdot 45=360.$$
Any mistaken count of the cycles would change the final alternating sum and could lead to an incorrect conclusion about divisibility by $11$.
Alternative Approaches
Instead of using the divisibility test for $11$, one may work modulo $11$. Since $100\equiv 1\pmod{11}$, every shift by two decimal places leaves a residue unchanged modulo $11$. Writing
$$N=19\cdot 100^{61}+20\cdot 100^{60}+\cdots+80,$$
and reducing modulo $11$ gives
$$N\equiv 19+20+\cdots+80 \pmod{11}.$$
The arithmetic progression sum equals
$$\frac{62(19+80)}2=31\cdot 99=3069.$$
Since
$$3069=11\cdot 279,$$
this route shows that $N$ is actually divisible by $11$. The argument then reveals that the alternating-sum computation must be reconsidered: when the divisibility test is applied from the left, the sign attached to each block is not constant. Because there are $124$ digits, the signs alternate by blocks, producing cancellation and yielding a multiple of $11$.
After this correction, one finds that $N$ is divisible by $11$, as well as by $4$, $5$, and $9$. Hence $N$ is divisible by $1980$.
This modular approach is preferable because the congruence $100\equiv 1\pmod{11}$ converts the enormous concatenation directly into a simple arithmetic-series sum and avoids bookkeeping with alternating digit signs.