¿Sabía que…

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

13 Comentarios

  1. Salen muchos “Invalid Equation” en el post, ¿os pasa a vosotros?

    Publica una respuesta
  2. Fascinante… pero no la entiendo.
    Concretamente ¿cómo se está usando (y porqué) A(x) y B(x)?
    Gracias y saludos.

    Publica una respuesta
  3. josejuan: A(x) y B(x) son las series generatrices (¿se dice asi? en inglés es “generating series”) de las sucesiones de elementos de A y B. En teoría analítica de números es muy habitual usar este método para convertir sucesiones en series. Estas series son “series formales”, la x no representa ningún número, así que no se necesita verificar condiciones de convergencia.

    Publica una respuesta
  4. Gracias “vengoroso”, realmente interesante.

    Leyendo sobre “Función generadora” aparece lo que tú comentas, sin embargo, deberé de suponer que las usadas en la demostración no son “funciones generadoras ordinarias” (las que he podido leer así por encima) puesto que los elementos de la sucesión se usan en las potencias (y no en los coeficientes) y que pueden definirse cualesquiera “función generadora”.

    :O oohhhhhh!

    Me quedo pasmado del uso de este tipo de funciones (había visto algunas como las generatrices de momentos en estadística pero no desde este punto de generalización).

    Realmente es muy ingenioso este uso para el tema de combinatoria (en este caso, para “contar” el número de combinaciones) y ahora se entiende perfectamente el resto de la demostración.

    Felicidades, me quedo maravillado de lo sencillo y poderoso de la demostración.

    Publica una respuesta
  5. Uhm… realmente interesante, en el post se busca las N formas de obtener un número sumando dos diferentes, podría haber sido, por ejemplo, sumando 2a+b con a y b diferentes, entonces usaríamos
    $G(x^{2})G(x)-G(x^{3})$
    para tener en el sumando
    $Nx^{M}$
    las N formas de obtener M como suma de un número y doble de otro (diferentes ambos).

    La combinatoria siempre me ha parecido una de las ramas más difíciles, agrada ver cosas como ésta. 😉

    Publica una respuesta
  6. (uhm… vale, estoy pegando ‘platex’ y no ‘latex’ [uso Scientific Notebook] ¿qué editor usáis? ¿MiKTeX?)

    Publica una respuesta
  7. josejuan Son funciones generadoras (gracias!) ordinarias, pero la sucesion asociada a los conjuntos no es el propio conjunto sino su funcion caracteristica. Para un conjunto X de naturales su funcion caracteristica es una sucesion cuyo elemento x_n es 1 si n pertenece a X o 0 en otro caso. Al calcular la funcion generadora de esta sucesion se obtiene la que se usa en la demostracion.

    PS: ^DiAmOnD^ cualquier expresion latex en los comentarios que use un simbolo distinto de letras y numeros me produce un error. Le ha pasado algo al plugin?

    Publica una respuesta
  8. Uhmmm…raro raro. A mí no me aparece ningún error, pero ya sois demasiados los que comentáis algo sobre problemas con las fórmulas. Quizás Codecogs está fallando a ratos. ¿Os siguen apareciendo errores? Si es así comentadlos con la mayor cantidad de detalles posible.

    Publica una respuesta
  9. “gaussianos”, parece ser que durante un periodo de tiempo el parser no estaba funcionando adecuadamente. Muchas de las fórmulas que yo he pegado en este post NO estaban saliendo correctamente, sin embargo, ahora SI salen correctamente.

    Mi hipótesis es que el servicio de “www.codecogs.com” (que es el usáis aquí para mostrar latex) no estaba funcionando como debía y posteriormente lo han solucionado.

    Yo es que me estaba volviendo loco. Como ha dado la casualidad que me ha dado por empezar a pegar código latex y me daba errores, lógicamente pensé que era error mío y no veía la forma de corregirme.

    En cualquier caso, yo ahora veo todas las fórmulas correctamente.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: …existe una partición muy curiosa de los números no negativos en dos conjuntos en…
  2. Twitter Trackbacks for ¿Sabía que… | Gaussianos [gaussianos.com] on Topsy.com - [...] ¿Sabía que… | Gaussianos gaussianos.com/representacion-de-un-numero-no-negativo-como-suma-de-dos-elementos-de-dos-conjuntos – view page – cached …existe una partición muy curiosa de los…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *