|
E6. Autres casse-tête
|
Le coffre-fort de la banque
Assurétourisk est protégé par un système de cartes magnétiques. Chacune
d'elles comporte tout ou partie d'un code à N caractères nécessaire
pour l'ouverture du coffre. Seul le directeur de la banque dispose de
la carte magnétique complète. En son absence, le directeur adjoint peut
ouvrir le coffre à condition que sa carte et celle de l'un quelconque
des quatre fondés de pouvoir de la banque puissent y être introduites.
Si le directeur et son adjoint sont absents, il faut les cartes de
trois quelconques des fondés de pouvoir pour y accéder.
Quel est la plus petite valeur possible de N ?
Malgré
ces précautions, la banque fait l'objet d'un cambriolage. Elle décide
qu'en plus du directeur toujours détenteur d'une carte magnétique
complète, il y aura deux adjoints et cinq fondés de pouvoir qui seront
détenteurs de cartes magnétiques incomplètes de telle sorte que :
- les deux directeurs adjoints,
- ou bien l'un des adjoints avec l'un quelconque de cinq fondés de pouvoir,
- ou bien quatre fondés de pouvoir parmi les cinq,
peuvent ouvrir le coffre.
Quel est la plus petite valeur possible de N ?
Source :Site Internet Brainjuice.net
Question n°1
Le problème paraît à première vue simple et on serait tenté de dire qu'il suffit d'un code à 5 caractères avec la répartition suivante selon les six responsables de la banque :

Le directeur dispose d'une carte magnétique complète. Le directeur adjoint associé à l'un quelconque des fondés de pouvoir est en mesure d'ouvrir le coffre et de la même manière trois fondés de pouvoir ouvrent également le coffre sans difficultés. Mais cette solution n'est pas bonne car deux fondés de pouvoir quelle soit la paire considérée parviennent aussi à ouvrir le coffre. Il faut donc augmenter le nombre de caractères de telle sorte que tout couple de fondés de pouvoir n'ait pas la totalité des codes exigés pour l'ouverture du coffre. Or il y a couples possibles et comme les fondés de pouvoir doivent tous avoir un caractère du code non détenu par le directeur adjoint, il en découle une carte à 7 caractères dont voici une distribution :

On s'assure bien que toutes les paires de fondés de pouvoir ne permettent pas de reconstituer le code complet.
Question n°2
En prenant les mêmes précautions que ci-dessus, on constate qu'il y a =10 couples et le même nombre =10 triplets de fondés de pouvoir. On part donc d'une configuration de base dans laquelle les cinq fondés de pouvoir ont une carte à dix caractères de telle manière qu'aucune paire et aucun triplet ne disposent d'un code complet. Si l'on tient compte maintenant des deux directeurs adjoints, l'un et l'autre séparément doivent être appariés avec l'un quelconque des fondés de pouvoir, ce qui revient à doubler la configuration de base à 10 caractères pour la porter à 20 caractères. Ci-après une distribution possible des cartes selon les huit responsables de la banque :

Là encore, on s'assure que toutes les paires et tous les triplets de fondés de pouvoir ne permettent pas de reconstituer le code complet.
 |