Práctico 9 - Ejercicio 6

Práctico 9 - Ejercicio 6

de Marco Liguori Hernandez -
Número de respuestas: 4

¡Buenas!

Quería consultar sobre la solución presentada para este ejercicio en las soluciones del P9. 

El mismo prueba lo requerido usando el principio del palomar. Hace una cuenta en base a 4 posibles caminos que se pueden dar uniendo vértices de los dos caminos simples de máxima longitud. 

Las longitudes de los posibles caminos son:

 long(C1) = i + a + (k - j)

long(C2) = i + a + j

long (C3) = k - (i - 1) + a + j

long (C4) = k - (i - 1) + a + (k - j)

Sumando estos 4 tenemos i+a+(k−j)+i+a+j+(k−(i−1))+a+(k−j)+(k−i+1)+a+j = 4a + 4k +2. 

Las dudas serían: 

1) ¿Por qué no aparece el 2 en la suma solución?

2) ¿Por qué resta 1 a i cuando el camino comienza en vk?

¡Desde ya muchas gracias!

En respuesta a Marco Liguori Hernandez

Re: Práctico 9 - Ejercicio 6

de Matías Valdés -
Buenas.

2) Creo que hay un error en la solución al contar el largo del siguiente camino: v_k, v_{k-1}, \ldots, v_{i+1}, v_i . A mi entender la cantidad de vértices de este camino es: (k + 1) - i   (*). Con esto la cantidad de aristas sería uno menos: k - i . Capaz quien escribió la solución confundió la cantidad de vértices con la de aristas, que era lo que le interesaba contar.

1) Si lo que digo arriba es correcto, entonces la suma pasa a ser 4a + 4k, que es el valor que termina usando.

Saludos.

(*) Mi razonamiento para llegar a esta cantidad de vértices es el siguiente: el camino v_0, v_{1}, \ldots, v_{i-1}, v_{i}, v_{i+1}, \ldots, v_k tiene k+1 vértices (porque va de cero a k ). Si le saco el tramo v_0, v_1, \ldots, v_{i-1} , le estoy sacando (i-1) + 1 = i vértices (el más uno es porque inicia en cero).
En respuesta a Matías Valdés

Re: Práctico 9 - Ejercicio 6

de Marco Liguori Hernandez -
Matías,

Entiendo lo que decís. Es cierto que debería estar contando aristas. Dicho eso, ¿por qué la longitud del camino x1,x2,...,xa = a? ¿No debería ser a-1?

Saludos.
En respuesta a Marco Liguori Hernandez

Re: Práctico 9 - Ejercicio 6

de Matías Valdés -
Sí, la longitud del camino x_1, x_2, \ldots, x_a es a - 1 (porque tiene a vértices).

Pero al unirlo con el tramo anterior, se agrega una arista más. Esto es: el camino v_i, x_1,x_2,\ldots, x_a tiene largo a (porque tiene a+1 vértices )

Si te complica contar el largo de a tramos, y a eso agregarle las aristas de cada unión de los tramos, podés sumar el total de vértices de todos los tramos, y a eso restarle uno.

Saludos.