SOLUCIÓN D37º – Un solo sitio de cruce


Acceder desde AQUÍ.

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.

Solución de Pedro Correa: Demostración desafío 37

Solución de José Luis Miota: 37 Un vecindario emprendedor.Maito

2 comentarios

Archivado bajo OTROS

2 Respuestas a “SOLUCIÓN D37º – Un solo sitio de cruce

  1. Maito

    Me ha gustado el dasafío, y la solución oficial mucho más que la solución de la yenka que propuse. La exposición de presentación fue un poco pesada, pero la de la solución ha estado mucho mejor,.chapeau por Francisco Antonio González.

  2. Pedro Correa

    Pues a mí también me ha gustado, aunque el enunciado al principio parecía algo lioso.

    Maito, tu demostración no es de la yenka, es impecable.

    Entre 90 tampoco nos ha tocado a ninguno???

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s