Le coffre du trésor

[Archi3]

Un roi très riche demande à son maitre serrurier de lui confectionner un coffre muni d'une porte très solide avec un certain nombre de serrures , pour garder son trésor (immense bien sur).

Par sécurité, il ne confiera les clés qu'aux 5 membres les plus surs de sa garde, mais pour encore plus de sécurité, il faudra qu'il y en ait 3 simultanément présents pour ouvrir les serrures, chacun n'ayant qu'une partie des clés. Ca ne marchera pas en dessous de 3, en revanche, n'importe quelle équipe de 3 peut ouvrir le coffre.
Quel est le nombre minimal de serrures que le maitre serrurier doit mettre ?
Combien de clés doit avoir chaque membre de la garde ?
-----

[Tryss2]

 Cliquez pour afficher

Il faut au moins 10 serrures.

En effet,
- chaque couple de garde doit avoir au moins une clé manquante
- deux couples de gardes différents (AB et AC sont deux couples différents) ne peuvent pas avoir la même clé manquante, sinon il existera un groupe de 3 qui ne pourra pas ouvrir toutes les serrures

On peut représenter la situation sous la forme d'un graphe complet à 5 sommets (un pentagramme si vous préférez ). Les sommets sont les gardes, et on attache sur chaque chaque arrête la clé manquante aux deux gardes qu'elle relie.

Les clés détenues par chaque garde sont celles qui ne lui manquent pas.

Ce qui donnerai comme solution :

A = (3,4,5,7,9,10)
B = (1,5,4,6,8,10)
C = (1,2,5,6,7,9)
D = (1,2,3,7,8,10)
E = (2,3,4,6,8,9)

On peut ainsi généraliser le problème à n gardes, il faut alors n(n-1)/2 clés, et chaque garde en possède alors (n-2)(n-1)/2

[Archi3]

bonne réponse !!

[Tryss2]

Du coup, je cherche la généralisation à n gardes et un minimum de k gardes présents...

[A voir en vidéo sur Futura]

[Bounoume]

 Cliquez pour afficher

Il faut au moins 10 serrures.

En effet,
- chaque couple de garde doit avoir au moins une clé manquante
- deux couples de gardes différents (AB et AC sont deux couples différents) ne peuvent pas avoir la même clé manquante, sinon il existera un groupe de 3 qui ne pourra pas ouvrir toutes les serrures

On peut représenter la situation sous la forme d'un graphe complet à 5 sommets (un pentagramme si vous préférez ). Les sommets sont les gardes, et on attache sur chaque chaque arrête la clé manquante aux deux gardes qu'elle relie.

Les clés détenues par chaque garde sont celles qui ne lui manquent pas.

Ce qui donnerai comme solution :

A = (3,4,5,7,9,10)
B = (1,5,4,6,8,10)
C = (1,2,5,6,7,9)
D = (1,2,3,7,8,10)
E = (2,3,4,6,8,9)

On peut ainsi généraliser le problème à n gardes, il faut alors n(n-1)/2 clés, et chaque garde en possède alors (n-2)(n-1)/2

ai-je encore fumé la moquette ce soir?
D'un côté l'énoncé dit qu'il faut au moins 3 gardes pour ouvrir toutes les serrures, et la solution donnée parle de 'couple' de gardes.
Pour moi un couple, c'est 2 individus (de genre, de sexe quelconques ou spécifiés, m'en fiche...)

EN supposant valide exclusivement l'énoncé initial: 5 gardes dont 3 doivent être présents pour ouvrir avec succès
j'ai construit un graphe avec en abscisses les gardes, et en ordonnées les serrures.... et en valeur l'appariement serrure/clef du trousseau du garde ....

 Cliquez pour afficher

cinq serrures;
sur le graphe, les intersections où la serrure est ouverte par la clé ad hoc sont deux diagonales parallèles (enfin, pour l'une fait supposer que l''espace des gardes se reboucle sur lui-même....)
chaque garde possède 2 clés seulement
ABCDE sont les gardes
12345 sont les couples clés/serrures ouvrantes
A=1,4
B=2,5
c=3,1
D=4,2
E=5,3


A B C D E

1 x . x . .

2 . x . x .

3 . . x . x

4 x . . x .

5 . x . . x

est-ce bien ça?
bonne soirée......

[Bounoume]

post-scriptum:
le problème considéré par Tryss se trouve être (graphiquement) le complément du problème original.....
et j'ai fort l'impression qu, même dans ce cas, 5 serrures suffisent encore, mais chaque garde aura 3 clés....

[Archi3]

Non, dans ta solution par exemple les gardes ABD n'ont pas la clé n° 3 ....

[Tryss2]

ai-je encore fumé la moquette ce soir?
D'un côté l'énoncé dit qu'il faut au moins 3 gardes pour ouvrir toutes les serrures, et la solution donnée parle de 'couple' de gardes.
Pour moi un couple, c'est 2 individus (de genre, de sexe quelconques ou spécifiés, m'en fiche...)

