1. Educación

Edición digital para la Biblioteca Digital del ILCE
Título original: Sequences of Plus and Minus
© De la traducción: Emilio Méndez Pinto
Publicado originalmente en inglés como: “Sequences of Plus and Minus”,
Paul Erdös e Irving Kaplansky, Scripta Mathematica, 12, pp. 73-75.
Derechos reservados. 1946. Scripta Mathematica.
Prohibida su reproducción por cualquier medio mecánico o
eléctrico sin la autorización por escrito de los coeditores.
2
Supongamos que n unos y un igual número de menos unos están dispuestos en
una serie. En total hay
2n
C n arreglos posibles. Por ejemplo, cuando n = 2 , son posibles
los siguientes 6(= 4 C 2 ) arreglos:
1 + 1 −1 −1
−1+1+1−1
1 −1 + 1 −1
−1+1−1+1
1 −1 −1 + 1
−1 −1 + 1+ 1
La suma de cualquiera de estas series es, desde luego, 0. Una suma parcial, formada al
romper una serie en un punto, puede ser positiva o negativa; en cualquier caso, se
encuentra entre n y − n . En conexión con una investigación realizada por uno de los
autores [de este artículo] surgió la siguiente pregunta: ¿en cuántos de los arreglos son
todas las sumas parciales no negativas?
De los 6 arreglos de arriba, dos (los primeros dos) son aceptables. De igual
forma, de los 20 arreglos para n = 3 , los siguientes 5 son aceptables:
1 + 1 + 1 −1 −1 −1
1 + 1 −1 + 1 −1 −1
1 + 1 −1 −1 + 1 −1
1 −1 + 1 + 1 −1 −1
1 −1 + 1 −1 + 1 −1
y de los 70 arreglos para n = 4 , uno puede verificar que 14 son buenos. Ahora es fácil
conjeturar la fórmula correcta: en general,
Cn
de los
(n + 1)
2n
2n
C n arreglos satisfacen la
condición.
Es curioso que, con el fin de probar esta conjetura, parece ser conveniente
generalizar como sigue: haya m unos y n menos unos, y requiérase que todas las sumas
parciales sean, al menos, m − n . Denotemos por f (m, n) el número de arreglos que
satisfacen esta condición. Si m > n + 1 , es evidente desde ya que la primera suma parcial
no puede satisfacer la condición, porque no puede ser mayor que 1. Así,
f ( m, n ) = 0
(m > n + 1) .
(1)
3
Si m = n o n + 1 , tendremos que comenzar la serie con 1. Entonces nos quedan
m − 1 unos y n menos unos, y las sumas parciales son ahora mayores que m − n − 1 . Por
lo tanto,
( m = n o n +1 )
f (m, n) = f (m − 1, n)
(2)
Por último, si m < n , tenemos derecho a comenzar con 1 o con − 1 , y
similarmente encontramos que
f (m, n) = f (m − 1, n) + f (m, n − 1)
( m < n)
(3)
Uno puede fácilmente verificar inductivamente que la solución de las ecuaciones
(1), (2), (3), con las condiciones límite f (1,0) = f (0, n) = 1 , está dada por (1), (4), y (5):
f (m, n) =
n − m +1
m+ n Cm
n +1
f (n + 1, n) =
( m < n)
Cn
(n + 1)
2n
(4)
(5)
Tomando m = n en (4) obtenemos, de manera particular, el resultado
conjeturado anteriormente.
Este problema puede presentarse en un tablero de ajedrez. Consideremos un
tablero unidimensional extendiéndose hacia la derecha hasta el infinito y limitado hacia
la izquierda, y coloquemos un rey en el extremo izquierdo. Entonces f (n, n) es el
número de formas en que el rey se mueve 2n veces para regresar a su punto de partida.
El problema correspondiente para un tablero bidimensional parece ser muy difícil si
permitimos que el rey se mueva diagonalmente; sin embargo, si lo restringimos a
movimientos horizontales y verticales, la respuesta es [ f (n, n)]2 .
Otro problema sugerido consiste en colocar al rey en la mitad del tablero y
preguntarse por el número de formas en que puede hacer un viaje a otro cuadrado
designado. En el caso unidimensional esto está convenientemente formulado como
sigue: ¿de cuántas formas pueden ser arreglados m unos y n menos unos de modo que
4
todas las sumas parciales sean, al menos, m − n − a ? Si permitimos que el número
deseado sea g (m, n, a ) , entonces g (m, n,0) = f (m, n) , y para a < 0 tenemos que
g (m, n, a ) = 0 , porque la suma final no puede ser mayor que m − n . Podemos obtener
una fórmula de recurrencia al dividir los arreglos aceptables en dos subconjuntos:
aquellos que terminan en 1 y aquellos que terminan en − 1 . En el primer caso nos
quedamos con m − 1 unos y n menos unos a ser arreglados con sumas parciales de al
menos m − n − a , y hay g (m − 1, n, a − 1) arreglos así. Similarmente hay g (m, n − 1, a + 1)
en el último grupo, por lo que tenemos
g (m, n, a ) = g (m − 1, n, a − 1) + g (m, n − 1, a + 1) .
Estableciendo a = 0,1,2 en sucesión, encontramos que
g (m, n,1) = f (m, n + 1)
g (m, n,2) = f (m, n + 2) − f (m − 1, n + 1)
g (m, n,3) = f (m, n + 3) − 2 f (m − 1, n + 2)
y la fórmula general es
g (m, n, a ) =
[ a / 2]
∑ (−1)
i =0
i
a −i
C1 f (m − i, n + a − i ) .
UNIVERSIDAD DE STANFORD
UNIVERSIDAD DE CHICAGO
5