Problem of the Week

Problem 12 Solution

A special congratulations to Yat Sum from from Cambourne Village College for being the only person to successfully solve part i, with a partial solution on ii.

Solution for i

For any $n$ -digit positive integer $N$ with digits $a_1, a_2, \ldots, a_n$ , we can express $N$ as:

$N = 10^{n-1}a_1 + 10^{n-2}a_2 + \dots + 10^0 a_n.$

Rewrite $N$ by decomposing each term $10^k a_i$ as $(10^k - 1)a_i + a_i$ :

$N = (10^{n-1} - 1)a_1 + (10^{n-2} - 1)a_2 + \dots + (10^0 - 1)a_n + (a_1 + a_2 + \dots + a_n).$

Each term $(10^k - 1)a_i$ is divisible by 3 because $10^k - 1$ is a multiple of 9. Therefore, $N$ is divisible by 3 if and only if the sum of its digits, $a_1 + a_2 + \dots + a_n$ , is divisible by 3.

Solution for ii

Lemma 1: Any number in the form $100\ldots01$ with an even number of digits is divisible by 11.

Performing long division of $100\ldots01$ by 11 shows that 11 divides each block of two zeros, leaving a remainder of 1 carried over at each step.

With an even number of digits, this remainder of 1 continues to the last digit and balances out exactly, showing that all even-length numbers of the form $100\ldots01$ are divisible by 11.

Lemma 2: Any even-length number in the form $99\ldots99$ is divisible by 11.

Explanation:
Each block of two nines (like 99) is divisible by 11. So any even-length sequence of 9’s, like $99\ldots99$ , is divisible by 11.

Proof:

Let $N = 10^n a_1 + 10^{n-1} a_2 + \dots + a_n$ . Rewrite $N$ by decomposing it as a sum of terms in the form $100\ldots01$ and $99\ldots99$ :

$N = (100\ldots01)a_1 + (99\ldots99)a_2 + \dots + (a_1 - a_2 + a_3 - \dots + (-1)^{n+1}a_n).$

The terms in the form $100\ldots01$ and $99\ldots99$ are divisible by 11, so $N$ is divisible by 11 if and only if the alternating sum of its digits,

$a_1 - a_2 + a_3 - \dots + (-1)^{n+1}a_n,$

is divisible by 11.

Problem of the Week

Problem 12 Solution

Site Search