Solution for November 2012

The Problem:

Let $w$ be any $n$-letter "word", where by word we just mean a collection of letters written together — it does not have to be a word in any known language. Prove that if $w$ contains at most 10 different letters, such as monthlyproblm, then you can replace the letters of $w$ by decimal digits (different letters replaced by different digits, same letters by same digit) so that the resulting $n$-digit number is a multiple of 3. For example, if we let $m=1, \; o = 2$, and so on, we get the number 1234567892061, which is a multiple of 3. Give an example of a word containing at most 10 different letters that is not a multiple of 7 by any assignment of the 10 decimal digits to its letters (again, different letters replaced by different digits, same letters by same digit)

The solution:

Solution to part (a)
Because the number we create from $w$ is a decimal number, it will be a multiple of 3 when the sum of its digits is divisible by 3. We are therefore concerned here with how many times a letter occurs in the word, not where it occurs. We can further simplify the problem by observing that any letter $x$ that appears three times contributes $3x$ the total, so no matter what value we assign to $x$, that portion of the total will be divisible by 3. Thus, without loss of generality we may assume that either a letter appears a single time and we place it in a set $S$, or it appears exactly twice and we place the letter in the set $T$. An example will make the procedure clear.

Example. Let $w$ be the word $aaabbbbbbbcdeeeeeff$. Since $a$ appears three times, we can put it aside; $b$ appearing $7 = 2\cdot3 + 1$ times will be placed in $S$, as will $c$ and $d$ (and the first six appearances of $b$ are set aside); $e$ appears 5 times, so we set aside the first three and place $e$ in $T$ along with f. The simplified word is now $bcdeeff$. That is, $S = \{b,c,d\}$ and $T = \{e, f\}$.

Should $S$ contain two or more letters, we choose two of them and assign one the digit 1, the other the digit 2. Should two or more letters of $S$ remain unassigned, we continue assigning pairs the digits 4 and 5, then 7 and 8. (Note that $1+2, 4+5$, and $7+8$ are all divisible by 3.) If we are left with fewer than two letters in $S$ before using all those digits, we apply the same process to $T$. (That is, we assign pairs of distinct letters in $T$ any unused pairs of digits from the pairs 1 and 2, then 4 and 5, then 7 and 8.) Because there are at most ten different letters to start with, there can be at most four letters in $S \cup T$ that have not been assigned a digit by this process; these can be assigned the digits 0, 3, 6, and 9, all of which are divisible by 3 no matter how many times they occur (although, of course, we should avoid assigning 0 to the letter that appeared first in the original word $w$). Finally, any letter of $w$ that is not in $S$ or $T$ will have a multiplicity that is divisible by 3, so that it can be assigned any digit that remains.

Example continued. The procedure tells us to set $b=1, c=2, e=4, f=5, d=0$, and $a=3$. Thus $w$ is assigned the number $3331111111204444455$, the sum of whose digits is
$$(3\cdot3) + (7\cdot 1) + 2 + 0 + (5\cdot 4) + (2\cdot 5) = 48\;,$$
which is divisible by 3 (and, therefore, so is $w$).

Solution to part (b).
The rule for divisibility of a decimal number by 7 is not so easy — the order in which the digits appear is important. The key to our solution is to observe that the powers of 10 (namely, $10^0, 10^1, 10^2, \dots$) are congruent modulo 7, respectively, to
$$1,3,2,6,4,5,1,3,2, \dots,$$
which forms a sequence that repeats with period 6. Our goal is to devise a word using exactly 10 different letters arranged so that no matter how the digits are assigned, the resulting number is always congruent to 2 modulo 7 (which means that division of the number by 7 always leaves a remainder of 2). Most solvers used the same strategy; Fang, Jakobsson, Lim, and Vause devised similar examples containing 17 letters, which tied for the shortest among all submissions. The word both Jakobsson and Lim proposed is aabcbdeefgfdhhiji (or, if you prefer, eels luvv go Gucci, Di, which, according to Jakobsson, is what Prince Charles said to Lady Diana when she told him not to buy his pet eel a new handbag — it does indeed sound like something Charles would say). We must show that for any assignment of digits to the corresponding letters, the number corresponding to $w$, namely
\begin{eqnarray*}
S &=&10^{16} a \;+\; 10^{15}a +10^{14}b \;+\; 10^{13}c \;+\;10^{12}b \;+\;10^{11}d \;+\;10^{10}e\\
& &\hspace{11mm} \;+\;10^{9}e \;+\;10^{8}f
+\;10^{7}g \;+\;10^{6}f \;+\;10^{5}d \;+\;10^{4}h \;+\;10^{3}h\\
& &\hspace{11mm} \;+\;10^{2}i \;+\;10^{1}j \;+\;10^0i\\
&\equiv& 4a+6a+2b+3c+1b+5d+4e+6e+2f+3g+1f+5d+4h\\
& &\hspace{14mm}+6h+2i+3j+1i\\
&=& 10a + 3b + 3c + 10d + 10e + 3f + 3g + 10h + 3i + 3 j\\
&\equiv& 3(a+b+c+d+e+f+g+h+i+j) \pmod 7,
\end{eqnarray*}
is not congruent to 0 (mod 7). But the ten letters represent some permutation of the decimal digits, so $a+b+c+d+e+f+g+h+i+j = 45$, whence $S = 3\cdot 45 \equiv 3 \cdot 3 \equiv 2 \pmod 7$. We conclude that no assignment of digits to the letters of aabcbdeefgfdhhiji could produce a number divisible by 7.

Alternative solution to (b). The solution submitted by Humbert used a different strategy — one that generalizes easily. Because $10^6 \equiv 1$ (mod 7), we devise a word $w$ whose letters come in blocks of six:
$$a\;aaaaaa\;baaaaa\;caaaaa\;daaaaa\;eaaaaa\;faaaaa\;gaaaaa\;haaaaa\;iaaaaa\;jaaaaa.$$
When digits are substituted for letters, each block looks like

\begin{eqnarray*}
10^{6k}\left(10^5x + 10^4a + 10^3a + 10^2a + 10a + a\right) & &\equiv 5x+4a+6a+2a+3a+a \\
& & \equiv
5x + 2a \pmod7,
\end{eqnarray*}
for some $k \ge 0$. Because of the extra letter $a$ at the start, $w$ becomes equivalent modulo 7 to
$$(10\cdot 2 + 1)a + 5(a+b+c+d+e+f+g+h+i+j) \equiv 0\cdot a + 5\cdot 3 \equiv 1 \pmod7 ,$$
whence $w$ could never have a numerical value divisible by 7.

Comments. Part (a) is problem 1859 from the problem journal Crux Mathematicorum (20:6, June 1994, pages 168-170), proposed by N. Kildonan. The published solution mentioned our part (b) as an additional challenge. Part (b) was used as Macalester's Problem of the Week #1093 (in February 2008). See their web page (http://mathforum.org/wagon/about.html) for further information. Robert Israel and Stan Wagon produced a theorem that deals with an interesting generalization of the problem. They define a positive integer $d$ to be attainable if every sufficiently long word composed of some or all of the ten letters from $a$ to $j$ can, by some substitution of distinct digits for letters, be turned into a decimal integer that is divisible by $d$. In this month's problem, for example, we showed that $d=3$ is attainable while $d=7$ is not.

Theorem (Israel and Wagon). The attainable integers consist of all the divisors of 18, 24, 45, 50, 60, or 80.

See their paper "Alphanumeric Divisibility" for a discussion of the problem and its proof:
http://stanwagon.com/public/AlphanumericPuzzlePaper.pdf