Solución: libros nuevos

Publicamos la solución al divertimento Libros Nuevos. En esta ocasión, Julio Ojeda Infantes y Pablo Puerto Muñoz, y Floro Damián Aranda han enviado respuestas acertadas.

Divertimento:

Una biblioteca recibe \(2N\) libros nuevos. Deciden colocar en el expositor de novedades dos libros cada día para darlos a conocer, con la posibilidad de repetir los libros con distintas parejas. ¿Cuál es el mínimo número de días que deben pasar para garantizar que, en cada subconjunto de tres libros, al menos dos de ellos hayan estado en el expositor?

Solución:

La solución del problema consta de dos partes. En primer lugar (1) vamos a mostrar que es suficiente \(N(N-1)\) días, es decir, que existe una estrategia para exponer los libros de modo que en ese número de días se cumple la condición del problema. Después (2) probaremos que si se cumple la condición del problema es necesario que hayan transcurrido al menos \(N(N-1)\) días. La solución de esta segunda parte ha sido enviada por Julio Ojeda Infantes y Pablo Puerto Muñoz (la publicada originalmente contenía un error que nos han señalado en los comentarios del problema).

(1) Comenzamos observando que es suficiente \(N(N-1)\) días. Separamos los libros en dos mitades de \(N\) libros. Para exponer todas las parejas que se pueden formar con dos libros de cada mitad, se necesitan $$\binom{N}{2} + \binom{N}{2} = N(N-1)$$ días. De este modo, cada conjunto de tres libros contiene una pareja que ya ha sido expuesta.

(2) Veamos ahora que, si cada conjunto de tres libros contiene una pareja que ya ha sido expuesta, entonces es necesario que hayan pasado al menos \(N(N-1)\) días. Sea \(G = (V, A)\) el grafo tal que su conjunto de vértices \(V\) es el conjunto de los \(2N\) libros nuevos, y hay una arista de \(A\) uniendo dos vértices si y sólo si esa pareja de libros no está ningún dı́a en el expositor. De esta forma, comenzamos con un grafo completo del que se van retirando aristas a medida que se exponen las parejas de libros. El problema se reduce a encontrar el máximo número de aristas que puede haber sin que haya ningún triángulo (\(3\)-ciclo). Esto es ası́ porque si hay tres libros conectados entre sı́, ninguna de sus parejas ha estado expuesta. Y si no hay ningún triángulo, por cada conjunto de tres se puede encontrar una pareja que no esté conectada, es decir, que sı́ haya estado expuesta.

Proposición. Dado \(N \geq 2\), todo grafo con \(2N\) vértices y \(N^2 + 1\) aristas posee al menos un triángulo.

Demostración (por inducción). Si \(N = 2\), sólo existe un grafo con \(2N = 4\) vértices y \(N^2 + 1 = 5\) aristas (el grafo completo \(K_4\) tiene \(6\)), y este tiene dos triángulos.

Supongamos ahora que cualquier grafo con \(2N\) vértices y \(N^2 + 1\) aristas posee al menos un triángulo. Sea \(G\) un grafo con \(2(N + 1) = 2N + 2\) vértices y \((N + 1)^2 + 1\) aristas, y sean \(u\) y \(v\) dos de sus vértices tales que estén conectados. Si \(G\setminus \{u,v\}\) tiene al menos \(N^2 +1\) aristas, se tiene la proposición por la hipótesis de inducción. En caso contrario, si \(G\setminus \{u,v\}\) tiene como mucho \(N^2\) aristas, entre este subgrafo y el formado por \(u\) y \(v\) tiene que haber al menos

$$((N+1)^2+1)-1-N^2 = 2N+1$$

aristas (es decir, el número total de aristas menos la arista \(\{u,v\}\) y como máximo las \(N^2\) aristas del subgrafo). Pero como en \(G\setminus \{u,v\}\) sólo hay \(2N\) vértices, por el princpio del palomar existe un vértice \(w\) conectado tanto con \(u\) como con \(v\), es decir, un triángulo. \(\square\)

Volviendo a los libros, en total hay

$$\binom{2N}{2} = 2N^2-N$$

posibles parejas. Como hemos visto, si faltan por exponer al menos \(N^2 + 1\) parejas, existen tres libros tales que ninguna de sus parejas ha estado expuesta.

En conclusión, tras \(2N^2 − N − (N^2 + 1) + 1 = N^2 − N\) dı́as, y no antes, es posible que en cada subconjunto de tres libros al menos dos de ellos hayan estado en el expositor.