Un vecindario emprendedor

Francisco Antonio González Lahoz

El pueblo de Bolci tiene solo una calle, que está dividida en 20 parcelas alineadas y numeradas como se muestra en la figura 1. En esas parcelas, viven 26 familias que nombramos con letras desde la A a la Z.

Diremos que dos familias son vecinas cuando vivan en la misma parcela, como las familias E y G, o cuando vivan en parcelas adyacentes, como las familias D y G.

Los habitantes de Bolci van a derribar sus viviendas actuales para construir una manzana de pisos a la que se mudarán. La manzana ocupará unas pocas parcelas y el resto del terreno se destinará a zonas verdes y servicios públicos.

Aún no han decidido donde estarán los pisos, ni cuantas viviendas habrá en cada parcela, pero los habitantes del pueblo han acordado que un posible proyecto será válido solo si cumple las tres condiciones siguientes:

1. Respeto de las divisiones parcelarias: cada nueva vivienda debe estar completamente ubicada dentro de alguna de las primitivas parcelas.

2. Mantenimiento de la vecindad: las familias que ahora son vecinas deben seguir siéndolo cuando se trasladen a su nueva casa. Cada familia podrá tener nuevos vecinos, pero no debe perder los actuales.

3. Cambio de parcela: todos los habitantes cambiarán de parcela, pues ninguna familia desea quedarse en su parcela inicial.

En la figura se muestra un ejemplo de proyecto válido:

Fíjate que en este ejemplo las familias vecinas L y M siguen ocupando sus parcelas iniciales, 9 y 10. Tan solo han intercambiado entre sí el número de parcela. Decimos entonces que en las parcelas 9 y 10 hay un sitio de cruce. En general, un proyecto presenta un sitio de cruce en dos parcelas si a ellas se trasladan al menos dos familias vecinas intercambiando sus números de parcela iniciales.

El desafío consiste en determinar la cantidad mínima y máxima de sitios de cruce que puede llegar a tener un proyecto válido.

Solución

Todo proyecto válido tiene un sitio de cruce y solo uno. La demostración puede realizarse de distintas formas.

Demostración gráfica

Dibujamos una gráfica donde los nombres de las familias se ponen en el eje de abscisas y los números de parcelas en el eje de ordenadas. Marcamos las celdas que indican qué parcela ocupa cada familia. A la gráfica de la situación de partida la llamaremos gráfica inicial, y a la del proyecto válido gráfica final. En la figura se muestra la gráfica inicial con aspas y la gráfica final de nuestro ejemplo con círculos.

La gráfica inicial parte de la esquina inferior izquierda y llega a la esquina superior derecha, sin bajar nunca. Como ni la familia A ni la familia Z pueden permanecer en su parcela inicial, la gráfica final debe arrancar (a la izquierda) necesariamente por encima de la gráfica inicial, y terminar (a la derecha) necesariamente por debajo.

Por mantenerse la relación de vecindad, ambas gráficas deben formarse siempre con celdas contiguas, unidas por un lado o por una esquina.

En estas condiciones las dos gráficas tienen que cruzarse, es decir, debe haber un punto fijo. En nuestro problema, el punto fijo no puede darse en una celda común, porque eso querría decir que hay un vecino que no cambia de parcela, de modo que el cruce solo puede ocurrir en una esquina de las celdas, tal como sucede en el ejemplo. Un cruce de este tipo representa a dos familias vecinas que intercambian su número de parcela. Dicho de otra forma: todo punto fijo de las gráficas estará en un sitio de cruce.

En el cruce de las gráficas, necesariamente una sube y la otra baja. Puesto que la gráfica inicial nunca baja, cuando la gráfica final haya pasado por debajo de ella ya no podrá volver a rebasarla pues para ello tendría que “retroceder”. Por tanto, solo puede tener un punto fijo.

Para completar nuestro razonamiento, debemos verificar que un sitio de cruce siempre implica la existencia de un punto fijo en la gráfica. Eso sería muy claro si en cada parcela solo hubiera inicialmente una familia, porque entonces la representación del intercambio de las dos parcelas entre los vecinos sería precisamente la del cruce de gráficas de nuestro ejemplo. La duda surge cuando en las parcelas iniciales viven varias familias.

Pero observemos que, en ese caso, cuando una familia intercambia la parcela con su vecino, las otras familias de esa parcela deben mudarse con ella, ya que todas deben ir a un lugar vecino a ambas familias. Eso quiere decir que esas familias se mudan como si fuesen solo una, generando también un cruce de gráficas.

En conclusión: todo sitio de cruce implica la existencia de un punto fijo en la gráfica, y, por tanto, el punto de cruce es único.

Otra demostración

Aunque la demostración gráfica proporciona una idea muy intuitiva de la situación, el resultado puede obtenerse con otro razonamiento.

Representamos las familias con una función F(1)=A... F(26)=Z. Entonces F(n) y F(n + 1) representan a familias vecinas.

Cada familia, al mudarse, se debe desplazar hacia la izquierda o hacia la derecha.

La familia F(1) se desplaza a la derecha y la F(26) a la izquierda. Luego debe haber un valor mínimo de n tal que la familia F(n) se desplace a la izquierda. La familia anterior a esa, F(n − 1), se desplaza a la derecha. Resulta entonces que F(n) y F(n − 1) son dos familias que intercambian de parcela. Con esto hemos demostrado la existencia de un punto de cruce.

Es imposible que F(m) se desplace a la izquierda y F(m + 1) a la derecha, porque entonces esas familias serían vecinas que quedarían separadas. A partir de esta observación se demuestra que cuando m es mayor que n la familia F(m) se desplaza necesariamente a la izquierda, sin poder dar lugar a un nuevo intercambio de parcelas en otro sitio. Un razonamiento similar demuestra que todas las familias F(m) con m menor que n − 1 se desplazan a la derecha y tampoco esas familias pueden generar un nuevo intercambio de parcelas.

En conclusión, el número de intercambios es exactamente uno.

MÁS INFORMACIÓN

Este desafío está inspirado en el Teorema del Punto Fijo. Se trata de un resultado topológico que se aplica a transformaciones continuas de un conjunto dentro de sí mismo. Tiene diversas variantes para distintos tipos de subconjuntos y topologías. Por ejemplo, si tomamos una hoja de papel y la plegamos sin roturas, dejándola dentro del lugar que ocupaba inicialmente, el teorema del punto fijo nos asegura que al menos uno de los puntos de la hoja quedará en su posición inicial.