En una biblioteca hay $n$ estantes, cada uno con al menos un libro. Se compran $k$ nuevos estantes y los libros se ordenan en los $n+k$ estantes, una vez más, con al menos un libro por estante.
Un libro se le llama privilegiado si está en un estante con menos libros que antes. Muestra que hay al menos $k+1$ libros privilegiados.
martes, 20 de marzo de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
12 comentarios:
Una pregunta: ¿lo de "Un libro se le llama privilegiado si está en un estante con menos libros que antes." se refiere a cuál de las dos:
a) el libro es privilegiado cuando estaba en un estante con más libros en el acomodo con n estantes que el estante en que está ahora en el acomodo con n+k estantes?
b) el libro es privilegiado cuando el estante en el que está ahora (en el acomodo con n+k estantes) tenía más libros en el acomodo con n estantes que en el acomodo con n+k estantes?
Probemos el problema por inducción a $n$ con n y k enteros positivos.
Caso base: $n=1$ es cierto porque todos los libros serían privilegiados y hay al menos $n+k \ge k+1$ libros.
Hipótesis de inducción: Es cierto para $n-1$ para $n-1$ y $k$ enteros positivos.
Sean A un acomodo con n estantes y B uno con los mismos libros pero repartidos en n+k estantes en ambos casos con al menos un libro por estante.
Sean $a_i$ la cantidad de libros en estante i de A tal que $a_1 \le a_2 \le ... \le a_n$.
Análogamente definimos $b_i$ para B:
$b_1 \le b_2 \le ... \le b_{n+k}$.
Sea f una función que le asigne a cada libro x el número de libros que había en el librero en el que estaba x en A.
Aplicaremos a B el siguiente algoritmo a cada uno de sus estantes, excepto a $b_{n+k}$:
Sea $i$ el menor entero tal que al estante $b_i$ no le hayamos aplicado el algoritmo antes (al principio $i=1$)
Caso 1.
Si el estante $b_i$ tiene al menos un libro $x$ privilegiado entonces podemos intercambiarlo por el libro $y$ que tenga la mayor $f(y)$ y que no se haya ocupado en el algoitmo anteriormente (al principio será un libro que estuvo en $a_{n}$). Y como $b_i < f(x) \le f(y)$ por ser $x$ privilegiado, $y$ también lo será y si suponemos que $y$ estaba en $b_j$ enonces si $b_j < f(x)$, es decir, $x es privilegiado al hacer el cambio entonces como $f(x) \le f(y)$,y también lo era. Por último movemos los demás libros al estante $b_{n+k}$, y como $b_i \le b_{n+k}$ entonces no creamos ningún nuevo libro privilegiado (al contrario, puede que disminuyan). Entonces el número de libros privilegiados no aumenta en este caso.
Caso 2._
Si el estante $b_i$ no tiene al menos un libro privilegiado. Entonces si $x$ es un libro de $b_i$, $f(x) \le b_i$. Tomemos los $b_i$ libros entre los que están en los estantes a partir de $i$ (incluyendo a $i$) con los menores valores de f asociados, y de menor a mayor intercambiemoslos por los libros de $b_i$ ordenados de menor a mayor (de acuerdo a su valor asociado en f). Si $x$ es uno de los libros de $b_i$ y $y$ el libro por el que se intercambiará que está en $b_j$ con $i \le j$, tenemos que $f(x) \ge f(y)$. Pero $f(x) \le b_i$ y $b_i \le b_j$ . Entonces ni $x$ ni $y$ son privilegiados. Entonces no cambiamos el número de libros privilegiados.
Si podemos aplicar el Caso 1 al menos $k+1$ veces entonces ya acabamos, porque tendríamos al menos $k+1$ libros privilegiados. Entonces supongamos que lo podemos aplicar a lo más $k$ veces. Y por el Caso 2 los libros están "ordenados" de menor a mayor (con base a su valor en f) en los $n+k-1$ estantes.
Sean $c_i$ los estantes a los que se le aplicaron el algoritmo en caso 2 (los demás sólo tienen un libro privilegiado), tal que:
$c_1 \le c_2 \le ... \le c_r$ con $r \ge n$.
Pero por como construimos las $c_i$, los libros están "ordenados" y ninguno es privilegiado (con excepción de $b_{n+k}$, donde podría haber un libro privilegiado). En $c_1$ están por construcción los libros que estaban en $a_1$, y como no son privilegiados $c_1 \ge a_1$.
Ahora lo que haremos es tomar los $s = c_1 - a_1$ libros con el valor de f mayor de cada $c_i$ y los cambiaremos a $c_{i+1}$ para $1 \le i \le {r-1}$. Y como las $c_i$ están ordenadas, no aumentamos la cantidad de libros privilegiados.
Por último veamos que sin contar a $a_1$ y a $c_1$, la configuracón que queda es de $n-1$ estantes en A y $n-1+k$ en B, entonces por hipòtesis de inducción hay al menos $k+1$ libros privilegiados.
Caso 1.
Si el estante $b_i$ tiene al menos un libro $x$ privilegiado entonces podemos intercambiarlo por el libro $y$ que tenga la mayor $f(y)$ y que no se haya ocupado en el algoitmo anteriormente (al principio será un libro que estuvo en $a_{n}$). Y como $b_i < f(x) \le f(y)$ por ser $x$ privilegiado, $y$ también lo será y si suponemos que $y$ estaba en $b_j$ entonces si $b_j < f(x)$, es decir, $x es privilegiado al hacer el cambio entonces como $f(x) \le f(y)$,y también lo era. Por último movemos los demás libros al estante $b_{n+k}$, y como $b_i \le b_{n+k}$ entonces no creamos ningún nuevo libro privilegiado (al contrario, puede que disminuyan). Entonces el número de libros privilegiados no aumenta en este caso.
Caso 2._
Si el estante $b_i$ no tiene al menos un libro privilegiado. Entonces si $x$ es un libro de $b_i$, $f(x) \le b_i$. Tomemos los $b_i$ libros entre los que están en los estantes a partir de $i$ (incluyendo a $i$) con los menores valores de f asociados, y de menor a mayor intercambiemoslos por los libros de $b_i$ ordenados de menor a mayor (de acuerdo a su valor asociado en f). Si $x$ es uno de los libros de $b_i$ y $y$ el libro por el que se intercambiará que está en $b_j$ con $i \le j$, tenemos que $f(x) \ge f(y)$. Pero $f(x) \le b_i$ y $b_i \le b_j$ . Entonces ni $x$ ni $y$ son privilegiados. Entonces no cambiamos el número de libros privilegiados.
Caso 1.
Si el estante $b_i$ tiene al menos un libro $x$ privilegiado entonces podemos intercambiarlo por el libro $y$ que tenga la mayor $f(y)$ y que no se haya ocupado en el algoitmo anteriormente (al principio será un libro que estuvo en $a_{n}$). Y como $b_i < f(x) \le f(y)$ por ser $x$ privilegiado, $y$ también lo será y si suponemos que $y$ estaba en $b_j$ entonces si $b_j < f(x)$, es decir, $x es privilegiado al hacer el cambio entonces como $f(x) \le f(y)$,y también lo era. Por último movemos los demás libros al estante $b_{n+k}$, y como $b_i \le b_{n+k}$ entonces no creamos ningún nuevo libro privilegiado (al contrario, puede que disminuyan). Entonces el número de libros privilegiados no aumenta en este caso.
Caso 2._
Si el estante $b_i$ no tiene al menos un libro privilegiado. Entonces si $x$ es un libro de $b_i$, $f(x) \le b_i$. Tomemos los $b_i$ libros entre los que están en los estantes a partir de $i$ (incluyendo a $i$) con los menores valores de f asociados, y de menor a mayor intercambiémoslos por los libros de $b_i$ ordenados de menor a mayor (de acuerdo a su valor asociado en f). Si $x$ es uno de los libros de $b_i$ y $y$ el libro por el que se intercambiará que está en $b_j$ con $i \le j$, tenemos que $f(x) \ge f(y)$. Pero $f(x) \le b_i$ y $b_i \le b_j$ . Entonces ni $x$ ni $y$ son privilegiados. Entonces no cambiamos el número de libros privilegiados.
Si podemos aplicar el Caso 1 al menos $k+1$ veces entonces ya acabamos, porque tendríamos al menos $k+1$ libros privilegiados. Entonces supongamos que lo podemos aplicar a lo más $k$ veces. Y por el Caso 2 los libros están "ordenados" de menor a mayor (con base a su valor en f) en los $n+k-1$ estantes.
Sean $c_i$ los estantes a los que se le aplicaron el algoritmo en caso 2 (los demás sólo tienen un libro privilegiado), tal que:
$c_1 \le c_2 \le ... \le c_r$ con $r \ge n$.
Pero por como construimos las $c_i$, los libros están "ordenados" y ninguno es privilegiado (con excepción de $b_{n+k}$, donde podría haber un libro privilegiado). En $c_1$ están por construcción los libros que estaban en $a_1$, y como no son privilegiados $c_1 \ge a_1$.
Ahora lo que haremos es tomar los $s = c_1 - a_1$ libros con el valor de f mayor de cada $c_i$ y los cambiaremos a $c_{i+1}$ para $1 \le i \le {r-1}$. Y como las $c_i$ están ordenadas, no aumentamos la cantidad de libros privilegiados.
Por último veamos que sin contar a $a_1$ y a $c_1$, la configuracón que queda es de $n-1$ estantes en A y $n-1+k$ en B, entonces por hipòtesis de inducción hay al menos $k+1$ libros privilegiados.
Podemos ver cómo el problema se puede transformar a una gráfica de $n$ puntos por un lado y $n+k$ del otro (son lados $A$ y $B$ respectivamente), dónde sólo hay segmentos del primer conjunto al segundo y todos tienen grado al menos uno (puede haber muchos segmentos de un punto a otro) y la suma de grados del lado $A$ y del lado $B$ son iguales. Además, si se cumple para cada componente conexa que tiene $i$ del primer tipo e $i+j$ del otro ($j+1$ segmentos privilegiados), entonces al sumar todos los de este tipo, la diferencia entre los que hay del segundo tipo y los del primero es de al menos $k$ y entonces al menos hay $k+1$ segmentos privilegiados, así que asumimos que es conexa.
Procederemos suponiendo que hay a lo más $k$ privilegiados, lo que significa que si eliminamos a los puntos del lado $B$ que están involucrados en esto nos quedan al menos $n$ y no sólo eso, sino que no habrá más privilegiados (entre los segmentos que quedaron), pues el grado de los del lado $A$ no aumentaron, además de que la suma de grados sigue siendo igual en ambos lados. Con esto, si hubo algunos puntos de $A$ que sólo estaban conectados con esos que eliminamos, entonces ya no los consideramos. Ahora veamos que de los restantes en $A$ podemos ver que sigue siendo una gráfica conexa. Esto se debe a que, si $v_{1}$ y $v_{2}$ no están conectados de ninguna forma, entonces cualquiera que esté conectado con uno, no está conectado con los conectados del otro, pero antes solían ser conectados (por lo que supusimos arriba), así que esa conección se perdió al eliminar los puntos de $B$ que tenían segmentos privilegiados.
Ahora, si tomamos cualquier subconjunto de $b$ puntos de $B$, están conectados al menos $b$ puntos del otro lado, pues si un punto de $A$ está conectado a uno de $B$, entonces el de $A$ tiene grado menor o igual al de $B$ pues quitamos todos los segmentos que no cumplían esto. Esto quiere decir que un punto de $B$ está conectado con al menos uno de $A$ y por cada uno que contemos de $B$, si hay menos que los que hay de $A$ entonces tomando al mayor de $A$ y viendo que con quien(es) esté conectado tienen al menos lo que él tiene (de grado) y yendo al siguiente más grande de $A$ que esté en contacto con al menos otro de $B$ (dentro de los que teníamos elegidos) y así sucesivamente. Entonces, si hubo entre el $i$-ésimo más grande y el siguiente (de estos) hubo $j$ puntos con grado menor o igual al $i$-ésimo que no fueron usados, significa que todos con los que ellos entraron en contacto, ya habían sido "tocados" por puntos de grado mayor (o igual) y entonces cada uno ya tenía grado mayor o igual que éstos (los que no se usaron). Además de que por la propiedad de que los de $B$ tienen grado mayor o igual, con los puntos ordenados de mayor a menor hasta el $i$-ésimo usado no pudieron haber satisfecho (igualado el grado) de todos los de $B$ que se tenían en consideración (a menos que el $i+1$-ésimo fuera, en orden, el siguiente punto con mayor grado, en cuyo caso si pudo pasar) por lo que, si el siguiente mayor fue usado, entonces este agregó al menos a otro, y si no fue usado, entonces con los mismos que había del otro lado (del lado $B$) alcanzaban a conectarse con incluso más del lado $A$. En conclusión, el primero que tomemos de $B$ está conectado con al menos otro, y a partir de ahí podemos agregar los de $A$ con una frecuencia siempre mayor o igual a con la cual agregamos los de $B$ (pues por cierto, si no se toma al $i$-ésimo y tomamos a alguno de los que siguen, sigue agregando a otro o se da lo mismo de que los anterioren no habían satisfecho el grado de los de $B$ y enotnces se sigue cumpliendo) y entonces por el Teorema Hall, podemos aparear perfectamente a los puntos de $B$ con los de $A$.
Esto nos dice muchas cosas, entre ellas, que no se eliminó (se ignoró) a ningún punto de $A$, otra, que en cada pareja del apareamiento, el que es de $B$ tiene grado mayor o igual al de $A$ pero la suma de los de $B$ (los que quedaron) es igual a la de los de $A$, así que se da la igualdad en cada pareja. Así, si los ordenamos de menor a mayor, los segmentos que llegaron al (o a los) de menor grado de $B$ tuvieron que haber venido de su pareja (o si hay muchos, todos los del mismo grado de $B$ vienen de todas las parejas de esos mismos), o habría habido otro segmento privilegiado y entonces los ignoramos y repetimos el proceso hasta ver que todas las parejas están conectadas únicamente entre sí. Pero ahora, sabemos que de los puntos de $A$, hay al menos uno que fue el que solía tener segmentos privilegiados (pues ninguno de $A$ fue ignorado) y entonces esto significa que en realidad tenía más grado antes y entonces todas las conexiones con su pareja (al menos una) son privilegiadas en realidad, y como teníamos ya a $k$ privilegiadas, entonces hay al menos $k$ con lo que concluímos que el enunciado es cierto $\blacksquare$
Lema 1. Sea $A$ una matriz de $nx(n+k)$, sean $c_{ij}$ sus entradas tal que todas son enteros no negativos, sean $x_1, x_2...x_n$ las filas y $y_1,y_2...y_{n+k}$ las columnas, y $X_i$ y $Y_i$ la suma de las entradas en la $x_i$ y en la $y_i$ respectivamente, tal que $X_i,Y_i\geq 1$ para todo $i$. Sea $f(i,j)=1$ si $X_i\geq Y_i+1$ y $f(i,j)=0$ de lo contrario. Entonces $\sum f(i,j)c_{i,j}\geq k+1$.
Hagámoslo por inducción sobre $k$, supongamos que es cierto para toda matriz de $nx(n+k)$, ahora tomemos una matriz $A$ de $nx(n+k+1)$, por hipótesis de inducción es claro que existe un sumando positivo en la suma $\sum f(i,j)c_{i,j}$, así que supongamos que $f(r,s)c_{r,s}\geq 1$, ahora, sea $B$ la matriz que resulta de quitar la columna $y_s$ a la matriz $A$, por hipótesis de inducción, $\sum_{c_{i,j}\in B} f(i,j)c_{i,j}\geq k+1$ haciendo dicha suma sobre la matriz B y como la $A$ mantiene la misma cantidad de filas se sigue cumpliento que $\sum f(i,j)c_{i,j}\geq 1$ haciendo la suma sobre la matriz $A$, pero como en esa suma no se tiene el sumando $f(r,s)c_{r_s}$ por la manera en que se construyó $B$ entonces $\sum_{c_{i,j}\in A} $f(i,j)c_{i,j}\geq (k+1)+1$ con lo cual se concluye el paso inductivo.
Lema 1. Sea $A$ una matriz de $nx(n+k)$, sean $c_{ij}$ sus entradas tal que todas son enteros no negativos, sean $x_1, x_2...x_n$ las filas y $y_1,y_2...y_{n+k}$ las columnas, y $X_i$ y $Y_i$ la suma de las entradas en la $x_i$ y en la $y_i$ respectivamente, tal que $X_i,Y_i\geq 1$ para todo $i$. Sea $f(i,j)=1$ si $X_i\geq Y_i+1$ y $f(i,j)=0$ de lo contrario. Entonces $\sum f(i,j)c_{i,j}\geq k+1$.
Hagámoslo por inducción sobre $k$, supongamos que es cierto para toda matriz de $nx(n+k)$, ahora tomemos una matriz $A$ de $nx(n+k+1)$, por hipótesis de inducción es claro que existe un sumando positivo en la suma $\sum f(i,j)c_{i,j}$, así que supongamos que $f(r,s)c_{r,s}\geq 1$, ahora, sea $B$ la matriz que resulta de quitar la columna $y_s$ a la matriz $A$, por hipótesis de inducción, $\sum_{c_{i,j}\in B} f(i,j)c_{i,j}\geq k+1$ haciendo dicha suma sobre la matriz B y como la $A$ mantiene la misma cantidad de filas se sigue cumpliento que $\sum f(i,j)c_{i,j}\geq 1$ haciendo la suma sobre la matriz $A$, pero como en esa suma no se tiene el sumando $f(r,s)c_{r_s}$ por la manera en que se construyó $B$ entonces $\sum_{c_{i,j}\in A} f(i,j)c_{i,j}\geq (k+1)+1$ con lo cual se concluye el paso inductivo.
Regresando al problema, tomemos una matriz en donde cada estante inicial será representado por una fila, cada estante final será representado por una columna, la entrada $c_{i,j}$ será la cantidad de libros que pasaron del estante que tiene asosiada la fila $x_i$ al que tiene asociada la columna $y_j$, así el problema se vuelve equivalente al lema 1.
Publicar un comentario