¿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$ y $B=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.

Meneame
Bitacoras
Facebook
Twitter

Posts aleatorios
En ocasiones veo 3'14…
Alicia y el país de las matemáticas: una maravillosa relación
Premio Abel
Busca Problemas: el buscador de acertijos
Mejorando Gaussianos

Autor: ^DiAmOnD^ | Publicado el 17 de December de 2009
Envia este post a Twitter
Categorías: ¿Sabía que ...? | Imprime este post

Sin comentarios

Trackback | 17 Dec, 2009

Bitacoras.com
coper | 17 de December de 2009 | 10:12

Salen muchos “Invalid Equation” en el post, ¿os pasa a vosotros?
^DiAmOnD^ | 17 de December de 2009 | 10:50

A mí no me sale ninguno. Qué raro.
josejuan | 17 de December de 2009 | 10:55

Fascinante… pero no la entiendo.
Concretamente ¿cómo se está usando (y porqué) A(x) y B(x)?
Gracias y saludos.
cdrman | 17 de December de 2009 | 11:07

A mí tampoco me sale ningún error.
Trackback | 17 Dec, 2009

Twitter Trackbacks for ¿Sabía que… | Gaussianos [gaussianos.com] on Topsy.com
Juan Carlos | 17 de December de 2009 | 13:19

A mi tambien me salen millones de INVALID EQUATION, no se puede leer el articulo…
vengoroso | 17 de December de 2009 | 13:30

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.
josejuan | 17 de December de 2009 | 13:56

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.
josejuan | 17 de December de 2009 | 14:14

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.
josejuan | 17 de December de 2009 | 14:32

(perdón por el borrón)
entonces usaríamos
$G(x^{2})G(x)-G(x^{3})$
para tener en el sumando
$Nx^{M}$
josejuan | 17 de December de 2009 | 14:34

(uhm… vale, estoy pegando ‘platex’ y no ‘latex’ [uso Scientific Notebook] ¿qué editor usáis? ¿MiKTeX?)
vengoroso | 17 de December de 2009 | 15:46

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?
gaussianos | 18 de December de 2009 | 05:24

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.
josejuan | 18 de December de 2009 | 10:57

“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.