Un vecindario emprendedor

Francisco Antonio González, desarrollador informático de Indra en San Fernando de Henares (Madrid), presenta el segundo desafío propuesto por los lectores, el 37º con el que celebramos el centenario de la Real Sociedad Matemática Española. Manda tu solución antes de las 00.00 horas del martes 29 de noviembre (medianoche del lunes, hora peninsular española) al correo problemamatematicas@gmail.com y participa en el sorteo de una biblioteca matemática como la que cada domingo distribuye EL PAÍS en el quiosco.

A continuación, para aclarar las dudas y en atención a nuestros lectores sordos, añadimos el enunciado del problema por escrito.

El pueblo de Bolci solo tiene solo una calle y su terreno se divide en 20 parcelas alineadas y numeradas como se muestra en la figura 1. En esas parcelas, viven 26 familias que hemos nombrado con letras desde la A a la Z. Diremos que dos familias del pueblo son vecinas cuando vivan en la misma parcela (como ocurre con E y G) o cuando vivan en parcelas adyacentes, (como ocurre con D y G).

Debido al estado de deterioro de las casas, los habitantes de Bolci han decidido derribar sus viviendas actuales y construir una manzana de pisos que ocupará unas pocas parcelas. El resto del terreno lo habilitarán para zonas verdes, comercios y otros servicios para lograr un pueblo más moderno, habitable y ecológico. No se conoce aún donde estarán los pisos, ni cuantas viviendas habrá en cada edificio. Tampoco se sabe cómo los ocuparán las familias. pero los habitantes del pueblo han acordado que en el nuevo proyecto se deben respetar las tres condiciones siguientes:

1.- Respetar las divisiones parcelarias: Cada vivienda nueva debe estar completamente ubicada dentro de alguna de las primitivas parcelas.

2.- Mantener la vecindad: Las familias que ahora son vecinas deben seguir siéndolo cuando se trasladen a su nueva vivienda. Se puede tener también nuevos vecinos, pero los viejos hay que mantenerlos.

3.- Cambiar obligatoriamente de parcela: Ninguna familia puede mantenerse en su parcela inicial, todas deben cambiar de número de parcela.

Solo si se cumplen esas tres condiciones podremos decir que un proyecto es válido como, por ejemplo, el que muestra lafigura 2. Fijémonos que en el ejemplo que damos se da una circunstancia curiosa: Las familias vecinas L y M siguen estando en las parcelas 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 cada proyecto, llamaremos sitio de cruce a dos parcelas que tienen al menos dos familias vecinas que intercambian entre sí el número de parcela que tenían en la distribución original.

Y el desafío de la semana consiste en determinar la cantidad mínima y máxima de sitios de cruce que puede llegar a tener un proyecto válido. En la respuesta, debéis indicar el valor mínimo y el valor máximo, aportar al menos un proyecto de ejemplo de cada caso, y señalar las razones que garantizan que no hay posibilidad de construir proyectos válidos con una cantidad de sitios de cruce fuera de ese rango.

DESAFÍOS ANTERIORES Y SUS SOLUCIONES