Pirates, coffre au trésor, nb min de serrures

Enpassant
Enpassant
dans Fondements et Logique
Bonjour à tous,

J'avais lu dans un livre le problème (assez classique?) suivant : une bande de N pirates a stocké son trésor dans un coffre à munir d'un certain nombre de serrures. Ils veulent que n'importe lequel groupe de n pirates puisse ouvrir le coffre, mais que n'importe lequel groupe de n-1 pirates ne puisse pas l'ouvrir. Quel est le nombre minimal de serrures PN,n pour remplir leur voeu? Par exemple P3,2=3 et on donne les clefs des serrures 1 et 2 au pirate n°1, 1 et 3 au pirate n°2 et 2 et 3 au pirate n°3 : un seul pirate ne peut rien ouvrir mais deux d'entre eux le peuvent. Personnellement, après tâtonnements je dirais qu'avec $\binom{N}{n-1}$ serrures, cela fonctionne, mais je ne sais pas si c'est le nombre minimal. Je pense que oui, mais n'en suis pas sûr. Quelqu'un a-t-il une idée sur la question s'il vous plaît?

En vous remerciant

Réponses

  • rebellin
    rebellin
    Je ne suis pas sûr de comprendre. Quel est le rôle de $N~?$
  • Enpassant
    Enpassant
    Bonjour

    C'est l'effectif de la bande de pirates. Par exemple, un groupe de 4 pirates (N=4) peut décider :
    a) qu'il faut que les 4 pirates soient là pour pouvoir ouvrir le coffre (n=4) -> 4 serrures, le pirate n°1 a la clé n°1, etc.
    b) qu'il faut 3 pirates pour ouvrir le coffre (n=3) : 6 serrures :
    -le pirate n°1 prend les clés 1, 2 et 3,
    -le pirate n°2 prend les clés 1, 4, 5
    -le pirate n°3 prend les clés 2, 4, 6
    -le pirate n° prend les clés 3, 5, 6
    c) qu'il faut 2 pirates pour ouvrir le coffre (n=2) : 4 serrures :
    -le pirate n°1 prend 1, 2, 3
    -le pirate n°2 : 1, 2, 4
    -le pirate n°3 : 1, 3, 4
    -le pirate n°4 : 2, 3, 4
    d) que n'importe quel pirate peut ouvrir le coffre (n=1) : 1 serrure, chaque pirate a la clé.
    La formule combinatoire fonctionne bien, mais est-on sûr que l'on ne peut pas faire mieux? Ici, je pense que oui, mais si N et n augmentent, je ne suis pas totalement sûr

    Bonne soirée
  • Pea
    Pea
    A tout ensemble de n-1 pirates, tu associes une serrure dont aucun n'a la clé. Cela définit une injection de l'ensemble des groupes de n-1 pirates dans l'ensemble des serrures. Il y a donc forcément au moins $\binom{N}{n-1}$ serrures. Réciproquement, si on a une bijection entre l'ensemble des groupes de n-1 pirates et l'ensemble des serrures, on donne à un pirate les clés de toutes les serrures associées aux groupes de n-1 pirates qui ne le contiennent pas.
  • Enpassant
    Enpassant
    Bonjour! Merci pour la réponse! Donc vous confirmez que c'est bien la solution minimale alors.

    Bonne soirée
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bonjour.

    Bof. vous faites un raisonnement qui ressemble à la méthode Coué. Quand vous aurez répété suffisamment de fois vos arguments, vous en serez convaincus. Je ne sais pas ce qu'est une clé, ni une serrure. N'est-il pas envisageable d'imaginer un système dans lequel les combinaisons des clés sont suffisamment spécifiques pour n'ouvrir qu'un coffre ?

    Un exemple : en guise de clé, pour 5 pirates, on donne le rang d'un chiffre dans un nombre binaire. Les combinaisons des clés, en fonction de leur présence (1) ou leur absence (0), ouvrent les coffres suivants :
    00000
    00001
    00010
    00011
    ...
    11110
    11111
    Soit 32 coffres.

    Nombre minimum de clés : 5 (soit N)
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 18

Dombiguine_equationmanutroisquayan2 +13 Invités