Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
260 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

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

Envoyé par Enpassant 
Pirates, coffre au trésor, nb min de serrures
28 avril 2021, 18:56
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



Modifié 1 fois. Dernière modification le 28/04/2021 19:05 par Enpassant.
Re: Pirates, coffre au trésor, nb min de serrures
28 avril 2021, 19:26
Je ne suis pas sûr de comprendre. Quel est le rôle de $N~?$
Re: Pirates, coffre au trésor, nb min de serrures
28 avril 2021, 21:13
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
Re: Pirates, coffre au trésor, nb min de serrures
29 avril 2021, 12:11
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.
Re: Pirates, coffre au trésor, nb min de serrures
29 avril 2021, 19:36
Bonjour! Merci pour la réponse! Donc vous confirmez que c'est bien la solution minimale alors.

Bonne soirée
Re: Pirates, coffre au trésor, nb min de serrures
30 avril 2021, 17:41
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)
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 151 317, Messages: 1 537 834, Utilisateurs: 28 260.
Notre dernier utilisateur inscrit Nemoris.


Ce forum
Discussions: 2 612, Messages: 53 242.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page