Problemas planteados por Paenza

Ideas sobre algunos de los problemas que plantea Adrián Paenza en el programa "Científicos Industria Argentina" 

El sitio web del programa es http://www.cientificos.arnet.com.ar/. Ahí pueden verse los problemas (ellos los llaman "cuentos" porque a veces no son problemas :-). El programa lo dan los días lunes a las 19 hs por Canal 7.

Problema planteado el lunes 18 de junio de 2007

Descripción

Cuatro personas (A, B, C y D) deben cruzar un puente de noche. Como el puente es muy antiguo, solo pueden cruzar dos a la vez y, como el cruce es peligroso por el deterioro del puente, deben llevar con ellos en cada viaje la única linterna que poseen. El tiempo que tarda cada persona en cruzar es idéntico tanto a la ida como a la vuelta y son los siguientes:

  • A: 1 minuto;
  • B: 2 minutos;
  • C: 5 minutos;
  • D: 10 minutos.

En cada cruce de un grupo de 2 personas se demora lo que tardaría la persona más lenta del grupo.

El problema consiste en ver si es posible realizar el cruce en menos de 17 minutos.

[Poner el link al video cuando lo encuentre...]

Solución

En primer lugar podemos observar que se realizan 3 viajes de ida, cada uno de 2 personas, y solo 2 de vuelta, siempre unipersonales. Veamos porqué esto es así. Para identificar a las personas que cruzan en cada viaje llamaremos 1a a una persona que cruza en el primer viaje de ida y 1b a la otra persona que cruza en ese viaje (1b puede o no existir, recordemos que pueden cruzar una o dos personas). En forma similar llamaremos 2a y 2b a las que cruzan en el primer viaje de vuelta y así sucesivamente.

  • Primer viaje de ida: tienen que ir dos, ya que si va uno solo, tiene que volver con la linterna y estamos como empezamos.

  • Primer viaje de vuelta: tiene que volver uno solo con la linterna porque, si volvieran los dos que cruzaron, estaríamos como al principio, con mayor tiempo transcurrido solamente. Supongamos, sin pérdida de generalidad, que 2a = 1b.

  • Segundo viaje de ida: podrían hacerlo dos o una. Pero, si lo hiciera una sola, estaríamos en la misma situación que si 3a y 1a hubieran cruzado juntas y con un mayor tiempo transcurrido (max{t1a,t3a}<t1a+t3a). Por lo tanto, deben cruzar dos. La situación en este momento son 3 personas (1a, 3a y 3b)  con la linterna en la costa 2 y una persona que queda en la costa 1.

  • Segundo viaje de vuelta: como queda solo uno en la costa 1, la idea es "ir a buscarlo" con la linterna. Podrían ir dos, pero entonces tendríamos 3 personas en la costa 1 y la misma situación podría haberse alcanzado al final del primer viaje de vuelta (haciendo que 1a sea la que no es ninguna de esas 3) y con menor tiempo total (max{t1a,t1b}+t1b<max{t1a,t1b}+t1b+max{t3a,t3b}+max{t4a,t4b}). Por eso debe volver uno solo, 4a.

  • Tercer y último viaje de ida:  no hay forma más rápida de terminar los viajes que hacer  que los dos crucen ahora.

Puede verse que C y D no pueden viajar de ida separados, ya que entonces sus viajes de ida insumirían 15 minutos que, sumados a otros dos viajes de ida mínimos y los dos viajes de vuelta mínimos, nos daría un tiempo total >15+1+1+1+1=19 minutos. Si cruzaran juntos en el último viaje, 4a debería ser C o D y, por lo tanto, tendríamos un tiempo total mínimo >1+1+1+5+10 = 18 minutos. Tampoco pueden cruzar juntos en la primera oportunidad, ya que entonces tendríamos que 2a es C o D y el tiempo mínimo de cruce sería >10+5+1+1+1=18 minutos. Por lo tanto, C y D deben cruzar en el segundo viaje de ida.

Esto implica que en el primer viaje de ida deben cruzar A y B. Ahora se nos abren dos posibilidades:

  • 1a = A o
  • 1a = B.

Supongamos que 1a = A. Entonces 2a = B y tenemos una sola opción para 4a: A, ya que si vuelve C o D tenemos un tiempo >2+2+10+5+5=24 minutos! Por lo tanto tenemos como solución óptima con esa suposición:

  • primer viaje de ida: cruzan A y B;
  • primer viaje de vuelta: cruza B;
  • segundo viaje de ida: cruzan C y D;
  • segundo viaje de vuelta: cruza A;
  • tercer viaje de ida: cruzan A y B.

Esto nos da un tiempo total de 2+2+10+1+2 = 17 minutos.

Si ahora suponemos 1a = B, podemos hacer un idéntico razonamiento y llegar a:

  • primer viaje de ida: cruzan A y B;
  • primer viaje de vuelta: cruza A;
  • segundo viaje de ida: cruzan C y D;
  • segundo viaje de vuelta: cruza B;
  • tercer viaje de ida: cruzan A y B.

Esto nos da  un tiempo total de 2+1+10+2+2 = 17 minutos.

Por lo tanto no es posible cruzar en menos de 17 minutos.

Problema planteado el lunes 2 de julio de 2007

Descripción

Supongamos que la temperatura es una función continua de la posición en la Tierra. Probar que siempre existe en la Tierra un punto tal que tiene  la misma temperatura que su antípoda.

Solución

Tomemos un punto cualuiera de la Tierra. La temperatura de dicho punto respecto de su antípoda solo puede ser:

  • mayor,
  • menor o
  • igual.

Si son iguales ya encontramos el punto buscado. Si la temperatura del punto elegido es menor que la de su antípoda, podemos elegir en lugar de él a su antípoda y esto nos garantizará que el punto elegido siempre tiene temperatura mayor que la de su antípoda (el ser antípoda es una relación simétrica). Si llamamos T1 a la temperatura del punto elegido y T2 a la de su antípoda, tenemos entonces T1 > T2.

Pensemos en un camino cualquiera desde el punto elegido a su antípoda (por ejemplo, podría ser un camino por el círculo máximo que incluye a ambos). Si graficamos la temperatura en función del avance en el camino obtendremos un gráfico como el siguiente

[Insertar gráfico de la temperatura al viajar a la antípoda]

Obviamente la forma del gráfico intermedia puede ser arbitraria, pero la temperatura al inicio debe ser T1 y al final, T2. Si realizamos el gráfico de la temperatura de la antípoda de  cada punto por el que pasamos al realizar el recorrido anterior tendremos

 [Insertar gráfico de la temperatura de la antípoda instantánea al viajar a la antípoda]

Nuevamente la forma en el medio del es arbitraria (y arbitrariamente diferente del gráfico anterior, ya que no se recorren los mismos puntos). Sin embargo, la temperatura al inicio debe ser T2 y al final, T1.

[Insertar grafico superpuesto] 

Si consideramos que T1 > T2, es intuitivamente obvio que habrá al menos un punto en el viaje donde la temperatura será igual a la de su antípoda. Formalmente esto puede demostrarse tomando la diferencia entre ambas funciones del recorrido y aplicando el Teorema de Bolzano.