Oui, donc tout couple de garde ne doit pas pouvoir ouvrir le coffre : il leur manque forcément une clé !


Sinon, pour la généralisation à n gardes et un minimum de k gardes présents :

 Cliquez pour afficher

Il faut un minimum de serrures, et chaque garde aura clés.

Il faut en effet :
- que chaque groupe de k-1 gardes ne puisse pas ouvrir la porte (donc qu'il leur manque une clé)
- deux groupes de k-1 gardes différents (= dont au moins un membre n'est pas le même) ne peuvent manquer la même clé, sinon on peut construire un groupe de k gardes incapable d'ouvrir la porte

Or il y a groupes de k-1 gardes

De plus, chaque garde est alors dans groupes de k-1 gardes, donc il va lui manquer clés.

[Bounoume]

j'ai essayé, empiriquement, de corriger le défaut.
Voici ce que ça donne:
correction du défaut:
état initial:
>ouverture en x pour xxx.. ou xx..x mais pas xx.x. (ici * est assimilé à . c.a.d. = pas de clé )
maintenant rajout des clés en *:
>pour ouvrir en xx.x. rajout des clés symbolisées par *: clé si x ou *, pas de clé seulement si .
A B C D E
1 x * x . .
2 . x * x .
3 . . x * x
4 x . . x *
5 * x . . x

mais effet de bord: ouvertures illégales de type x.x.. ,x..x.
>blocage des ouvertures non voulues
6 . x . x x
7 x . x . x
8 x x . x .
9 . x x . x
10 x . x x .


11 . x x . x
12 x . x x .
13 . x . x x
14 x . x . x
15 x x . x .

Ainsi il me faudrait 15 serrures et chaque garde aurait 9 clés.....

Pour ta généralisation, Tryss2,j'ai 2 doutes:
les 'n' sur la ligne au-dessus, est-ce bien des exposants (puissance 'n' )?..... et s'appliquent-ils bien au contenu entre parenthèses?
si oui, en posant k=2, alors..
comme (k-1) devient (2-1)=1
alors
n
(k-1) devient 1 quel que soit l'exposant
il faudrait UNE SEULE serrure pour avoir ouverture à 2 gardes minimum ....
et si non, on en viendrait très vite à des nombres monstrueux..

bonne soirée!

[Tryss2]

Il s'agit des coefficients binomiaux, et oui effectivement, ça grimpe "vite".

Par exemple, le nombre de serrures pour 100 gardes dont plus de la moitié doivent être présent est un nombre à 30 chiffres

[Archi3]

j'ai essayé, empiriquement, de corriger le défaut.

ce qui prouve que c'est bien moins efficace que le raisonnement rigoureux ...

[Bounoume]

Il s'agit des coefficients binomiaux, et oui effectivement, ça grimpe "vite".

Par exemple, le nombre de serrures pour 100 gardes dont plus de la moitié doivent être présent est un nombre à 30 chiffres

effectivement, ça me rappelle de très vieux souvenirs....mais alors le nombre de combinaisons de p éléments pris dans un ensemble de n entiers naturels s'écrivait
avec le symbole C (combinaison/ensemble non ordonné ) et A (arrangements, ordonnés )

n
Cp et on n' utilisait pas la notation ( )


pour nos 5 gardes parmi lesquels 3 quelconques sont nécessaires et suffisants pour ouvrir,
5
C(3-1), ça fait 10 serrures.......;


et ma solution empirique:
comme en réalité les serrures 6,7,8,9,10 permettent de gérer les DEUX séquences x.x.. et x..x. parce que.... c'est la même par translation avec retour en pos. zéro !!!
les serrures suivantes sont inutiles!
ainsi, après seconde correction (la suppression des serrures et clés redondantes de 11 à 15)
j'ai aussi 10 serrures!
l'empirique rejoint le théoricien......