Solution for March 2012

The Problem:

Can the sixteen digits $$2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9$$ be arranged to form two 8-digit numbers $A$ and $B$ with $B= 2A$? Remarks. You might wish to practice by arranging the digits $1,1,2,2,4,4,5,5,7,7,8,8$ into two 6-digit numbers $C$ and $D$ with $D=2C$, but please do not submit the solution for this practice problem; and please do not submit any long solution to our monthly problem that involves intricate case analyses.

Solution: No.

Correct solutions were submitted by

Lamis Alsheikh (Syria)	Martin Argerami (Regina)
Patrik Bak (Slovakia)	Bojan Bašić (Serbia)
Luigi Bernardini (Italy)	Aleksandar Blazhevski-Cane (Macedonia)
Lou Cairoli (USA)	Bernard Collignon (France)
Hubert Desprez, (France)	Mei-Hui Fang (Austria)
Philippe Fondanaiche (France)	Bruce Golfman (Austria)
Gruian Cornel (Romania)	Verena Haider (Austria)
Tony Harrison (England)	Tom Holens (Manitoba)
Benoît Humbert (France)	Ilijevski (Macedonia)
Wolfgang Kais (Germany)	Omran Kouba (Syria)
Albert Stadler (Switzerland)	Hakan Summakoğlu (Turkey)

The fastest solution (which was almost everybody's first choice) uses modular arithmetic. For those readers who might be unfamiliar with modular arithmetic we provide a second solution which is longer but straightforward.

Solution 1.
(For this solution one must know that any number is congruent modulo 3 to the sum of its digits.) For any arrangement of the given digits that produces two numbers $A$ and $B$, we see that
\begin{eqnarray*}
A + B &\equiv& \mbox{ (sum of the digits of $A+B$)}\\
&\equiv& \mbox{ (sum of the digits of $A$) + (sum of the digits of $B$)}\\
&\equiv& 2\cdot(2+3+4+5+6+7+8+9) \equiv 2\cdot 2 \equiv 1 \quad (\mbox{mod }3).
\end{eqnarray*}
If, however, $A$ and $B$ were to satisfy $B = 2A$, then
$$A + B = A + 2A = 3A \equiv 0 \quad (\mbox{mod }3).$$
Since both congruences cannot be satisfied simultaneously, the answer is no, the given sixteen digits cannot be arranged to form two numbers $A$ and $B$ with $B= 2A$.


Solution 2. We shall present Lamis Alsheikh's solution, which in some ways was the simplest of the submissions that avoided modular arithmetic. To follow his argument you might want first to look at the suggested practice problem: to arrange the digits $1,1,2,2,4,4,5,5,7,7,8,8$ into two 6-digit numbers $C$ and $D$ with $D=2C$. You perhaps recognize that these are the digits in one period of the decimal expansion of both 1/7 and 2/7, so $C = 142857$ serves as a solution (with $D = 2C = 285714$). Note that the 5 in $D$ comes from having multiplied the 2 in $C$ by 2 — there is a carry of 1 from the digit greater than 4 to the right of 2; the 4 in $D$ comes from the 7 in $C$ because there is no carry involved. What is important here is that the even digits in $D$ come from the digits of $C$ with a number less than 5 on the right, while the odd digits in $D$ come from the digits of $C$ with a number 5 or greater on the right. It turns out that there are 12 arrangements of the digits $1,2,4,5,7,8$ into candidates for $C$ for which $2C$ is a permutation of those digits. In each such arrangement, 2, 8, and 5 have a digit 5 or greater on the right, so their double produces an odd digit of $2C$. For another example, note that the digits 1 through 8 can be arranged into $8$-digit numbers whose digits are permuted by multiplication by 2; $E = 42715638$ is such an example. We return now to our March problem.

Suppose that the 16 given digits can be arranged into numbers $A$ and $B$ for which $B=2A$. Denote by $a_n$ and $b_n$ the number of times the digit $n$ appears in the numbers $A$ and $B$, respectively. Then for each of the eight different values of $n$ we have

Because 2 times the digit 5 in $A$ would produce either a 1 or 0 in $B$ (according as there is or is not a carry), both of the 5's must appear in $B$:

Similarly, because any 2 or 3 in $B$ would necessarily come from a 6 in $A$, we have $a_6 = b_2 + b_3$. Adding $b_5+b_6$ to both sides of this equation yields (with the help of (1) and (2))
$$b_5+(b_6+a_6) = 4 = b_2 +b_3+b_5+b_6,$$
whence (because $B$ consists of eight digits)

Because any digits 8 or 9 in $B$ would come from 4 or 9 in $A$, we have $a_4+a_9 = b_8+b_9$, whence (adding $b_4$ to both sides and invoking (3))
\begin{eqnarray*}
2+a_9 &=& b_4+b_8+b_9\\
&=& 4-b_7 = 4-(2-a_7) = 2+a_7.
\end{eqnarray*}
Thus,

observing the correspondence between digits greater than 4 in $A$ and odd digits in $B$, we have
$$a_6+a_7+a_8+a_9 = b_3+b_5+b_7+b_9.$$
From (1), (2), and (4) this equation becomes
$$8-b_6-2b_7-b_8 = b_3+2+2b_7,$$
whence

We deduce immediately from (5) that $b_7 \ne 2$. Nor can $b_7$ equal 0: otherwise (2) and (5) would imply that $b_3=b_6=b_8=b_5 = 2$, which in turn implies that both $a_2$ and $a_7$ would have to be 2, so that $b_4$ and $b_5$ would have to be 2, which would force five of the $b$'s to be 2, a contradiction. The remaining possibility is that $a_7=b_7=a_9=b_9=1$. But this also leads to a contradiction: Equation (5) then becomes
$$b_3+b_8 = 2-b_6.$$
Because any digits 6 and 7 in $B$ come from 3 and 8 in $A$, $b_6+b_7 = a_3+a_8$. Setting $b_7=1$ we get
$$b_6 + 1 = 4-(b_3+b_8) = 4- (2-b_6) = 2+b_6,$$
which is a contradiction. We conclude that there can be no such $A$ and $B$.