Problema

Nivel de dificultad:
  • 5.5

Su valoración: No ha valorado al problema en un nivel de dificultad.
Una compañía tiene 2n+1 directivos.  Las reglas de la compañía requieren que cualquier mayoría (n+1 o más) de directivos pueda abrir la caja fuerte, pero que ninguna minoría (n o menos) de directivos la pueda abrir.  Se propone equipar la caja fuerte con  c cerrraduras, de tal manera que la caja fuerte sólo se pueda abrir cuando estén disponibles las llaves de todas las cerraduras, y dar a cada directivo un conjunto de llaves distintas.  

Cada directivo debe tener el mismo número de llaves. ¿Cuál es el mínimo número de cerraduras c con el que hay que equipar a la caja fuerte para que la anterior distribución sea posible? ¿Cuál es el número  l de llaves se darían a cada directivo en caso de utilizar dicho número mínimo de cerraduras?

Autor Tema: Un problema de olimpiada para divertirse  (Leído 1238 veces)

SilverDude

  • Miembro
  • *
  • Mensajes: 39
  • Would the future refuse to change...???
    • Ver Perfil
Un problema de olimpiada para divertirse
« : noviembre 03, 2008, 06:17:47 pm »
Una compañía tiene 2n+1 directivos.  Las reglas de la compañía requieren que cualquier mayoría (n+1 o más) de directivos pueda abrir la caja fuerte, pero que ninguna minoría (n o menos) de directivos la pueda abrir.  Se propone equipar la caja fuerte con  c cerrraduras, de tal manera que la caja fuerte sólo se pueda abrir cuando estén disponibles las llaves de todas las cerraduras, y dar a cada directivo un conjunto de llaves distintas. 

Cada directivo debe tener el mismo número de llaves. ¿Cuál es el mínimo número de cerraduras c con el que hay que equipar a la caja fuerte para que la anterior distribución sea posible? ¿Cuál es el número  l de llaves se darían a cada directivo en caso de utilizar dicho número mínimo de cerraduras?

La respuesta la posteo en un par de dias.  ;D

Saludos,
SilverDude
  8)
Aquel que ha decidido ante todo cumplir sus sueños, es alguien que aprendió lo más poderoso del mundo: La esperanza es la decisión de hacer posible lo imposible.

Mapache

  • (maestro)
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1881
  • "All your forum are belong to us." -Mc Pache
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #1 : noviembre 04, 2008, 11:43:15 pm »
¿lo muevo a combinatoria?

SilverDude

  • Miembro
  • *
  • Mensajes: 39
  • Would the future refuse to change...???
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #2 : noviembre 05, 2008, 06:55:50 pm »
Mapachux lo dejo a tu discreción, no estoy seguro de donde debería de ir el mensaje,así que por el teorema de la buena ordenación y el axioma de selección, decidí ponerlo en este thread. Jo Jo  ???
Aquel que ha decidido ante todo cumplir sus sueños, es alguien que aprendió lo más poderoso del mundo: La esperanza es la decisión de hacer posible lo imposible.

sergiomerida

  • Moderador Global (maestro)
  • Sr. Member
  • *****
  • Mensajes: 284
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #3 : noviembre 06, 2008, 03:03:20 pm »
Yo digo que si debería ir en la sección de combinatoria

esteban

  • (maestro)
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1044
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #4 : noviembre 08, 2008, 07:35:32 pm »
Solo un par de dudas

¿Puede un directivo tener dos llaves idénticas?

¿Puede una llave de un directivo ser idéntica a una llave de otro directivo?

Para un distribución de llaves y cerraduras que satisfacen las condiciones se define una cerradura como "cerradura inútil" si es tal que al removerla de la caja fuerte, el sistema sigue funcionando como se desea.
Una vez removidas todas las cerraduras inútiles de la caja fuerte, ¿puede la caja fuerte tener dos cerraduras idénticas?

:)

SilverDude

  • Miembro
  • *
  • Mensajes: 39
  • Would the future refuse to change...???
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #5 : noviembre 09, 2008, 12:35:58 pm »
Esteban,

¿Puede un directivo tener dos llaves idénticas?
Si.

¿Puede una llave de un directivo ser idéntica a una llave de otro directivo?
Si.

Para un distribución de llaves y cerraduras que satisfacen las condiciones se define una cerradura como "cerradura inútil" si es tal que al removerla de la caja fuerte, el sistema sigue funcionando como se desea.
Una vez removidas todas las cerraduras inútiles de la caja fuerte, ¿puede la caja fuerte tener dos cerraduras idénticas?

No. El objetivo de las cerraduras es que la mayoría puedan abrirlas, y aunque halla mas de una copia de cada llave cada cerradura es única.  :D

Saludos,
SilverDude
  8)
Aquel que ha decidido ante todo cumplir sus sueños, es alguien que aprendió lo más poderoso del mundo: La esperanza es la decisión de hacer posible lo imposible.

esteban

  • (maestro)
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1044
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #6 : diciembre 04, 2008, 11:49:34 pm »
jo jo si estaba divertido el problema
Spoiler (click to show/hide)




Mapache

  • (maestro)
  • Administrador
  • Hero Member
  • *****
  • Mensajes: 1881
  • "All your forum are belong to us." -Mc Pache
    • Ver Perfil
Re: Un problema de olimpiada para divertirse
« Respuesta #7 : diciembre 05, 2008, 12:34:48 am »
WOW Esteban... estoy plenamente confiado que se puede escribir de manera más corta la solución, pero no deja de ser ilustrativa la manera en la que la escribiste... ojhala la aprovechen los patógenos...

 


zzz