Nacional 1995 Nivel 3 (P6)

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

OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 115
Registrado: Lun 20 Ene, 2014 1:26 am
Medallas: 5
Nivel: Exolímpico
Ubicación: La Plata, Prov. de Bs. As.

Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Dauphineg » Lun 30 Ene, 2017 2:04 am

Se marcan los 27 puntos [math] del espacio tales que [math], [math] y [math] toman los valores 0, 1 o 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 2x2x2. Una hormiga parte de una coyuntura A y avanza a lo largo de las varillas; cuando llega a una coyuntura gira 90º 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 OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico » Lun 29 May, 2017 7:19 pm

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].
Queda Elegantemente Demostrado

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado FOFO 7 años - Jurado
FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 594
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 10
Nivel: Exolímpico

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por tuvie » Lun 29 May, 2017 7:50 pm

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 OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico » Lun 29 May, 2017 8:18 pm

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 [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?
Uh. Entendí cualquiera, estoy medio perdido últimamente.
Queda Elegantemente Demostrado

Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 400
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 » Mar 30 May, 2017 11:32 am

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 OFO - Medalla de Oro
Mensajes: 1064
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por Gianni De Rico » Mar 30 May, 2017 12:12 pm

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.
Queda Elegantemente Demostrado

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado FOFO 7 años - Jurado
FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 594
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 10
Nivel: Exolímpico

Re: Nacional 1995 Nivel 3 (P6)

Mensaje sin leer por tuvie » Mar 30 May, 2017 2:04 pm

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].

Responder