La curiosa identidad de Proizvolov

Matemoción

La conocida como identidad de Proizvolov fue propuesta por el matemático Vyacheslav Proizvolov en forma de problema en las Olimpiadas Matemáticas Soviéticas de 1985:

Consideremos el conjunto de los primeros 2N enteros positivos,

CN = {1, 2, 3, …, 2N − 1, 2N},

y una partición de él en dos subconjuntos de N elementos cada uno de ellos:

AN = {a1, a2, …, aN-1, aN} y BN = {b1, b2, …, bN-1, bN}.

Ordenemos los elementos de ambos conjuntos de la siguiente manera:

Se pide probar que la siguiente suma de valores absolutos

|a1 – b1| + |a2 – b2| + … + |aN-1 – bN-1| + |aN – bN|

es igual a N2.

Un ejemplo

Para entender mejor el enunciado, vamos a ver un ejemplo. Si N = 10, tenemos el conjunto de los veinte primeros números naturales

C10 = {1, 2, 3, …, 19, 20}.

Elegimos las particiones (hemos ordenado los números de la primera partición de manera creciente y los de la segunda de manera decreciente):

A10 = {1, 3, 4, 7, 8, 9, 10, 18, 19, 20}, y

B10 = {17, 16, 15, 14, 13, 12, 11, 6, 5, 2},

Es decir, a1 = 1, a2 = 3, a3 = 4, …, a9 = 19, a10 = 20, b1 = 17, b2 = 16, b3 = 15, …, b9 = 5 y b10 = 2.

Entonces,

|a1 – b1| + |a2 – b2| + … + |a9 – b9| + |a10 – b10| =

|1 – 17| + |3 – 16| + |4 – 15| + |7 – 14| + |8 – 13| + |9 – 12| + |10 – 11| + |18 – 6| + |19 – 5| + |20 – 2| =

16 + 13 + 11 + 7 + 5 + 3 + 1 + 12 + 14 + 18 = 100 = 102.

Una demostración sencilla de la identidad de Proizvolov

Observemos en primer lugar que |a – b| = máx{a,b} – mín{a,b}. En efecto, si a > b, es |a – b| = a – b = máx{a, b} – mín{a, b}, y si b > a, es |a – b| = b – a = máx{a, b} – mín{a, b}.

En segundo lugar, para cada i en {1, 2…, N − 1, N}, se verifica que uno de los números del par {ai, bi} está en el conjunto A = {1, 2…, N − 1, N} y el otro en el conjunto B = {N + 1, N + 2, …, 2N − 1, 2N}.

En efecto, si esta propiedad no fuera cierta, supongamos, por ejemplo, que los números ai y bi pertenecen ambos al conjunto A. Es decir, N + 1 > ai y N + 1 > bi. Eso significa que al menos hay i elementos del conjunto AN que pertenecen a A (ya que N + 1 > ai > … > a2 > a1) y podría haber algún otro elemento de AN también en A) y al menos N − i + 1 elementos del conjunto BN que pertenecen a A (ya que N + 1> bi > bi+1 > … > bN-1 > bN y podría haber algún otro elemento de BN también en A). Es decir, en el conjunto A habría al menos i + (N – i + 1) = N + 1 elementos de CN. Pero eso es imposible, porque A solo posee N elementos. Un argumento similar prueba que tampoco puede suceder que ai y bi pertenezcan ambos al conjunto B.

Es decir, efectivamente, para cada i en {1, 2…, N − 1, N}, se verifica que uno de los números del par {ai, bi} está en el conjunto A = {1, 2…, N − 1, N} y el otro en el conjunto B = {N + 1, N + 2, …, 2N − 1, 2N}. De aquí se deduce que para cada i en {1, 2…, N − 1, N}, es N + 1 > mín{ai, bi} < y máx{ai, bi} > N. Es decir, de otra manera,

A = {1, 2…, N − 1, N} = {mín{ai, bi}: i en {1, 2…, N − 1, N}}, y

B = {N + 1, N + 2, …, 2N − 1, 2N} = {máx{ai, bi}: i en {1, 2…, N − 1, N}}.

Por lo tanto,

|a1 – b1| + |a2 – b2| + … + |aN-1 – bN-1| + |aN – bN| =

(máx{a1, b1} – mín{a1, b1}) + (máx{a2, b2} – mín{a2, b2}) + … + (máx{aN-1, bN-1} – mín{aN-1, bN-1}) + (máx{aN, bN} – mín{aN, bN}) =

(máx{a1, b1} + máx{a2, b2} + … + máx{aN-1, bN-1} + máx{aN, bN}) – (mín{a1, b1} + mín {a2, b2} + … + mín{aN-1, bN-1} + mín{aN, bN}) =

((N + 1) + (N + 2) + … + (2N – 1) + 2N) – (1 + 2 + … + (N – 1) + N) =

((N + 1) – 1) + ((N + 2) – 2) + … + ((2N – 1) – (N – 1)) + (2N – N) =

N + N + … + N = N2. QED

Una generalización de la identidad de Proizvolov

Grégoire Nicollier propuso en 2015 la siguiente generalización de la identidad de Proizvolov:

Consideremos un conjunto de números reales,

CN = {c1, c2, …, c2N-1, cN},

y una partición de él en dos subconjuntos de N elementos cada uno de ellos:

AN = {a1, a2, …, aN-1, aN} y BN = {b1, b2, …, bN-1, bN}.

Ordenemos los elementos de estos conjuntos de la siguiente manera:

Entonces, la suma

|a1 – b1| + |a2 – b2| + … + |aN-1 – bN-1| + |aN – bN|

es independiente de las particiones elegidas AN y BN.

Para probar esta propiedad, basta con observar, con un argumento similar al realizado antes, que para cualquier par {ai, bi}, uno de los elementos es menor que cN + 1 y el otro es mayor que cN. Entonces,

{c1, c2, …, cN-1, cN} = {mín{ai, bi}: i en {1, 2…, N − 1, N}}, y

{cN+1, cN+2, …, c2N-1, c2N} = {máx{ai, bi}: i en {1, 2…, N − 1, N}}.

Y por lo tanto:

|a1 – b1| + |a2 – b2| + … + |aN-1 – bN-1| + |aN – bN| =

(máx{a1, b1} – mín{a1, b1}) + (máx{a2, b2} – mín{a2, b2}) + … + (máx{aN-1, bN-1} – mín{aN-1, bN-1}) + (máx{aN, bN} – mín{aN, bN}) =

(máx{a1, b1} + máx{a2, b2} + … + máx{aN-1, bN-1} + máx{aN, bN}) – (mín{a1, b1} + mín {a2, b2} + … + mín{aN-1, bN-1} + mín{aN, bN}) =

(c2N + c2N-1 + … + cN+2 + cN+1) – (c1 + c2 + … + cN-1 + cN),

que es la misma cantidad para cualquier partición elegida. QED

Además, Grégoire comentaba en el artículo que esta propiedad sigue siendo cierta aunque los números del conjunto C no sean todos diferentes.

¡Curiosas propiedades!

Referencias

Sobre la autora: Marta Macho Stadler es profesora de Topología en el Departamento de Matemáticas de la UPV/EHU, y colaboradora asidua en ZTFNews, el blog de la Facultad de Ciencia y Tecnología de esta universidad

1 comentario

Deja una respuesta

Tu dirección de correo electrónico no será publicada.