Nacional 1995 Nivel 3 (P6)

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Dauphineg

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019
OFO - Medalla de Plata-OFO 2020 COFFEE - Mención-COFFEE Ariel Zylber OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022
Mensajes: 235
Registrado: Lun 20 Ene, 2014 1:26 am
Medallas: 9
Nivel: Exolímpico
Ubicación: La Plata, Prov. de Bs. As.

Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Dauphineg »

Se marcan los $27$ puntos $(a,b,c)$ del espacio tales que $a$, $b$ y $c$ toman los valores $0$, $1$ ó $2$. A estos puntos los llamaremos "coyunturas".
Utilizando $54$ varillas de longitud $1$ se unen entre sí todas las coyunturas que están a distancia $1$. Queda así formada una estructura cúbica de $2\times 2\times 2$. Una hormiga parte de una coyuntura $A$ y avanza a lo largo de las varillas; cuando llega a una coyuntura gira $90^\circ$ y cambia de varilla.
Si la hormiga regresa a $A$ y no ha visitado más de una vez ninguna coyuntura excepto $A$, a la que visitó $2$ veces, al iniciar el paseo y al finalizarlo, ¿Cuál es la mayor longitud que puede tener el recorrido de la hormiga?
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Armamos el grafo, con las coyunturas como vértices y las varillas como aristas, lo que nos pide el problema es encontrar un Ciclo Hamiltoniano, por lo que el problema es muy sencillo, ya que un Ciclo Hamiltoniano tiene exactamente la misma cantidad de aristas que de vértices, por lo que la mayor longitud se obtiene cuando recorre un Ciclo Hamiltoniano sobre el grafo completo, al tener [math] vértices, tendrá [math] aristas y por lo tanto la mayor longitud que puede tener el recorrido de la hormiga es [math].
♪♫ do re mi función lineal ♪♫
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por tuvie »

Gianni De Rico escribió:
Spoiler: mostrar
Armamos el grafo, con las coyunturas como vértices y las varillas como aristas, lo que nos pide el problema es encontrar un Ciclo Hamiltoniano, por lo que el problema es muy sencillo, ya que un Ciclo Hamiltoniano tiene exactamente la misma cantidad de aristas que de vértices, por lo que la mayor longitud se obtiene cuando recorre un Ciclo Hamiltoniano sobre el grafo completo, al tener [math] vértices, tendrá [math] aristas y por lo tanto la mayor longitud que puede tener el recorrido de la hormiga es [math].
Esta bien, y ¿como obtenemos eso?
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico »

tuvie escribió:
Gianni De Rico escribió:
Spoiler: mostrar
Armamos el grafo, con las coyunturas como vértices y las varillas como aristas, lo que nos pide el problema es encontrar un Ciclo Hamiltoniano, por lo que el problema es muy sencillo, ya que un Ciclo Hamiltoniano tiene exactamente la misma cantidad de aristas que de vértices, por lo que la mayor longitud se obtiene cuando recorre un Ciclo Hamiltoniano sobre el grafo completo, al tener $27$ vértices, tendrá $27$ aristas y por lo tanto la mayor longitud que puede tener el recorrido de la hormiga es $27$.
Esta bien, y ¿como obtenemos eso?
Uh. Entendí cualquiera.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Martín Vacas Vignolo »

Gianni De Rico escribió: recorre un Ciclo Hamiltoniano sobre el grafo completo
El grafo no es completo, sólo se unen los puntos que están a distancia 1, no todos con todos
[math]
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico »

Martín Vacas Vignolo escribió:
Gianni De Rico escribió: recorre un Ciclo Hamiltoniano sobre el grafo completo
El grafo no es completo, sólo se unen los puntos que están a distancia 1, no todos con todos
No me refería a eso, tendría que haber puesto "el grafo en su totalidad" o "sobre todo el grafo". Pasa que ahora tampoco estoy seguro de si se puede interpretar que se existe un CH sobre todo el grafo (en ese caso el problema es trivial) o si la idea era encontrar el mayor subgrafo tal que contenga un CH, que sería un problema bastante interesante.
♪♫ do re mi función lineal ♪♫
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 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
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por tuvie »

Asi de una no es trivial la relacion del problema con un grafo. Que el vertice [math] se conecte con [math] y [math] se conecte con [math] no quiere decir que se pueda hacer [math].
Gabriel Bernal

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 FOFO Pascua 2020 - Mención-FOFO Pascua 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 OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Plata-OFO 2022
Mensajes: 33
Registrado: Sab 10 Ago, 2019 12:37 pm
Medallas: 10

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gabriel Bernal »

Lo edité varias veces pero ahora sí.
Spoiler: mostrar
Es claro que la hormiga recorrerá como mucho $27$ varillas. Ahora dividamos la estructura en tres pisos de $9$ coyunturas (cada uno con coordenadas $(a,b,0)$; $(a,b,1)$; $(a,b,2)$) y al resto de varillas llamémoslas columnas. Por un lado la cantidad de columnas es par porque la hormiga debe volver siempre al piso de donde salió (cada vez que sale del piso donde está debe volver a él en algún momento). Por otro lado, veamos que hay $2$ varillas por coyuntura, por ende en cada piso habrá algunas coyunturas con una sola varilla en el piso y otra que es una columna, pero habrá una cantidad par de coyunturas que cumplan esto y en el caso que no sea así habrá $2$ varillas en el piso, en definitiva hay una cantidad para de varillas en cada piso. Sumando ambas varillas tenemos que la hormiga recorrió una cantidad par por lo que descartamos los casos impares.
Por otro lado veamos el cubo grande (el de $2x2x2$). Éste tiene $8$ vértices y $12$ aristas, cada una de ellas con su coyuntura. Cada vértice requiere $2$ varillas (simplemente porque pasa la hormiga) y ambas deben estar unidas a aristas (no hay otra conexión). Una arista está unida a dos caras del cubos y a dos vértices mediante un recorrido recto, pero esto está prohibido por la consigna, luego debe haber $12$ varillas asignadas a vértices que cubren como mucho $6$ vértices y $2$ quedan afuera del recorrido de la hormiga. Acá hay que contemplar el detalle de que la hormiga al llegar al punto donde inició puede hacer un recorrido recto, si es así habría $13$ varillas asignadas a vértices que cubren como mucho $6$ vértices. Esto hace que haya como mucho $25$ coyunturas en el recorrido de la hormiga.
Viendo la cota de $25$ y que para los impares no se puede, la cota es $24$. Acá un ejemplo (el punto rojo es donde empieza y termina la hormiga):
Captura.PNG
Al final, la mayor longitud que pudo tener el recorrido es $24$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
([{&}])
Mensajes: 17
Registrado: Sab 10 Jun, 2023 4:38 pm
Nivel: 2

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por ([{&}]) »

Spoiler: mostrar
Notar que es imposible un recorrido de dos varillas seguidas que estén en la misma dirección (es fácil de ver)(1).
Notar que la cantidad de movimientos en la dimensión que sea (atrás-adelante / arriba-abajo / derecha-izquierda) debe ser par ya que es un camino cerrado.
Por (1) es imposible hacer mas de 9 movimientos en una dirección.
Por (2) el máximo por dirección es 8.
Finalmente el máximo se define 8x3=24 (es posible)
Responder