Acceder desde AQUÍ.
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.
Santiprofemates 
Puffff, pensaba reengancharme pero viendo el vídeo se me han quitado las ganas…
Al principio da bastante pereza este desafío, pero cuando te pones a él, no es tan difícil. A mí me ha recordado bastante al de las sillas, sólo que esta vez, se pueden «sentar» unos encima de otros.
Yo creo que este desafío se lee mejor que se ve. Dicho lo cuál, de momento no se me ocurre cómo atacarlo.
Creo saber la solución, pero no llego a poder demostrarla, quizás si de palabra pero no bajo cocneptos matemáticos.
Aunque tiene similitud con las sillas, el razonamiento no me lo parece.
Creo saber la solución, pero no llego a poder demostrarla, quizás si de palabra pero no bajo cocneptos matemáticos.
Aunque tiene similitud con las sillas, el razonamiento no me lo parece
Es de los que hay que leer un par de veces.
Encuentro una solución más lógica que matemática, y eso me lleva a extenderme un poco.
Si existe una solución sencilla, indicadlo por favor.
En efecto, se parece algo al de las sillas. Según como lo plantees creo que los primeros términos se comportan como una sucesión de dos elevado a n, los últimos no.
La idea es sencilla, pero hace falta explicarla bien.
Igual se parece también un poco al problema del reloj…
Pedro, lo del reloj creo que lo cojo, porque para el «no más de» creo que algo me apoyo en eso.
Para el «no menos de», iría bien encaminado si hablo de permutar?
Espero no ser muy explícito, alguien de vosotros va por un camino en el que al final inexorablemente se dan dos tipos de casos diferentes, xxxx e imxxx.
Creo que estamos yendo por caminos distintos. Aunque puede que los dos lleven a la solución.
¿se debe dejar siempre alguna parcela vacia obligatoriamente? El planteamiento inicial del problema parece indicarlo, ya que la reoorganizacion es para tener mas parques, etc…
Yo creo que es algo que despista, porque no es una condición que luego se imponga. De hecho, sí es posible reordenar a los vecinos en 20 parcelas, cumpliendo las condiciones. Si hubiesen sido otro número distinto, habría que verlo.
El vídeo no pude terminar de verlo, menudo lío arma con los cruces. Se nota que el que expone no es profesor.
Creo que he encontrado una solución demasiado fácil. Aún me falta concretar la demostración.
Hola!
Despues de ver el video 20 veces ya me he enterao!
Jabon ha encontrado una solucion imaginaria, que intriga,
yo, como Pedro, me he inclinado por el reloj.
Hasta el proximo!
Yo empecé con la del reloj, pero al final me he decantado por otra que además permitiría valorar el lugar de cruce (en función de una condición que se traduce en un círculo que puede ser vicioso, pero que tiene siempre un final). Sería válida incluso para un proyecto de 20 parcelas. Se basa en una simple cuestión de combinatoria.
Por otro lado permitiría afirmar que en una parcelación inicial de 25 solares, no se podría mantener un proyecto, como el exigido, en el que terminasen 25 parcelas.
Naturalmente, puede que haya ido por un camino equivocado, pero no le veo el fallo, por ahora.
Si no hay restricción de altura, una de las preguntas me parece un tanto trivial.
¿Seguro? Piensa que todos los vecinos deben moverse…
Si, todos, salvo uno, en la misma torre. Hay parcelas a montones para elegir.
No, todos todos deben moverse. Ninguno puede quedarse en la parcela en la que estaba. Es la tercera condición del enunciado…
A mí la única duda que me queda es si el señor que ha propuesto el problema ha salido de las propuestas de los lectores. Por cierto, de entre los topológicos (que me suelen dar algo de guerra, la verdad) éste no me ha gustado demasiado. Y como no tengo mucho tiempo y mi solución es susceptible de cierto pulimento, creo que no la enviaré. Total… igualmente no toca.
Topológico?? A mí me ha parecido totalmente algebraico…
Mi solución es topológica, y con notación al uso. Quizá por ello no me gusta, amigo Pedro, porque acaso me he ido por los cerros de Úbeda. Ahora bien, creo que si existe una solución más bonita que ninguna será topológica, pero eso ya se escapa a mis capacidades.
Es posible que haya varias respuestas, creo que es de los que se da para ello.
Y yo no tengo dudas de que ha salido de un lector. Se debe pasar bastante mal trago, al tener que presentar además el desafío. Estos de la organización son un poco masoquistas, por lo que se ve.
Si, por supuesto que habra varias formas, como ya es medianoche aqui va la mia:
Sea Po el vector con los indices inicialmente de las parcelas para
cada familia. Es decir la componente i de Po, sea Poi,
es la parcela que ocupa la familia i.
Sea Pf el vector tras la reorganizacion.
Las condiciones son:
-|Pfi-Poi| > 0 para todo i (cambio de parcela obligatorio)
-Si |Poi-Poi|<=1 entonces |Pfi-Pfi|<=1 (vecinos antes y despues)
-Un cruce se da cuando 2 vecinos i,j tal que |Poi-Poj|=1
tras el cambio intercambian parcelas: Poi-Poj=-(Pfi-Pfj)
Si todas las parcelas (T) estan ocupadas por al menos una
familia existe al menos una secuencia de T familias en
correspondencia biunivoca con las parcelas. Vamos a renombrar
a las familias de esta secuencia de acuerdo a la parcela
que ocupan i=1,2,3…T y sus parcelas correspondientes
Po1, Po2, Po3 … T = 1,2,3…T. La secuencia puede no ser
unica y el argumento a continuacion vale para todas
estas secuencias.
Tras la reorganizacion calculemos cuanto se desplaza
la familia i (sea este valor Di) con rlacion a la familia i-1:
Di=Pfi-Poi = Pfi-i = Pf(i-1)-(i-1)+Pfi -Pf(i-1)-1
Di=D(i-1)+ Pfi-Pf(i-1)-1
Osea una de tres: Di=D(i-1) o D(i)=D(i-1)-1 o D(i)=D(i-1)-2
Esto implica que siempre Di <= D(i-1) pues |Pfi-Pf(i-1)| Pfi-Pf(i-1) = -1
La condicion de cambio obligatorio en terminos de D es:
|Di| > 0
Para i=1 y T esto se traduce en:
D1>0
DT<0
Asi pues Di pasa de ser positivo para D1 a negativo
para DT. A la fuerza ha de existir k tal que D(k-1)=1 y Dk=-1
pues si Di=0 violaria el cambio de parcela y el salto maximo de D es 2.
Como Di <= D(i-1) para todo i podemos decir que D es una funcion
monotona decreciente y el 0 solo se puede cruzar una vez.
La solucion al problema es que solo puede haber un sitio
de cruce, un ejemplo de reorganizacion ocupando solo 2 parcelas es:
Parcela 1: BC
Parcela 2: ADEFGHIJKLMNOPQRSTUVWXYZ
Rogelio, ahora sólo hace falta saber cuál será la oficial. Me temo que va a haber muchas más variantes. Yo tenía una primera que era todo pura lógica, pero no me terminaba de convencer. Luego estará el tema de las que se consideran correctas.
Tengo curiosidad por la oficial.
Desde luego este les va a costar sudor!!
La mía es básicamente como la tuya.
Supongo que no existe ningún punto de cruce. En ese caso, las familias de la primera parcela deben estar en la segunda o más a la derecha, los de la segunda, en la tercera o más a la derecha, los de la tercera, en la cuarta o más a la derecha… y llego a que los de la 20 deberían estar fuera de las parcelas (en tu caso, D(k)>0 para todo k). Por cierto, yo no uso para nada la función D monótona creciente, pero que sepas que me encanta.
Sin embargo, en tu demostración echo en falta el análisis sobre qué pasa con familias que coinciden inicialmente en la parcela con las que has seleccionado que coinciden biunívocamente con las parcelas en el momento inicial. Está claro que para esas familias D(pi’) = D(pi) más menos uno, y que por tanto, es imposible que exista otro punto de cruce n (tal que D((pn-1)’)=1 y D(pn’)=-1 con n distinto de k), pero creo que haría falta explicitarlo.
Hola Pedro,
totalmente de acuerdo, se me paso. Vaya, y en esta ocasion solo hubo 90 acertances, la probabilidad era optima…
me alegra que te guste D!
la mía
Planteamos primero el caso, como si sólo hubiese un vecino por parcela inicialmente. Nos fijaremos en los “m” vecinos que ocupaban los lugares donde están ahora las “m” casas nuevas porque son los únicos que pueden cruzarse. Éstos deben reagruparse entre 2 y “m” casas siempre consecutivas, de otro modo nunca cumplirían con el proyecto (en “una” estaría también el anterior dueño y si se interrumpe la secuencia, indica que se ha perdido vecindad). Si el número de casas que ocupan esos “m” vecinos, es realmente menor de “m”, volveríamos a decir que “n” vecinos tienen que repartirse entre esas “n” casas, y así sucesivamente.
De ese modo siempre se va a acabar en que “x” vecinos deban ocupar “x” casas consecutivas (hasta el límite de 2, en 2 casas, porque “uno” en “una”, la misma, haría inviable el proyecto), es decir, al final se debe producir una “permutación” tal como se conoce en combinatoria.
Al hacer las diferentes permutaciones de un grupo de elementos iniciales nos encontramos con estas situaciones:
– Si son un número “par” de elementos, la única permutación que permite conservar vecindad es la que se originaría de hacer un eje de giro entre los dos elementos centrales de los implicados (ej: de 123/456 tendríamos 654/321) luego habrá un cruce, obligatorio entre “3” y “4” los elementos centrales).
– Si son un número “impar” de elementos a “permutar”, no sería posible validar el proyecto porque cualquier permutación impide mantener a todos los vecinos junto a sus vecinos, y la que se deriva del giro del caso anterior inmoviliza a la casa central, que permanece en su sitio, siendo proyecto no válido (12345 a 54321).
En los casos de parcelas con viviendas múltiples, se consideraría el grupo de viviendas (una de cada bloque inicial) que constituya una permutación “par” de elementos consecutivos. En estos casos, para no errar, lo ideal es llamar a las viviendas 1A, 2B, 2C, 3D, etc., de esta manera identificamos rápidamente una secuencia de números consecutivos, para operar de la forma detallada anteriormente.
Analicemos el ejemplo del video, con estos argumentos. El nuevo edificio se ubica entre las antiguas parcelas K y P/Q (si se prefiere 8K a 13P/13Q). Luego sólo puede haber un cruce entre esas letras. Vemos que están agrupadas esas letras entre las antiguas K y N luego sólo las letras de este intervalo pueden cruzarse. Hemos llegado al final porque hay 4 letras para 4 espacios, número par y permutación. Haremos el giro de KL/MN, acabando en NM/LK, han tenido que cruzar L y M, por fuerza. Comprobamos el caso, y en efecto, ese ha sido el cruce.
Este procedimiento nos permite por lo tanto, entre otras cosas:
– Identificar un lugar de cruce y anticiparlo en determinados supuestos.
– Comprobar si un proyecto no es correcto, si se ve que al final se llega a una permutación impar.
– Facilitar la creación de nuevos proyectos.
– Probar que un proyecto inicial de N casas, puede convertirse en otro de N casas, sólo si N es par, se trataría simplemente de una nueva numeración en sentido contrario. Por ejemplo un proyecto de 21 parcelas, no podría nunca terminar siendo de 21 nuevas, porque la parcela 11 se mantendría en esa inversión.
– No puede haber más de un cruce.
Un cruce implica que un vecino de la derecha “retrocede” y otro de la izquierda “avanza”. Ello obliga a que los vecinos de la derecha se muevan retrocediendo todos como mínimo una parcela, para seguir la vecindad, eso quiere decir que entre ellos no se producirá un cruce en ningún caso porque todos siguen el mismo movimiento. Lo mismo podríamos decir del otro lado que avanza.
Y por otro lado entre los de la derecha y los de la izquierda (de los que ya han hecho el cruce inicialmente), aún en el supuesto de que intercambiasen sus parcelas, nunca se podría hablar de cruce en el sentido que impone el desafío, porque inicialmente no habrían sido vecinos, habrían saltado más de dos parcelas.
Coloread en azul las viviendas que se desplazan a la derecha. Coloread en rojo las viviendas que se desplazan a la izquierda. Observad dónde se encuentran los colores.
A mi me gusta la explicación de Jorge, que he visto en el foro del país:
“La respuesta es uno: mínimo y máximo. Basta darse cuenta de que los vecinos de cada bloque se desplazan, o bien hacia la derecha, o bien hacia la izquierda. No puede ser que, si en una parcela hay dos viviendas cada uno vaya para un lado, pues en ese caso, hay vecinos que dejarían de serlo. Así, ponemos debajo de cada bloque una flecha, indicando derecha o izquierda. Por ejemplo, los de la parcela 1 han de ir hacia la derecha, y los de la 20, hacia la izquierda. En algún sitio habrá un cambio de sentido en las flechas, en las parcelas n, y n mas 1. Ese es un sitio de cruce, pues las flechas se apuntan una a la otra, y debe conservarse la relación de vecindad. Y es el unico posible: si hubiera otro cambio de sentido en las flechas, habría dos flechas que apuntarían en sentidos opuestos, lo cual implicaría que los vecinos de dos parcelas contiguas dejarían de ser vecinos.”
A la vista de las soluciones que dais, este desafio me venia grande. Que le vamos a hacer.
Me encanta la solucion oficial de la gráfica, y esa si que estaba a mi nivel si se me hubiera ocurrido.
Divagante, la tónica es que después de un desafío difícil, viene una fácil. No son tan perversos los organizadores como pensamos.
Ha sido un desafío bonito y una respuesta bonita; y además permitía variedad de ellas, alguna de lógica pura.