Un solo sitio de cruce

Ya hay solución para el trigésimo séptimo desafío matemático con el que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española., el segundo de los propuestos por los lectores. Francisco Antonio González, desarrollador informático de Indra en San Fernando de Henares (Madrid), propuso el problema (vídeo de la izquierda), y lo resuelve ahora (vídeo de la derecha).

Parece que a los lectores les ha costado algo más hacerse con este desafío: se han recibido en el plazo marcado 120 respuestas, de las que un 75% eran correctas. El ganador de una biblioteca matemática como la que entrega cada semana EL PAÍS ha sido en esta ocasión Javier Rodríguez, de San Sebastián de los Reyes (Madrid).

Recordemos brevemente que el desafío trataba sobre un nuevo diseño urbanístico para el pueblo de Bolci. Esta localidad tenía una sola calle, con 20 parcelas alineadas y numeradas en las que vivían 26 familias distribuidas como muestra la figura 1. Para mejorar los equipamientos, se iban a derribar las viviendas para construir una manzana de pisos. El proyecto arquitectónico para la nueva distribución debía respetar tres condiciones: 1) Cada vivienda nueva debe estar completamente ubicada dentro de alguna de las primitivas parcelas; 2) Las familias que ahora son vecinas deben seguir siéndolo cuando se trasladen a su nueva vivienda; y 3) Ninguna familia se mantiene en su parcela inicial, todas deben cambiar de número de parcela.

A partir de ahí, llamábamos sitio de cruce de un proyecto a dos parcelas que contuvieran al menos un par de familias vecinas que, en la mudanza, intercambiasen entre sí su número de parcela. Y el desafío consistía en obtener la cantidad mínima y máxima de sitios de cruce que puede llegar a tener un proyecto válido, dando las razones que garantizan que no hay posibilidad de construir proyectos válidos con una cantidad de sitios de cruce fuera de ese rango.

La solución es que en todo proyecto válido siempre hay un sitio de cruce y solo puede haber uno. Por tanto, los valores máximo y mínimo coinciden y valen 1.

Para demostrarlo, hacemos la gráfica que se muestra a la izquierda (ver ampliación aquí) con los nombres de las familias en el eje de abscisas y los números de parcelas en el eje de ordenadas. A continuación, marcamos las celdas que representan una asignación familia-parcela. En la gráfica, hemos representado la situación inicial (figura1) con celdas azules y la de nuestro proyecto ejemplo (figura 2) con celdas amarillas. Observemos que la gráfica azul, relativa a la situación inicial, parte de la esquina inferior izquierda y llega a la esquina superior derecha, sin bajar nunca.

Observemos a continuación que la gráfica de un proyecto válido, sea cual sea este, deberá arrancar a la izquierda, necesariamente por encima de la gráfica azul, y llegar a la esquina derecha, necesariamente por debajo de la gráfica azul (porque ninguna familia puede repetir parcela y, por tanto, la A deberá estar por encima de la casilla 1 y la Z por debajo de la 20). Además, ambas gráficas deben presentar siempre celdas contiguas (unidas por un lado o por un pico), debido a la necesidad de mantener la relación de vecindad y, en los proyectos válidos, la gráfica puede oscilar para arriba y para abajo.

Así, debido a dónde empiezan y terminan, y a que recorren celdas contiguas, las dos gráficas tienen necesariamente que cruzarse en algún momento (deben tener 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. El cruce solo puede ocurrir en un pico de las celdas, tal como sucede en la gráfica de ejemplo.

Un cruce de este tipo representa a dos familias vecinas que intercambian su número de parcela. Dicho de otra forma, el punto fijo de la gráfica está en un sitio de cruce.

Además, al cruzarse las gráficas, necesariamente una sube y la otra baja. Puesto que la gráfica azul nunca baja, esto descarta que pueda haber más de un punto fijo, ya que no es posible un cruce que haga pasar la gráfica amarilla por encima de la azul.

Para completar nuestro razonamiento, debemos asegurarnos ahora de que un sitio de cruce siempre implica la existencia de un punto fijo en la gráfica. Eso está muy claro si en cada parcela solo hay un habitante, porque entonces la representación del intercambio de las dos parcelas entre los vecinos es la misma que la del cruce de gráficas de nuestro ejemplo. Pueden surgir dudas cuando en la parcela inicial vivan varias familias ya que las familias que intercambian parcela pueden quedar separadas en el eje de la gráfica.

Pero observemos que, cuando una familia intercambia la parcela con su vecino, si en su parcela inicial había otras familias, entonces todas ellas deben mudarse juntas a la parcela del vecino. Esto ocurre porque cada una de las otras familias debe ir a un lugar que mantenga la vecindad con ambas y, como no se puede quedar en su parcela inicial, acaba necesariamente en la parcela vecina.

Luego, en este caso, las familias se mudan en grupo, y el dibujo de esta situación muestra también necesariamente un cruce de gráficas para un par de familias vecinas. 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 también debe ser único.

Otras soluciones

La demostración anterior puede hacerse sin utilizar la gráfica, con un razonamiento que es equivalente al anterior, aunque formulado en otros términos:

Representamos las familias como F(1)=A... F(26)=Z.

Entonces F(n) y F(n+1) representan familias vecinas.

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

La familia F(1) se desplaza a la derecha y la F(26) a la izquierda.

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 a la derecha.

Se puede ver que entonces que F(n) y F(n-1) tienen que ser dos familias que intercambian de parcela. Con esto hemos demostrado la existencia de un punto de cruce.

Suponiendo la existencia de otro punto de cruce posterior en m, y apoyándonos en la observación de que es imposible que F(m) se desplace a la izquierda y F(m+1) a la derecha, porque entonces estas familias serían vecinas que quedarían separadas, también se demuestra que el sitio de cruce es único.

Este desafío está inspirado en el llamado Teorema del punto fijo. Es un teorema matemático muy importante y útil. En nuestra solución mostramos su versión más sencilla, el caso sobre una dimensión, pero el teorema también ofrece variantes muy interesantes para superficies, volúmenes y otros casos más generales. Varias soluciones mencionan explícitamente el Teorema de Bolzano (Alfonso Pérez Arnal sugiere incluso, acertadamente, que esa puede ser la inspiración para el nombre del imaginario pueblo de Bolci).

Algunos lectores han cometido un pequeño error de interpretación: no han tenido en cuenta que el valor pedido es el de número de puntos de cruce, no de familias que intercambian de posición. Así, tras exponer un argumento correcto, han dado la respuesta de 4 puntos de cruce (es el máximo de familias que pueden intercambiar de posición).

Las respuestas basadas en la gráfica son algo menos de 1/3 de las correctas, por ejemplo la de Fabio Sarmiento Almeida. Una mayoría de las respuestas, como la de Eduardo Rodríguez Golvano, se han basado en argumentos sobre el número de parcelas que se han desplazado los vecinos o sobre ir a la derecha o a la izquierda.

Unas pocas versiones de la demostración, entre ellas la del ganador del sorteo, plantean demostraciones por recurrencia (añadiendo parcelas de los extremos) o aumentando el número de parcelas de la manzana, y hay una especialmente buena por su concisión enviada, sin firmar, por RDAVIDA.

Para seguir investigando: Jesús Campos resuelve correctamente el problema y plantea una variante que no termina de resolver: ¿cuál es el número máximo y mínimo si no ponemos la restricción de que las familias que intercambian de parcela sean vecinas?

El jueves plantearemos un nuevo desafío.

Un solo sitio de cruce

Un vecindario emprendedor