Solución del problema de Noviembre, 2012

El problema:

Sea $w$ una "palabra'' de $n$ letras, donde palabra significa simplemente una colección de letras una al lado de la otra en algún orden (no tiene que ser una palabra de algún idioma conocido). Probar que si $w$ está formada por 10 o menos letras distintas (con repeticiones permitidas) entonces se pueden remplazar las letras de $w$ con dígitos (a igual letra igual dígito, distintas letras corresponden a distintos dígitos) de manera que el número resultante es múltiplo de 3. Dar un ejemplo de una palabra que contiene 10 o menos letras distintas tal que no es múltiplo de 7 bajo ningún remplazo de las letras por dígitos de la manera descripta arriba.

Respuestas correctas:
	Recibimos soluciones correctas de Lamis Alsheikh (Syria) Aleksandar Blazhevski (Macedonia) Mei-Hui Fang (Austria) Federico Foieri (Argentina) Tony Harrison (England) Benoît Humbert (Francia) Magnus Jakobsson (Suecia) Matthew Lim (USA) Patrick J. LoPresti (USA) Albert Stadler (Suiza) Bruno Tisserand (Francia) Arthur Vause (UK) David K.M. Yang (USA)

La solución:

Solución de la parte (a).
Como el número que creamos a partir de $w$ es decimal, será múltiplo de 3 si la suma de sus dÌgitos es divisible por 3. Esto implica que solamente nos importa la cantidad de veces que aparece una letra, pero no su ubicación. Podemos también simplificar el problema notando que cualquier letra $X$ que aparezca 3 veces contribuye $3x$ al total, de manera que no afecta si el número es divisible por 3. En resumen, podemos suponer que cada letra aparece una vez, en cuyo caso la colocamos en un conjunto $S$, o aparece dos veces y la colocamos en un conjunto $T$. Veamos un ejemplo.

Ejemplo. Sea $w=aaabbbbbbbcdeeeeeff$. Como $a$ aparece 3 veces, la podemos dejar de lado; $b$ aparece $7 = 2\cdot3 + 1$ veces y entonces la colocamos en $S$, como a $c$ y $d$; $e$ aparece 5 veces, por lo que dejamos de lado las primeras 3 y ponemos a $e$ en $T$ junto con $f$. La palabra simplificada es $bcdeeff$, y tenemos $S = \{b,c,d\}$, $T = \{e, f\}$.

Si $S$ contiene dos o más letras, elegimos dos de ellas y les asignamos a una el dÌgito 1 y a la otra el dÌgito 2. Si aún quedan letras en $S$, elegimos dos de ellas y les asignamos 4 y 5, y luego 7 y 8 (notemos que $1+2$, $4+5$, $7+8$ son múltiplos de 3. Si en algún momento nos queda un solo dÌgito en $S$, aplicamos el proceso anterior a $T$. Como habÌa a lo sumo 10 letras diferentes, puede haber a lo sumo 4 letras en $S$ y $T$ que no fueron asignadas; a éstas les podemos asignar 0, 3, 6, 9 que son múltiplos de 3. Cualquier letra de $w$ que no esté en $S$ ó $T$ aparece con multiplicidad divisible por 3, por lo que puede asignársele los dÌgitos restantes.

Ejemplo: continuación. El proceso anterior nos sugiere asignar $b=1, c=2, e=4, f=5, d=0$, $a=3$. Entonces $w$ es asignada al número $3331111111204444455$, cuyos dÌgitos suman
$$(3\cdot3) + (7\cdot 1) + 2 + 0 + (5\cdot 4) + (2\cdot 5) = 48\;,$$
que es divisible por 3 (de menera que también lo es $w$).

Solución de la parte (b).
La regla de divisibilidad de un número decimal por 7 no es tan sencilla
— el orden en que aparecen los dÌgitos es importante. La clave es notar que las potencias de 10 (es decir $10^0, 10^1, 10^2, \dots$) son congruentes módulo modulo 7 a
$$1,3,2,6,4,5,1,3,2, \dots,$$
respectivamente. La observación es que esta sucesión tiene perÌodo 6. Nuestro objetivo es crear una palabra usando exactamente 10 letras distintas de tal manera que, de cualquier manera que sean asignados los dÌgitos, el número resultante siempre será congruente con 2 módulo 7. Esta estrategia fue mayoritaria. Fang, Jakobsson, Lim, Vause crearon ejemplos similares con 17 letras, que fue lo más corto que apareció en las respuestas. La palabra de
Jakobsson y Lim es {\em aabcbdeefgfdhhiji}. Debemos mostrar que cualquier elección de dÌgitos para tales letras hace que el número $w$, es decir
\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*}
no es congruente con 0 (mod 7). Pero las 10 letras representan alguna permutación de los 10 dÌgitos, por lo que $a+b+c+d+e+f+g+h+i+j = 45$, y por tanto $S = 3\cdot 45 \equiv 3 \cdot 3 \equiv 2 \pmod 7$. ConcluÌmos que es imposible que $aabcbdeefgfdhhiji$ sea múltiplo de 7.

Solución alternativa para (b). La solución de Humbert utiliza una estrategia diferente — que se generaliza fácilmente. Como $10^6 \equiv 1$ (mod 7), creamos una palabra $w$ cuyas letras vienen en bloques de seis:
$$a\;aaaaaa\;baaaaa\;caaaaa\;daaaaa\;eaaaaa\;faaaaa\;gaaaaa\;haaaaa\;iaaaaa\;jaaaaa.$$
Cuando sustituÌmos dÌgitos por letras, cada bloque queda
\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*}
para algún $k \ge 0$. Por la letra $a$ extra al
comienzo, $w$ queda equivalente, módulo 7, a
$$(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 ,$$
por lo que $w$ nunca puede tener un valor numérico divisible por 7.

Comentarios. Parte (a) es el problema 1859 de la revista Crux Mathematicorum (20:6, June 1994, pages 168-170), propuesto por N. Kildonan. La solución publicada menciona la parte (b) como un desafÌo adicional. La parte (b) fue utilizada en el Macalester's Problem of the Week #1093 (Febrero 2008, http://mathforum.org/wagon/about.html). Robert Israel y Stan Wagon probaron un teorema que es una interesante generalizacaión del problema. Definen un entero positivo $d$ como alcanzable si toda palabra suficientemente larga compuesta por las 10 letras de la $a$ hasta la $j$ puede, por sustitución de las letras por dÌgitos, ser convertida en un entero decimal divisible por $d$. En el problema de este mes probamos que $d=3$ es alcanzable, y que $d=7$ no lo es.

Teorema (Israel and Wagon). Los enteros alcanzables son los divisores de 18, 24, 45, 50, 60, y 80.

El Teorema y su demostración se hallan en el trabajo "Alphanumeric Divisibility":
http://stanwagon.com/public/AlphanumericPuzzlePaper.pdf