Este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.
Este post sobre una curiosa propiedad de determinadas particiones en dos conjuntos de algunos conjuntos finitos de números me recordó una curiosa propiedad de cualquier partición en dos conjuntos infinitos del conjunto de todos los números naturales que leí en algún libro de Honsberger.
Sea una secuencia cualquiera no decreciente,esto es,
, de enteros no negativos.
La función que da el número de términos de la secuencia
que son menores o iguales que
, define una nueva secuencia no decreciente de enteros no negativos que para la secuencia anterior
resulta ser
A esta segunda secuencia, cuyos términos cuentan los términos de la primera menores o iguales que , la llamamos secuencia contadora de la primera secuencia.
Como la secuencia contadora es una secuencia no decreciente de no negativos, podemos obtener a su vez la secuencia contadora de esta secuencia contadora y así sucesivamente.
Pero sucede que:
Dada cualquier secuencia no decreciente de enteros no negativos, la secuencia contadora de la secuencia contadora es la secuencia inicial.
La curiosa conexión con las particiones de números está en:
Si tomamos dos secuencias de forma que una sea la secuencia contadora de la otra, y sumamos vectorialmente a cada una de ellas la secuencia de todos los naturales , resulta una partición
de los números naturales.
En el caso de las secuencias anteriores y
resulta la partición:
Recíprocamente, si partimos en dos subconjuntos infinitos el conjunto de todos los naturales y restamos la secuencia de los naturales de las dos secuencias resultantes de la partición, obtenemos dos secuencias no decrecientes de enteros no negativos que son cada una contadora de la otra.
Los resultados anteriores tienen una demostración visual sin palabras, debida a Dijkstra.
Si busca, el lector encontrará representadas en la figura adjunta las 4 secuencias que hemos usado como ejemplo:
y la secuencia
, de los números naturales.
Y, tras unos momentos de reflexión, verá que la posibilidad de construir una figura análoga para cualquier partición en dos de los naturales da una demostración de los hechos anteriormente expuestos.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
No lo entiendo, ¿qué significa que una secuencia es contadora de otra?
Mirando la secuencia del ejemplo: P = {2,3,5,7,11}, la contadora D(h) es la que cuenta cuantos números hay menores o iguales que h en la secuencia P siendo h>= 0. ejem: h=0, D(0) = 0, ya que no hay ningún valor menor o igual que 0 en P. h=1, D(1) = 0, ya que no hay ningún valor menor o igual que 0 en P. h=2, D(2) = 1, ya que 2 pertenece a P. h=3, D(3) = 2, ya que en P están el 2 y el 3 (menor o igual que h). h=4, D(4) = 2, ya que… Lee más »
Ah vale, muchas gracias es que no lo entendía porque no lo había visto nunca y como no estaba el desarrollo en el post, pues no entendía la explicación que viene en él.
Muchas gracias Orlin.
Un saludo
Pues debo ser muy obtuso pero el caso es que no veo las cuatro secuencias en el gráfico ni, lo más importante, cómo se construyen.
Por cierto, aunque pueda parecer trivial, pienso que habría que exigir que las secuencias no sólo fueran no decrecientes, sino que cada término se repita un número finito de veces, pues de lo contrario no estaría definida su secuencia contadora.
@MMA: Fíjate que en el gráfico hay un rectángulo que ocupa un cuadrito, si miras a la derecha de este hay otro rectángulo que ocupa 2; al lado, otro que ocupa 4, 6, 7, 9… a medida que avanzas hacia la derecha (ya tienes B). Si en lugar de ir hacia la derecha subes, verás que hay un rectangulo de 3 cuadritos, encima otro de 5, 8, 11… y así a medida que subes (ya tienes A). El hecho de la yuxtaposición de todos estos rectángulos ocupe la mitad del plano indica que entre los dos grupos cubren todos los… Lee más »
MMA, buena obervación, como dices las secuencias no solo deben ser no-decrecientes sino además tender a infinito, para que exista la contadora.
Y creo que en el diagrama por ejemplo la secuencia 2,3,5,7….aparece a la derecha de la
linea de puntos vertical…
vaya… que sorprendente el arreglo.
A dijkstra lo conocia solo por su algoritmo de caminos mas cortos.
Un sencillo pero bonito problema de combinatoria: Quien se anima a demostrar:

¿Qué es una partición?
es una pagina que brinda un buen apoyo en el desarrollo de las matemáticas