Sea N un entero positico. Supongamos que una coleccion de enteros fue escrita en un pizarron de tal manera que se cumplen las siguientes propiedades:
Cada numero escrito k satisface qeu 1=<k=<N
Cada k con 1=<k=<N fue escrito una vez
La suma de todos los numeros escritos es par
Demuestra que es posible marcar algunos con O y el resto con X de tal manera que la suma de los numeros marcados con 0 es igual a la suma de los numeros marcados X
cada k fue escrita a lo mas 1 vez, es decir, puede no estar escrita? o tiene que ser exactamente 1 vez?
ResponderBorrarsorry me comi palabras al menos una vez
BorrarCambia la redaccion del post, porque tambien me confundi yo jeje para que otra persona no lo entienda mal
BorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarSolución.
ResponderBorrarDemostraremos que el conjunto $X$ de números se puede separar en dos subconjuntos $A$ y $B$ con la misma suma por inducción.
Comenzaremos con la mínima cantidad de números posibles en el conjunto $X$ para hacer el caso base. Sabemos que los números $1, 2, 3, ... , N$ deben aparecer al menos una vez. Entonces esa puede ser la mínima cantidad. Pero si los sumamos tenemos que $\frac{N(N+1)}{2}$ debe ser par. Esto solo puede ocurrir cuando $N \equiv 0, 3 (mod 4)$. Ahora para la mínima cantidad de números cuando $N \equiv 1, 2 (mod 4)$ necesitamos los números del $1$ al $N$ por la condición del problema y agregar un número más que tiene que ser impar para que la suma total sea par.
Entonces hagamos el caso base en 4 casos.
1) $N \equiv 0 (mod 4)$.
Para este caso podemos usar el siguiente lema. Lema W: Si tenemos $4k$ números consecutivos, entonces se pueden partir en $2$ subconjuntos con igual suma. La desmotración es directa cuando tomamos el primer número de la lista y lo sumamos con el último y el segundo con el penúltimo, etc. Si son $4k$ números entonces tendremos $2k$ parejas de números que sumen lo mismo entonces ponemos $k$ parejas en un subconjunto y otras $k$ parejas en otro. Entonces tendremos los dos subconjuntos con igual suma como queríamos.
Por el lema anterior los números $1, 2, ... , N$ se pueden partir en 2 subconjuntos $A$ y $B$ con igual suma.
2) $N \equiv 1 (mod 4)$.
En este caso tenemos los números $1, 2, ... , N$ y un número impar extra $a$ para que la suma de todos los números sea par. Este número puede ser de la forma $4k+1$ o $4k+3$ ya que es impar. Haremos los dos casos.
2.1) $a = 4k+1$. Aquí tenemos repetido el número $a$ en la lista de números. Entonces cada uno de ellos lo mandamos a un subconjunto de $A$ y $B$. Entonces nos quedarían $4k$ números a la izquierda de $a$ y otro múltiplo de $4$ a la derecha de $a$ para así sumar $1 mod 4$ en este caso. La lista se vería de la siguiente forma:
\[1, 2 , ... , 4k, 4k+1, 4k+1, 4k+2, ... , N\]
donde $a=4k+1$ y esta repetido. Sabemos que quitando los dos $a$ dividiremos el conjunto en dos subconjuntos de números consecutivos y con cardinalidad múltiplo de 4.
${1, 2 , ... , 4k}$ y ${4k+2, ... , N}$ ya que $N \equiv 1 (mod 4)$. Por el lema W sabemos que esos 2 subconjuntos se pueden partir en 2 subconjuntos de igual suma cada uno. Entonces el conjunto original se puede partir en 2 subconjuntos $A$ y $B$ de igual suma.
2.2) $a=4k+3$. En este caso nos tomamos los números $4k+1, 4k+2, 4k+3, 4k+3, 4k+4, 4k+5$, donde sabemos que $4k+3$ esta repetido. Entonces, ponemos en $A$ los números $4k+1, 4k+5, 4k+3$ y en $B$ ponemos $4k+2, 4k+4, 4k+3$. Entonces los dos subconjuntos tendran la misma suma. Cuando quitamos estos $5$ números dividimos a $X$ en $2$ subconjuntos con cardinalidad múltiplo de 4. Por el lema W sabemos que los podemos acomodar en $A$ y $B$ para tener la misma suma tal como lo hicimos en el caso 2.1. Entonces acabamos.
Este comentario ha sido eliminado por el autor.
Borrar3) $N \equiv 2 (mod 4)$.
BorrarEn este caso nos tomamos los números $1, N-1, N$ del conjunto y ponemos a $1, N-1$ en $A$ y a $N$ en $B$ y tendrán igual suma. Ahora nos quedan la lista ${2, 3, ... , N-3, N-2}$ y un número $a$ extra impar. Si este número impar es $1$ o $N-1$ entonces tendriamos una lista con cardinalidad múltiplo de 4 y acabaríamos por el lema W. Supongamos que el número $a$ es uno de los números en ${2, 3, ... , N-3, N-2}$. Este número puede ser $4k+1$ o $4k+3$. Hagamos ambos casos.
3.1) $a = 4k+1$. En este caso tomamos los números $4k, 4k+1, 4k+1, 4k+2$. Ponemos a $4k+1, 4k+1$ en $A$ y a $4k, 4k+2$ en $B$ y la suma sera igual. Entonces nos quedamos con las listas ${2, 3, ... , 4k-1} y {4k+3, ... , N-2}$ por acomodar. Cada lista tiene una cardinalidad $2 (mod 4)$. Nos tomamos la mas pequeña de ellas. S.P.D.G. sea ${2, 3, ... , 4k-1}$ la mas chica. Entonces nos tomamos las parejas $2+(N-2), 3 + (N-3), ... , (4K-1) + (N - 4k + 2)$. Como cada pareja suma $N+1$ y son un núm. par de parejas, podemos poner la mitad en $A$ y la mitad en $B$. Al final nos quedaría la lista ${4k+3, ... , N - 4k +1}$ por acomodar. Pero estos son números consecutivos y una cantidad mult. de 4. Entonces por el lema W se pueden acomodar en $A$ y $B$.
3.2) $a=4k+3$. Aquí nos tomamos los números $4k+2, 4k+3, 4k+3, 4k+4$ y ponemos $4k+2, 4k+4$ en $A$ y $4k+3, 4k+3$ en $B$. Entonces la suma sera la misma. Ademas los números que nos quedan son dos listas $2, … , 4k+1$ y $4k+5, … , N-2$ de numeros consecutivos y cada lista tiene cardinalidad mult. De 4. Entonces por el lema W se pueden acomodar en $A$ y $B$ y tendran la misma suma.
4) $N \equiv 3 (mod 4)$.
En esta caso solo tenemos que acomodar los números $1, 2, ... , N$ en los subconjuntos $A$ y $B$. Tomamos $1, 2$ los ponemos en $A$ y $3$ lo ponemos en $B$ y la suma es igual. Ahora nos quedan la lista ${4, 5, ... , N}$ por acomodar, pero la lista tiene cardinalidad mult. de 4 y son números consecutivos. Entonces por el lema W se pueden acomodar y acabamos.
Ahora que demostramos los casos base. Hagamos la hipótesis de inducción.
Supongamos que tenemos la lista de números $X$ y se puede separar en dos subconjuntos $A$ y $B$ de igual suma.
Nuestro paso inductivo será agregar un número o dos y ver que se sigue cumpliendo la condición. Podemos agregar un número par y la suma en $X$ seguira siendo par. Pero no podemos agregar un solo impar, así que tenemos que agregar al menos dos impares para que la suma sea par. Hagamos los dos casos.
Caso 1) Si agregamos un par $2k$ a $X$, tenemos que acomodarlo en uno de los dos conjuntos $A$ o $B$ y que tengan la misma suma. Sea $S$ la suma de los números en $A$ y en $B$ inicialmente. Luego encontramos el número $k$ en alguno de los subconjuntos. Sabemos que existe porque $k \leq N$. S.P.D.G. $k$ esta en $A$, entonces lo movemos a $B$, y la suma de cada conjunto será la siguiente:
$Suma(A) = S - k$
$Suma(B) = S + k$.
Luego ponemos al nuevo número $2k$ en $A$ y tendremos.
$Suma(A) = S - k + 2k = S + k$
$Suma(B) = S + k$
lo cual completa el paso inductivo.
Caso 2) Si agregamos los impares $2k+1$ y $2m+1$ entonces nos tomamos el número $k+m+1$ en alguno de los subconjuntos $A$ o $B$ y sabemos que existe porque $k+m+1 \leq N$ ya que $2k+1, 2m+1 \leq N$ por la condicion del problema que todos los núm. en $X$ son menores o iguales a $N$. S.P.D.G. $k+m+1$ esta en $A$. Movemos $k+m+1$ a $B$ y entonces la suma sera
$Suma(A) = S - (k+m+1)$
$Suma(B) = S + (k+m+1)$
Agregamos los dos nuevos números a $A$ y tendremos
$Suma(A) = S - (k+m+1) + (2k+1) + (2m+1) = S + k +m + 1$
$Suma(B) = S + k + m + 1$
donde las dos suman serán la misma y esto completa la inducción. Q.E.D.