Ayuda de inducción... número de ciudades

Decimos que una ciudad$C_{k}$(no necesariamente único) con el número máximo de caminos que conducen a él, tiene la propiedad requerida.

Supongamos por el contrario que hay alguna ciudad$C_{j}$para que no haya camino que salga de$C_{j}$a$C_{k}$directamente o a través de una parada. Supongamos que hay exactamente$m$caminos que salen de$C_{j}$, a ciudades que no son$C_{k}$. Luego, para cada una de estas ciudades, los caminos tienen que salir de$C_{k}$a ellos también. Además, el camino entre$C_{k}$a$C_{j}$también tiene que salir de$C_{k}$a$C_{j}$. Así, tenemos al menos$m+1$caminos que salen de$C_{k}$, mientras que teníamos exactamente$m$caminos que salen de$C_{j}$. Esto da una contradicción al hecho de que$C_{k}$tiene el número máximo de caminos que conducen a él.

La respuesta de Aritro funciona y es más elegante, pero si debe usar inducción, hay una manera de hacerlo usando inducción fuerte.

etiquetar la ciudad$A_1, \dots A_n$, y supongamos$A_1$es la ciudad a la que se puede llegar desde cualquier otra ciudad pasando como máximo por otra ciudad. Y ahora agregamos$A_{n+1}$. Si el camino entre$A_1$y$A_{n+1}$lleva a$A_1$entonces hemos terminado. Así que ahora asumimos que el camino conduce a$A_{n+1}$.

dividir las ciudades$A_2, \dots, A_n$en tres categorías:

Categoría 1: las que conducen directamente a$A_{n+1}$.

Categoría 2: aquellos en los que$A_{n+1}$conduce a él, pero conduce a$A_1$

Categoría 3: aquellos en los que$A_{n+1}$conduce a él, y$A_1$también conduce a ella.

Obviamente desde la categoría 1 podemos llegar$A_{n+1}$fácilmente. Desde la categoría 2, también podemos llegar desde esa ciudad a través de$A_1$entonces a$A_{n+1}$.

Si la categoría 3 está vacía, entonces$A_{n+1}$es nuestra ciudad requerida, porque de todas las ciudades restantes ($A_1$, categoría 1 y categoría 2) podemos alcanzar$A_{n+1}$a lo sumo a través de otra ciudad.

Ahora asumimos que la categoría 3 no está vacía.

Caso 1: la categoría 3 contiene varias ciudades.

Invocamos la hipótesis de inducción una vez más, SOLO en ciudades de categoría 3. Hay una ciudad decir$B$que satisfaga la propiedad requerida entre las ciudades de categoría 3. Entonces afirmamos que$B$es nuestra ciudad requerida para todos$n+1$ciudades

Es decir, desde otras ciudades de la categoría 3, podemos llegar$B$a lo sumo a través de otra ciudad por la hipótesis de inducción. Desde ciudades de categoría 1, podemos llegar$B$a través de$A_{n+1}$. Desde ciudades de categoría 2, podemos llegar$B$a través de$A_1$.

Caso 2: la categoría 3 contiene una sola ciudad, digamos$B$. No podemos invocar la hipótesis de inducción porque la premisa requiere que haya al menos 2 ciudades, pero aún podemos afirmar que$B$es nuestra ciudad requerida. De cualquier otra ciudad ($A_1, A_{n+1}$, categoría 1 y categoría 2) podemos alcanzar$B$ya sea directamente o a través$A_1$o$A_{n+1}$.