existe una partición muy curiosa de los números no negativos en dos conjuntos en relación con la representación de un número como suma de dos elementos de cada uno de ellos?

Ayer mismo nuestro admirado fede me envió una demostración sobre un hecho muy curioso y he decidido publicarla. La cuestión es la siguiente:

Sea X el subconjunto de los enteros no-negativos que tienen un numero par de unos en binario y sea Y el de los que tienen un número impar de unos en binario, es decir:

X = \{ 0, 3, 5, 6, 9, 10, \ldots \} \quad Y = \{ 1, 2, 4, 7, 8, 11, \ldots \}

Entonces se cumple la siguiente propiedad:

El número de representaciones de cualquier no-negativo N como suma de dos elementos distintos de X es el mismo que el número de representaciones de N como suma de dos elementos distintos de Y.

Además \{ X,Y \} es la única partición de los no-negativos que tiene esa propiedad.

Vamos a ver la demostración de este hecho.

Demostración

Sea P(A,B) la propiedad:

\lbrace A,B \rbrace es una partición de los no-negativos y el número de representaciones de cualquier no-negativo N como suma de dos elementos distintos de A es el mismo que el número de representaciones de N como suma de dos elementos distintos de B.

Sean A = \{ a_0, a_1, a_2, \ldots \}, B = \{ b_0, b_1, b_2, \ldots \}, A(x) = x^{a_0} + x^{a_1} + x^{a_2} + \ldots y B(x) = x^{b_0} + x^{b_1} + x^{b_2} + \ldots.

Entonces la propiedad P(A,B) anterior es equivalente a la igualdad:

(A(x))^2 - A(x^2) = (B(x))^2 - B(x^2)

Es decir:

(A(x))^2 - (B(x))^2 = A(x^2) - B(x^2)

ya que el coeficiente de x^n en (A(x))^2 - A(x^2) es el número de representaciones de n como suma de dos elementos diferentes de A.

Como \lbrace A,B \rbrace es una partición de los no negativos:

A(x) + B(x) = 1 + x + x^2 + x^3 + \ldots = \cfrac{1}{1-x}

Sea X el subconjunto de los enteros no-negativos que tienen un numero par de unos en binario y sea Y el de los que tienen un número impar de unos en binario. Esto es:

X = \{ 0, 3, 5, 6, 9, 10, \ldots \} \quad  Y = \{ 1, 2, 4, 7, 8, 11, \ldots \}

Demostramos primero que se cumple la propiedad P(X,Y):

Si A=X yB=Y:

(1-x)(1-x^2)(1-x^4) \cdots (1-x^{2^i}) \cdots = A(x) - B(x)

y entonces:

(A(x))^2 - (B(x))^2 = [A(x) + B(x)][A(x) - B(x)] =

=(1-x^2)(1-x^4) \cdots (1-x^{2^i}) \cdots=

=A(x^2) - B(x^2)

y por tanto se cumple la propiedad P.

Y ahora demostramos que \{X,Y\} es la única partición de los no-negativos que cumple esa propiedad.

Si se cumple P tenemos que:

(A(x))^2 - (B(x))^2 =  [A(x) + B(x)][ A(x) - B(x)] = A(x^2) - B(x^2)

Es decir:

A(x) - B(x) = (1-x) [A(x^2) - B(x^2)] = (1-x)(1-x^2)[A(x^4) - B(x^4)] =

=(1-x)(1-x^2)(1-x^4) \cdots (1-x^{2^i}) \cdots

Y en la serie de potencias resultante de la multiplicación los términos con signo positivo serán los de A(x) y los términos con signo negativo los de B(x). Pero el signo de un término x^n es positivo o negativo según sea n suma de un número par o impar de potencias distintas de 2, y por tanto A=X y B=Y.


Los resultados anteriores fueron demostrados en 1959 por Leo Moser y Joe Lambek.

Print Friendly, PDF & Email