Un problema del dinamarqués "Georg Mohr Konkurrencen en I Matematik 1996" fue generalizado por Pierre Bornsztein [CRUX MATHEMATICORUM 2001, página 240]. El demostró que si (a) P es una permutación del conjunto {1, 2, ..., n}, y (b) n es congruente con 2 o 3 módulo 4, entonces los números |k - P(k)| no pueden ser distintos. Nuestro problema de agosto es saber que pasa cuando n = 20:
Hay alguna permutación P para la cual los números |k - P(k)| toman todos los
valores desde el 0 hasta el 19?
Recibimos este mes soluciones correctas de Juan Mir Pieras (de España) y gordon Robison (de Victoria, British columbia). No solo Mir contestó la pregunta para n = 20, sino que mandó una construcción para toda n congruente con 0 y 1 módulo 4. Robinson incluyó con su respuesta una prueba del resultado de Bornsztein que no puede haber tal permutación cuando n es congruente con 2 o 3 módulo 4.
Mir solutionVoy a demostrar constructivamente que, para el caso en que n sea congruente a 0 ó 1 módulo 4, sí existen permutaciones P(k) del conjunto {1, 2, ..., n}que cumplan que todos los D(k) = |k - P(k)| son diferentes.
- Para el caso n=4m hay al menos una solución:
| P(k) = 4m+1-k | para 1 <= k <= m | (I) |
| P(k) = m+1 | para k = m+1 | (II) |
| P(k) = 4m+2-k | para m+1 < k <= 2m | (III) |
| P(k) = 4m+1-k | para 2m < k < 3m | (IV) |
| P(k) = 4m-k | para 3m £ k < 4m | (V) |
| P(k) = 2m+1 | para k = 4m | (VI) |
Es fácil ver que para el intervalo II tenemos D=0, entre el III y el IV tenemos todos los valores pares e impares respectivamente de 1 £ D < 2m-1, en el VI D=2m-1, y todos los valores de 2m £ D < 4m divididos en pares e impares en el V y el I respectivamente.
Por ejemplo, para n=20
20 19 18 17 16 6 15 14 13 12 10 9 8 7 5 4 3 2 1 11
las diferencias son
19 17 15 13 11 0 8 6 4 2 1 3 5 7 10 12 14 16 18 9
- Para el caso n=4m+1, hay también al menos una solución, muy parecida a la anterior:
| P(k) = 4m+1-k | para 1 <= k <= m |
| P(k) = m+1 | para k = m+1 |
| P(k) = 4m+2-k | para m+1 < k <= 2m + 1 |
| P(k) = 4m+1-k | para 2m < k <= 3m |
| P(k) = 4m-k | para 3m < k <= 4m |
| P(k) = 2m+1 | para k = 4m + 1 |
Por ejemplo, para n=21
21 20 19 18 17 6 16 15 14 13 12 10 9 8 7 5 4 3 2 1 11
las diferencias son
20 18 16 14 12 0 9 7 5 3 1 2 4 6 8 11 13 15 17 19 10
De todas maneras esas no son las únicas permutaciones que cumplen las condiciones del problema. Para empezar, hay dos simetrías. Veamos. Si colocamos en un damero de dimensiones n por n, una ficha por cada pareja (k, P(k)), las condiciones del problema se limitan a que ninguna ficha comparta fila k ni columna P(k) (como si fueran torres de ajedrez), y que ninguna ficha esté a la misma distancia de la diagonal k=P(k) que otra. Esta condición sobre el damero presenta dos ejes de simetría: las dos diagonales del damero. A partir de este razonamiento, podemos decir que: Si P(k) cumple las condiciones del problema, también las cumplen
P-1(k)
n+1-P-1(n+1-k)
De hecho el número de soluciones "diferentes" (sin contar las simetrías, es decir, dividiendo por cuatro) crece muy rápidamente con los primeros valores de m, tanto para n=4m como para n=4m+1:
| n = 4 | 1 solución | |
| n = 8 | 8 soluciones | |
| n = 12 | 248 soluciones | |
| n = 16 | 12628 soluciones | |
| n = 5 | 1 solución | |
| n = 9 | 24 soluciones | |
| n = 13 | 628 soluciones | |
| n = 17 | 36036 soluciones |
Finalmente este mes, para la conveniencia de los lectores sin acceso a Crux Mathematicorum with Mathematical Mayhem reproduciremos el argumento de Pierre Bornsztein de Mayo del 2001 (Volumen 27:4) página 240 que tal permutación no existe cuando n es congruente con 2 o 3 módulo 4. Mas precisamente, él asume que
p es una permutación de {1,...,n} y |p(k) - k| es una permutación de {0,...,n-1}, y entonces demuestra que n debe ser congruente con 0 o 1 módulo 4. Nuestra condición en p implica que S(p(k) - k) = 0 y
Aún mas, ya que |j| - j deber ser par para todos los enteros j, para algún entero d tenemos
Comparando (1) y (2), obtenemos n(n-1) = 4d, lo cual implica que n es congruente con 0 o 1 módulo 4 como se afirmaba. Gordon Robinson dió un argumento similar; así es como él explica la conclusión: Si n es congruente con 2 o 3 mod 4, la suma 0 + 1 + 2...+ n-1 es un número impar, así que ninguna asignación de símbolos a los brincos de k a p(k) puede dividir parejo las subidas y bajadas de tal forma que la suma sería cero.
Crux with Mayhem, una revista publicada por la Sociedad Matemática Canadiense, es una fuente rica de problemas interesantes. Para mayor información, vea http://journals.cms.math.ca/CRUX/