Sel Cono - 1999 - P1

Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 31
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 6
Nivel: 1

Sel Cono - 1999 - P1

Mensaje sin leer por Felibauk »

En un reino hay $12$ ciudades. Entre ciertos pares de ciudades se crean enlaces de ida y vuelta de ómnibus, tren o avión. Hallar la menor cantidad de enlaces necesaria para que, si hay un paro de uno cualquiera de los tres medios de transporte, igual sea posible viajar desde cada ciudad a todas las demás ciudades.

Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años
Mensajes: 95
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 4
Nivel: 3
Ubicación: Córdoba, Córdoba

Re: Sel Cono - 1999 - P1

Mensaje sin leer por Tomás Morcos Porras »

Pregunta:
Spoiler: mostrar
Si hubiera $33$ enlaces, de manera que las ciudades queden conectadas por una única ruta, y la ruta para los tres medios fuera la misma, ¿se cumpliría la condición del enunciado? Al fin y al cabo, se puede viajar entre todas las ciudades y si para algún medio los otros dos pueden realizar la misma ruta. ¿"viajar de una ciudad a otra" necesariamente implica que haya un enlace por algún medio entre ambas ciudades?
¿Mis intereses? Las várices de Winston Churchill.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 1569
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 10
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Sel Cono - 1999 - P1

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
"Viajar de una a otra" significa que para cada par de ciudades $a,b$ hay una sucesión de ciudades $a=c_0,c_1,\ldots ,c_{n-1},c_n=b$ tales que hay un enlace entre $c_{i-1}$ y $c_i$ para $i$ desde $1$ hasta $n$.

En criollo, hay un caminito desde $a$ hasta $b$ que pasa por algunas ciudades en el medio.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 1002
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Sel Cono - 1999 - P1

Mensaje sin leer por Fran5 »

Spoiler: mostrar
Consideremos el problema cono un grafo de 12 vértices, y Consideremos a las aristas de tres tipos $O,T,A$. Para que haya solución, tiene que suceder que para todo Charly García parado en cualquier ciudad, pueda ir en Avión o Ómnibus a cualquier otra, ya que él no va en tren. Esto significa que las aristas $O,A$ son al menos $11$. Similarmente, vemos cotas para $O,T$ y $T,A$.

Demo de que son al menos $11$
Spoiler: mostrar
A cada ciudad tiene quebllegar al menos una linea. Luego como hay otras $11$ ciudades, hay al menos $11$ líneas
Luego $O+T+A \geq \frac{33}{2} > 16$. Luego debería haber alguna solución con $17$ tramos.

Notar que $17=6+6+5$

El ejemplo, (un galerazo?)
Spoiler: mostrar
no voy en tren voy en avion.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
2  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Responder