El Viajero

Como comentó Brandon en este problema, hay que construir una gráfica. La gráfica que hay que considerar es la que se forma poniendo en el eje X a cada ciudad i en el punto $C_i$, de tal manera que la distancia de $C_i$ al origen sea exactamente la distancia que hay desde la ciudad cero a la ciudad i (pasando por la ciudad 1, 2, ..., i-1).

Luego, en el eje Y ponemos la cantidad de kilómetros que va rendir la gasolina del automóvil del turista. Luego, en este eje coordenado graficamos precisamente lo que va rendir la gasolina del automóvil en cada momento de su recorrido, un valor negativo de este rendimiento significa que le hace falta gasolina, pero sin embargo, dejaremos que pueda seguir avanzando a la siguiente gasolinería aunque tenga una cantidad negativa de gasolina.

Ahora bien, en cada ciudad, el rendimiento en kilómetro sube exactamente $K_i$ kilómetros, por lo que la gráfica brinca en esos puntos. Veamos entonces, más o menos la gráfica se vería así:

En la gráfica hemos dibujado los cambios en el rendimiento de la gasolina como líneas rectas. Cada centímetro que avanza debe perder exactamente ese rendimiento de centímetros. Por lo que, efectivamente, deben ser rectas pero además deben ser rectas de pendiente -1 (lo que avanza es exactamente lo que disminuye su rendimiento).

Ahora bien, en cada intervalo la función desciende exactamente la magnitud del intervalo. Por ello, en todo el recorrido desciende exactamente K (la distancia de $C_0$ a $C_n$), pero al mismo tiempo crece $K_i$ en cada punto $C_i$. Pero como $K_1+K_2+ \cdots + K_n = K$, se tendrá que lo disminuido y lo aumentado en todo el recorrido es igual, por ende, la gráfica terminár donde empezó. Por ello, en nuestra gráfica ejemplo, se observa que la gráfica regresa exactamente al cero.

Ahora bien, la ciudad donde debe empezar el viajero es la ciudad donde esta gráfica alcanza su valor mínimo. Si en dicha ciudad empieza con 0 gasolina, en el resto del camino jamás le faltará gasolina pues la gráfica siempre quedará por arriba. Y se puede ver que no hay problema después de $C_n$ ya que después de ese punto la gráfica se volverá a repetir exactamente igual, basta con recordar que en $C_n$ el rendimiento quedó exactamente igual como en $C_0$.

Con esto se concluye la demostración.