Pirates, coffre au trésor, nb min de serrures
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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
Bonne soirée
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)