…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
el subconjunto de los enteros no-negativos que tienen un numero par de unos en binario y sea
el de los que tienen un número impar de unos en binario, es decir:
Entonces se cumple la siguiente propiedad:
El número de representaciones de cualquier no-negativo como suma de dos elementos distintos de
es el mismo que el número de representaciones de
como suma de dos elementos distintos de
.
Además
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 la propiedad:
es una partición de los no-negativos y el número de representaciones de cualquier no-negativo
como suma de dos elementos distintos de
es el mismo que el número de representaciones de
como suma de dos elementos distintos de
.
Sean ,
,
y
.
Entonces la propiedad anterior es equivalente a la igualdad:
Es decir:
ya que el coeficiente de en
es el número de representaciones de
como suma de dos elementos diferentes de
.
Como es una partición de los no negativos:
Sea el subconjunto de los enteros no-negativos que tienen un numero par de unos en binario y sea
el de los que tienen un número impar de unos en binario. Esto es:
Demostramos primero que se cumple la propiedad :
Si
y
:
y entonces:
y por tanto se cumple la propiedad
.
Y ahora demostramos que
es la única partición de los no-negativos que cumple esa propiedad.
Si se cumple
tenemos que:
Es decir:
Y en la serie de potencias resultante de la multiplicación los términos con signo positivo serán los de
y los términos con signo negativo los de
. Pero el signo de un término
es positivo o negativo según sea
suma de un número par o impar de potencias distintas de 2, y por tanto
y
.
Los resultados anteriores fueron demostrados en 1959 por Leo Moser y Joe Lambek.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: …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ó un…
Salen muchos «Invalid Equation» en el post, ¿os pasa a vosotros?
A mí no me sale ninguno. Qué raro.
Fascinante… pero no la entiendo.
Concretamente ¿cómo se está usando (y porqué) A(x) y B(x)?
Gracias y saludos.
A mí tampoco me sale ningún error.
[…] ¿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 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? […]
A mi tambien me salen millones de INVALID EQUATION, no se puede leer el articulo…
josejuan:
y
son las series generatrices (¿se dice asi? en inglés es «generating series») de las sucesiones de elementos de
y
. 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
no representa ningún número, así que no se necesita verificar condiciones de convergencia.
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… Lee más »
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. 😉
(perdón por el borrón)


entonces usaríamos
para tener en el sumando
(uhm… vale, estoy pegando ‘platex’ y no ‘latex’ [uso Scientific Notebook] ¿qué editor usáis? ¿MiKTeX?)
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
de naturales su funcion caracteristica es una sucesion cuyo elemento
es
si
pertenece a
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?
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.
«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… Lee más »