[Maths] Help
-S'il existe une solution avec n serrures, il en existe une avec n+1 serrures.
En effet : Supposons qu'il existe une solution avec n serrures.
On suppose désormais qu'on a ajouté une n+1 ème serrure. Il suffit de donner à chacun de nos 6 individus la clé de cette nouvelle serrure pour que tous les trios puissent ouvrir le coffre, alors que les duos n'y parviendront toujours pas.
-Deux individus distincts ont toujours au moins une clé en commun.
En effet : Procédons par l'absurde. On suppose qu'il existe deux individus n'ayant AUCUNE clé en commun.
On nomme A,B,C,D,E et F les 6 individus. On peut par exemple considérer que A et B n'ont aucune clé commune.
Supposons que A possède une clé x qui n'est pas possédée par le duo CD. Alors le trio BCD ne possède pas la clé x et ne peut pas ouvrir le coffre. Or, par hypothèse BCD peut bien ouvrir le coffre. Donc le duo CD possède toutes les clés de A.
Or, le trio ACD peut, par hypothèse, ouvrir le coffre. Donc le duo CD le peut également, absurde.
-Le trousseau d'un individu ne peut pas être inclus dans le trousseau d'un autre.
Par l'absurde : supposons que le trousseau de B soit inclus dans le trousseau de A.
On sait que le trio ABC peut ouvrir le coffre. Mais puisque A possède toutes les clés de B, le duo AC peut lui aussi ouvrir le coffre, absurde.
-Au moins 4 personnes possèdent au moins n/3 clés, où "n" désigne le nombre total de serrures.
Par l'absurde : si au maximum 3 personnes possèdent au moins n/3 clés, alors pour simplifier on peut supposer que ces trois personnes sont A, B et C. Mais alors le trio D,E,F possède strictement moins de n clés (différentes) et ne peut donc pas ouvrir le coffre ...
-Il y a au moins 8 serrures.
J'imagine qu'il y a plus court 
On nomme A,B,C,D,E,F les 6 individus et on les suppose classés de celui ayant le plus de clés à celui en ayant le moins.
On montre aisément qu'il faut au moins 3 serrures :
S'il n'y a qu'une serrure, bah un unique individu pourra toujours ouvrir le coffre.
S'il y a deux serrures, on aura forcément un duo qui parviendra à tout ouvrir.
S'il y a trois serrures et qu'aucun duo ne peut accéder au coffre, c'est que chacun des 6 individus n'est en possession que d'une unique clé, et donc il existe un trio qui ne possède que deux clés différentes.
Supposons qu'il y ait 4 serrures.
Alors aucun individu ne peut avoir 3 clés ou plus : sinon il y a forcément un duo qui ouvre tout.
A, B, C et D ont donc exactement deux clés. Chacun a exactement une clé commune avec les trois autres.
Quitte à renuméroter, on pourra supposer que A a les clés 12 et B les clés 13.
Deux possibilités :
C possède les clés 14 ou C possède les clés 23.
Si C possède les clés 23, alors D aura forcément deux clés parmi les clés 1,2, et 3 et donc D aura exactement le même trousseau que A, que B ou que C, ce qui est proscrit.
Si C=14, alors quelles que soient les deux clés qu'on attribue à D, soit il aura exactement le même trousseau que A, B ou C (interdit) soit il n'aura aucune clé en commun avec l'un d'entre eux (interdit aussi). Absurde.
Bref, il faut au moins 5 serrures.
Supposons qu'il y a exactement 5 serrures :
Si A possède 3 clés (ou plus), disons A=123, alors aucun des 5 autres individus ne doit posséder simultanément les clés 4 et 5. Mais alors le trio constitué de A et de deux individus quelconque ayant tous deux la clé 4 (ou tous deux la clé 5) ne sait pas ouvrir le coffre.
Donc A possède seulement deux clés. Disons, les clés 12. On peut alors supposer (quitte à réindexer) B=13. Mais alors C et D doivent tous deux posséder les mêmes clés : 45 (pour que les triplets ABC et ABD ouvrent le coffre). Or c'est interdit.
Donc il faut au moins 6 serrures.
Supposons qu'il y a exactement 6 serrures.
Si A ne possède que les clés 12, alors :
Si B possède 23 alors on a un souci car personne dans le groupe ne possède à lui seul les clés 456 (je rappelle que A est supposé comme étant celui qui a le plus de clés).
Supposons que A a trois clés, disons les clés 123.
Si B a aussi 3 clés, il y a deux cas possibles :
-B=345 (une unique clé commune) mais alors chacun des autres membres du groupe doit posséder la clé 6. On montre (facile mais flemme de détailler) que C ne peut pas avoir trois clés. Mais du coup le trio CDE n'a que (maximum) 4 clés distinctes, absurde.
-B=234 (deux clés communes) impossible car alors chacun des 4 autres individus possède les clés 5 et 6, et donc le trio CDE ne possède que (maximum) 5 clés distinctes.
Donc B n'a que deux clés distinctes. En tenant plus ou moins le même raisonnement que juste avant, on montre que cette situation aussi est absurde.
Supposons que A a 4 clés.
A1234. B possède exactement une clé distincte de A. Disons, la clé 5. Mais alors C, D et E possèdent tous trois la clé 6 (pour que ABC, ABD et ABE ouvrent) et donc pas la clé 5. (Sinon AC, AD et AE ouvriraient), et donc CDE ne peut pas ouvrir.
Bref, il faut au moins 7 serrures.
Supposons qu'il y a 7 serrures exactement.
Si A possède 3 clés (123) alors (quitte à réindexer) B possède 234 ou 345 et en tous les cas D,E,F et possèdent tous la clé 6 et la clé 7, or ils possèdent tous 3 clés ou moins, donc le trio DEF n'a pas toutes les clés.
Si A possède 4 clés (1234) et B 3 ou moins, alors B=345 ou 456 (quitte à réindexer).
Si B= 345 alors D,E,F possèdent tous la clé 6 et la clé 7 et donc le trio DEF n'a pas toutes les clés.
Si B=456 alors C,D,E,F possèdent tous la clé 7 (et au maximum 3 clés). Le trio CDE peut déverrouiller le coffre. donc à part la clé 7, C, D et E n'ont AUCUNE clé en commun. Autrement dit, si je connais les clés possédées par C et par D, je n'ai plus qu'un unique choix pour les clés à donner à E. Mais on peut dire la même chose de F, autrement dit E et F ont le même trousseau. Absurde.
Si A et B possèdent 4 clés :
A=1234 et B=4567 impossible
A=1234 et B=3456 implique que C,D,E et F possèdent tous la clé 7. Tous possèdent soit la clé 5, soit la clé 6, mais pas les deux. (Si C possède 5 et 6 alors AC déverrouille le coffre. Si C ne possède ni 5 ni 6, alors puisque ACD déverrouille coffre, c'est que D possède 5 et 6 et donc AD déverrouille le coffre...).
Disons par exemple que C possède la clé 6. Alors puisque ACD, ACE et ACF déverrouillent le coffre, c'est donc que D, E et F possèdent la clé 5 ... mais alors DEF ne possède pas la clé 6, et donc ne déverrouille pas le coffre, absurde.
Si A=1234 et B=2345 alors C,D,E et F possèdent tous les clés 6 et 7 et donc pas la clé 5, absurde car alors CDE ne déverrouille pas le coffre.
...Donc A possède au moins 5 clés. A=12345, donc aucun individu ne possède simultanément les clés 6 et 7. Il suffit alors de considérer le trio formé de deux personnes ayant la clé 6 (ou deux ayant la clé 7) et de A pour aboutir à un truc absurde.
Puisqu'il est évident que A ne peut pas posséder 6 ni 7 clés, c'est donc qu'il faut au moins 8 serrures.
J'ai beaucoup aimé cette énigme, et je suis content de l'avoir résolue même si ça m'aura pris un paquet de temps
J'ai fait l'erreur de partir du principe qu'il existait forcément une solution avec très peu de serrures (genre 6) et de chercher explicitement cette dernière, c'est pour ça que dans le premier raisonnement que je présente je me contente de dire "pas possible pour 1 serrure, ni deux, ni trois, ni ..."
API disponible. Utilisez le paramètre "api" en GET, peu importe le contenu, sur une page du site.
-
Partenaire: JVFlux
Ce site n'est pas associé à Jeuxvideo.com ou Webedia. Nous utilisons seulement des archives publiques.
Il est inutile de me spammer par e-mail pour supprimer un topic. Au contraire, en conséquence, je mettrais votre topic dans le bloc ci-dessous.
-
Personne n'a pas assumé de topic pour le moment.