¿Habrá otra solución para este ejercicio?
Hola! La pregunta es la siguiente: Un cuadrado de 3x3 se ha dividido en cuadraditos de lado 1. Una hormiga sale del punto A, camina por las líneas de la cuadrícula y llega a B (A y B se encuentran en los vértices opuestos del cuadrado de 3x3). Los únicos puntos por los que puede pasar más de una vez son los vértices de los cuadraditos. ¿Cuál es la máxima longitud que puede tener el camino de la hormiga? He hecho muchas este ejercicio y encontré que la longitud máxima es de 18 de un total de 24 (24 es la cantidad ideal o máxima). Pero esta respuesta no sería muy seria para mi profesor jajaja. Así que comencé a ver si existía una relación entre el lado de un cuadrado y la longitud máxima que podía lograr... Primero hice un cuadrado de 1x1, osea que la cantidad máxima o ideal que podría pasar sería de 4, pero como esta cantidad no se podría al pasar solo una vez por cada linea, el camino mas largo sería de 2. Luego encontré que la diferencia entre la cantidad máxima y el camino mas largo encontrado sería 4-2=2. Ahora tomaré un cuadrado de 2x2, osea podría pasar idealmente por 12 unidades, pero haciendo el camino mas largo encontrado llegue a que la mayor trayectoria es de 8. Haciendo nuevamente la diferencia 12-8=4. Luego con el cuadrado de 3x3 tenia que la cantidad ideal era 24, pero podía pasar cumpliendo con la condiciones por 18 unidades, luego la diferencia es 24-18=6. Con un cuadrado de 4x4 me queda lo siguiente: 40-32=8 y con un cuadrado de 5x5 me queda 60-50=10. Finalmente llego a que existe una relación entre la diferencia entre el máximo camino y el de la máxima trayectoria con las condiciones, esta relación es 2n (con n lado del cuadrado). Ademas encontré la relación para la cantidad ideal respecto al lado del cuadrado y esta es 2n^2+2n. Lo que encontré al final es que 2n^2+2n-(2n)=máxima trayectoria= 2n^2. En particular en el cuadrado de 3x3 me quedaría que la máxima trayectoria sería 2x(3^2)=18, lo que concuerda con lo que encontré...ahora lo malo es que le pregunte a mi profesor y me respondió que encontraba que la respuesta no era lo que el quería, que no estaba del todo justificada mi respuesta, es por eso que recurro a ud para ver si me puede ayudar con algo para resolver de mejor forma mi ejercicio. De ante mano gracias!! Saludos cordiales...
1 Respuesta
Hallamos primero la distancia de los caminos., la que llamas ideal, pero que es imposible completarla sin repetir tramos de camino
Si el cuadrado tiene n casillas en cada lado, cada línea horizontal o vertical de lado a lado mide n. Y el número de lineas verticales es n+1 y el de horizontales n+1 también. Luego son 2(n+1) tramos de longitud n. Asi que la suma de caminos mide 2n(n+1).
Llamaré aristas a los lados de los cuadraditos.
Vemos que en la cuadrícula hay vértices donde confluyen dos aristas (los puntos A y B), vértices donde confluyen tres aristas (los otros vértices exteriores) y vértices donde confluyen 4 aristas (los interiores).
Cada vez que pasamos por un vértice entramos por un arista y salimos por otra. Luego por los vértices de 2 y 3 aristas solo puede pasarse una vez y por los de 4 aristas dos veces.
Aparte, los vértices A y B son principio y final, eso significa que no podemos pasar por las dos aristas que tienen, ya que si lo hiciéramos por el A nos quedaríamos atrapados sin continuación y en el B cuando se pasa una vez ya se ha terminado y la otra arista se queda siempre sin recorrer.
Si damos un nombre a cada vértice y escribimos por cada uno que pasamos tendremos algo asi:
A, x2, x3, x4,...xm, B
En los vértices intermedios solo podrán aparecer una vez los de dos o tres aristas y dos veces los de cuatro aristas.
Hay 4 de dos aristas (A y B incluidos)
Hay 4(n-1) de tres aristas
Hay (n-1)^2 de cuatro aristas
Lo verificamos
4+4(n-1)+(n-1)^2 = 4+4n-4+n^2+1-2n =1+n^2+2n = (n+1)^2
Está bien, ese el el número total de vértices.
Entonces la cadena puede tener a lo sumo esta cantidad de elementos
4+4(n-1)+2(n-1)^2 =
4+4n-4+2n^2+2-4n =
2n^2 + 2
La longitud es el número de elementos menos 1, luego la longitud máxima que se puede recorrer es:
2n^2+1
Eso es un acotación, pero no quiero decir que tenga que llegarse a ella, de hecho tu has hecho muchas pruebas y te has quedado a uno de ella. Seguramente habrá una explicación de porque no se pueden recorrer las 2n² + 1 pero ahora no la encuentro.
Te mando esto de todas formas por si te puede servir. Dime si eres estudiante de topología o si en qué estudios te ha aparecido el problema para así saber hasta que punto nos pueden exigir. No obstante al ser el problema referido solo al cuadrado de 3x3 quizá no haga falta tanta teoría y ponerse a probar y probar, pero no tengo papel cuadriculado para hacer pruebas.
Muchas gracias! yo soy estudiante de Física y matemática y estos ejercicios nos los da un profesor de un ramo de matemática y son ejercicios de olimpiadas de matemática de américa. Me ha quedado bastante claro a lo que se refiere en su planteamiento, asi que seguiré con este razonamiento a ver si puedo llegar a la solución que quiere mi profesor. Agradezco mucho su tiempo y ayuda. Saludos cordiales!!!!
