Track / Stage 5 / 375 of 400 #975 of 2000

Problem 975

AIME late

Number theory Difficulty 5.9 Find the answer

$36 \cdot 8$ Let $A$ be an $n$ -digit positive integer, $n \geqslant 2$ , and $B$ be a $k$ -digit positive integer, $k \geqslant 1$ . Then there are $n-1$ ways to insert $B$ entirely between two adjacent digits of $A$ , resulting in an $n+k$ -digit positive integer $C$ . For example, if $A=1991$ and $B=35$ , there are three insertion methods: $C$ can be 135991, 193591, or 199351.
If for every $A$ that is divisible by $B$ , inserting $B$ into $A$ in any way results in a $C$ that is also divisible by $B$ , then $B$ is called a harmonious number. Among the 15 numbers $1,2,3,4,5,6,7,8,9,10,11,12,15,66,90$ , the number of harmonious numbers is
(A) 6.
(B) 8.
(C) 10.
(D) 11.
(3rd "Five Sheep Cup" Junior High School Mathematics Competition, 1991)

Your answer

Official solution

［Solution］By checking each number, we can easily find:
(1) 1 is a harmonious number;
(2) If $A$ is divisible by 2, then the last digit of $A$ is even. Inserting 2 arbitrarily into $A$ results in the last digit of $C$ still being even, so $C$ is divisible by 2. Therefore, 2 is a harmonious number;
(3) Note that: A natural number is divisible by 3 if and only if the sum of its digits is also divisible by 3. It is easy to verify that 3 is a harmonious number;
(4) If $A$ is divisible by 11, then the difference between the sum of the digits in odd positions and the sum of the digits in even positions of $A$ is a multiple of 11. After inserting 11 arbitrarily into $A$ to get $C$ , the difference between the sum of the digits in odd positions and the sum of the digits in even positions remains unchanged, i.e., it is still a multiple of 11, so $C$ is divisible by 11. Therefore, 11 is a harmonious number;
Similarly to (2), we can prove that 5 and 10 are harmonious numbers;
Similarly to (3), we can prove that 9 is a harmonious number;
Since 2 and 3 are harmonious numbers, we can prove that 6 is a harmonious number;
Since 3 and 5; 2, 3, and 11; 9 and 10 are harmonious numbers, we can prove that 15, 66, and 90 are harmonious numbers.
In addition, it can be calculated that 4, 7, 8, and 12 are not harmonious numbers.
Thus, there are 11 harmonious numbers among the above numbers.
Therefore, the answer is $(D)$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.