![](/img/vague-bas-gauche.png) |
#1 - 06-11-2010 11:58:01
- Yannek
- Passionné de Prise2Tete
- Enigmes résolues : 10
- Messages : 60
Sytsème de lampes...
Une première énigme mathématique maison...
Boole, l'éléctricien de Gauss, lui a installé un plafonnier composé de 6 lampes A,B,C,D,E et F, telles que ABCDEF forme un hexagone régulier.
Chacune des lampes a deux états possibles : éteinte ou allumée.
Dans la pièce, Boole a installé 6 interupteurs, u,v,w,x,y,z. Actionner l'interputeur * u change d'état les lampes F,A,B * v change d'état les lampes A,B,C * w change d'état les lampes B,C,D * x change d'état les lampes C,D,E * y change d'état les lampes D,E,F * z change d'état les lampes E,F,A
Chaque interupteur a deux états : position haute ou position basse.
En rentrant chez lui, Gauss constate que certaines des lampes sont allumées, d'autres éteintes. Tous les interupteurs sont en position basse. Au bout de quelques secondes, il est certain de pouvoir éteindre toutes les lampes.
Question 1 : Donner une condition nécessaire et suffisante (la plus élégante possible!) sur l'état initial des six lampes pour que Gauss puisse effectivement les éteindre. C'est plus classe quand c'est démontré... À titre de test, entrez le nombre de possibilités trouvé dans la case réponse.
Question 2 : (bonus) Dans chacun des cas où l'on peut éteindre les lampes, combien de configurations différentes des interrupteurs permettent de les éteindre ?
Question 3 : (super bonus) expliquer les positions possibles des interupteurs pour éteindre une configuration initiale donnée...
[Edit] : à l'arrivée de Gauss, il se peut que toutes les lampes soient éteintes ou allumées... (désolé)
#2 - 06-11-2010 12:47:13
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 964
sysrème de lampes...
Boole a été très nul dans son installation car on ne perd rien à supprimer les deux derniers interrupteurs. En effet : y=v+u+x & z=w+u+x
Les 4 premiers me semblent former une famille libre : il y aurait dont 16 (2 puissance 4) possibilités avec cette configuration. Hélas, les lampes peuvent être allumées de 64 manières (2 puissance 6). Il n'y aurait donc qu'une chance sur quatre pour qu'on puisse tout éteindre. En reprenant y et z, cela ferait donc 4 positions différentes pour un même résultat...
Pour les autres questions, j'attends encore la lumière _____________________
Me revoilà. Une configuration permettant de tout éteindre est telle que : - ou bien chaque lampe est dans le même état que celle qui lui ait diamétralement opposée dans le cercle circonscrit à l'hexagone, - ou bien chaque lampe est dans l'état opposé à son vis-à-vis. Je retrouve bien 8+8=16 configurations.
Dans le détail, je regarde celles qui sont allumées parmi A, B et C : * ABC --> j'actionne l'interrupteur v * AB --> u * BC --> w * AC --> x & z * A --> z * B --> u, v & w * C --> x * aucune --> rien
Après cette étape, aucune des lampes A, B ou C n'est restée allumée. D, E et F sont alors ou bien toutes allumées et j'actionne y, ou bien toutes éteintes et c'est fini. J'ai donc bien trouvé 8*2=16 configurations...
Celui qui fuit les casse-tête ne vaut pas un clou.
#3 - 06-11-2010 16:48:21
- Khyros
- Habitué de Prise2Tete
- Enigmes résolues : 23
- Messages : 18
SSystème de lampes...
Elle était sympa celle là =] Par contre pour le test de la question 1, soit je comprends pas la question, soit il y a une faute ? Ce qui est demandé, ce n'est pas le nombre d'états initiaux que le bonhomme Gauss sera capable d'éteindre ? Si c'est bien ça, la réponse est à priori 16 (j'ai vérifié manuellement..) alors que la réponse attendue est 12.
Question 1: Pour commencer on peut montrer que les interrupteurs disons u et z ne servent à rien ( la famille des 6 interrupteurs est de rang 4 <3 ). u = v + x + y z = v + w + y On ne les utilisera donc pas <3
De là on a nos 6 lampes A B C D E F. On va dire que A=1 si A est initialement allumée, 0 sinon, et de même pour les autres lettres.
Le seul de nos 4 interrupteurs restant contrôlant A est v. On appuie donc A fois sur l'interrupteur v pour avoir A éteinte. Puis on appuie A+B fois sur l'interrupteur w pour avoir A et B éteintes. Puis on appuie B+C fois sur l'interrupteur x pour avoir A, B et C éteintes. Puis on appuie A+C+D fois sur l'interrupteur y pour avoir A, B, C et D éteintes.
Finalement on a notre double condition sur E et F pour que toutes les lampes soient éteintes: E=A+B+D F=A+C+D
Ce qui pour le test nous donne 16 cas où l'on peut éteindre les lampes qui correspondent aux 16 états possibles de A,B,C et D. Les lampes E et F sont dans l'état déterminé par la condition. Je vois pas trop comment faire plus élégant, c'est de base pas très élégant <3
Question 2
Toujours avec les interrupteurs u et z dans un certain état fixé, on a une unique possibilité en jouant sur les 4 autres d'éteindre le plafonnier. C'est ce que montre l'algorithme d'au dessus. Donc, sachant qu'il y a 4 états possibles pour les interrupteurs u et z qui peuvent être compensés par les 4 autres (puisqu'ils sont liés aux autres), on en déduit qu'il y a 4 position possible des interrupteurs pour chaque situation solvable ! =]
Question 3
Alors je comprends pas spécialement la question là ^^ Connaissant la configuration initiale des lampes, on retrouve assez facilement avec cette méthode les 4 configurations des interrupteurs qui les éteignent, mais de là à l'exprimer directement, je vois pas.
Voila voilà, en espérant avoir bon et avoir été clair =P
#4 - 06-11-2010 19:09:09
- Yannek
- Passionné de Prise2Tete
- Enigmes résolues : 10
- Messages : 60
Système de lampes..
Excellentes réponses de Scrablor et Khyros (avec en plus la correction de la réponse test !)
#5 - 07-11-2010 13:24:46
- McFlambi
- Professionnel de Prise2Tete
- Enigmes résolues : 48
- Messages : 144
système de mampes...
Alors on travaille en base 2, et toucher un interrupteur c'est ajouter 1 a une lampe et ses voisines.
Partant de n'importe quelle configuration ABCDEF (les lampes allumees ou eteintes), on voit bien que si il existe la meme configuration avec des interrupteurs dans un autre etat c'est qu'on a ajoute 0 ou 2 a chaque lampe (puisqu'on peut ajouter 0,1,2, ou 3.). Ci dessous des exemples de changements d'interrupteurs uvwxyz (1 pour changement, 0 pour rien, a gauche de la fleche) et les additions sur les lampes ABCDEF (a droite de la fleche) qui devraient tout nous faire comprendre: 000000 -> 000000 010000 -> 111000 010100 -> 112110 = 110110 011000 -> 122100 = 100100 011100 -> 123210 = 101010
Donc pour garder un 000000 a droite, il y a les possibilites suivantes: 000000 -> 000000 011011 -> 222222 = 000000 et les deux configurations jumelles...
Et pour changer tout, 111111 -> 333333 = 111111 100100 -> 111111
On en deduit qu'a chaque configuration ABCDEF, s'il y en a une, il y a quatre configurations uvwxyz differentes qui la redonnent (3 de plus quoi).
Comme il y a 2^6 = 64 configurations d'interrupteurs ET de lampes possibles, mais que celles des interrupteurs ne permettent pas de donner toutes celles des lampes (puisqu'elles vont par 4, avec ce qui a ete dit au dessus). Plus precisement donc, il y a 16 configurations de lampes atteignables. Avec les exemples du dessus on les trouve assez vite, si on part de la configuration de lampe 000000 : 000000 -> 000000 (1 configuration) 010000 -> 111000 (6 configurations jumelles) 010100 -> 110110 (3 configurations jumelles) 011000 -> 100100 (3 configurations jumelles) 011100 -> 101010 (2 configurations jumelles) 100100 -> 111111 (1 configuration)
Donc reponse a la question 1) au dessus ; c'est a dire les configurations de droite. Reponse a la question 2) au dessus aussi : 4. et question 3) au dessus aussi.
Pour l'elegance, je vois pas par contre.
#6 - 08-11-2010 13:31:39
- dylasse
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 378
Système de lameps...
Etape 1 :
A une rotation près, les configurations possibles en modifiant l'état de 3 lampes voisines sont :
conf A : 111111 (1 seule config par rotation) conf B : 111000 (6 config par rotation) conf C : 110110 (3 config par rotation) conf D : 100100 (3 config par rotation) conf E : 101010 (2 config par rotation) conf F : 000000 (1 config par rotation)
Soit un total de 16 configurations possibles. LA conditions nécessaires et suffisante est donc d'être dans une de ces configuration pour pouvoir éteindre toutes les lampes.
Je n'ai pas de démonstration plus simple que l'essai systématique de chaque config et de chaque interrupteur.
Etape 2 : de la conf E, on passe à la conf D ou C en une commutation (au hasard). de C ou D on passe à B en une commutation (bien choisie). de B on passe à F en une commutation (bien choisie).
de la conf A, on passe à B, puis à F en 2 commutation (une au hasard, la seconde bien choisie).
Dans tous les cas, 3 commutations suffisent.
Etape 3 : tout est possible comme on ne sait pas comment sont les ampoules à l'initial.
#7 - 08-11-2010 16:14:19
- Milou_le_viking
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 446
Système de lampes..
Question 1 : Il faut que l'état initial respecte une symétrie central ou une anti-symétrie centrale. Il y a 16 cas possibles. Il y a peut-être un groupe en mathématique qui exprime cela. Je vais un peu rechercher.
Question 2 : Dans tous les cas, il existe 4 configurations finales qui permettent d'éteindre toutes les lumières.
Question 3 : J'y réfléchis.
#8 - 08-11-2010 22:23:38
- luthin
- Professionnel de Prise2Tete
- Enigmes résolues : 36
- Messages : 124
système de lamoes...
1\ Pour savoir si il est possible d'éteindre toutes les lampes dans une configuration donnée, il suffit qu'on puisse y parvenir à partir de celle où toutes les lampes sont éteintes. Je trouve alors six configurations possibles:
![http://www.prise2tete.fr/upload/luthin-Lampes.jpg](http://www.prise2tete.fr/upload/luthin-Lampes.jpg) On peut vérifier rapidement que modifier l'état de l'une ou l'autre, abouti à l'une ou l'autre de ces configurations. C1: une possibilité! C2: trois. C3: deux. C4: six. C5: trois (le contraire de C2). C6: une.
Ce qui fait au total, 16 possibilités.
2\ Pour chaque configuration, on peut éteindre les lampes en un minimum d'événements. Je vais donc faire le dénombrement des façons de les éteindre pour ces cas précis. C1: le travail est déjà fait, il n'y a qu'une façon. C2: au minimum, deux événements: 4*1=4 façons. C4: un év.: 1 façon. C5: deux év.: 4*1=4 façons. C6: deux év.: 6*1=6 façons. C3: trois év: 1er cas: on appui en premier sur un interrupteur qui nous mène à C2. 3*4=12 façons. 2ème cas: à la suite du premier événement, on tombe sur C5. 3*4=12 façons. Soit au total pour C3, 24 façons.
3\ pour l'instant, je ne comprends pas la question!
Très sympathique cette énigme, merci. ![smile](img/smilies/smile.png)
#9 - 09-11-2010 12:46:25
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Système dee lampes...
On va faire un peu d'algèbre de Boole. a,b,c,d,e et f sont les états initiaux des lampes (1 si allumé) u,v,w,x,y,z sont les états finaux des interrupteurs (1 si levé) On va utiliser du xor à tour de bras (du coup, je vais pas le noter, mais implicitement chaque variable est séparée des autres par un xor). Pour rappel, a xor a = 0 a xor b = c => a = b xor c
On veut tout éteindre 0 = azuv 0 = buvw 0 = cvwx 0 = dwxy 0 = exyz 0 = fyzu
Ca se résoud comme un système d'équation classique. On commence comme ca u = azv 0 = bazw 0 = cvwx 0 = dwxy 0 = exyz 0 = fyav etc... Au final, on arrive à u = zadcy w = zab x = dyzab v = dcy 0 = abde 0 = acdf Conclusion: il faut, pour arriver à résoudre ce problème, que 0=abde et 0=acdf, qu'on peut encore écrire ad = be = cf. Autrement dit, sur chaque diagonale, on doit avoir 2 lampes dans le même état ou une lampe dans chaque état.
Combien de configuration cela nos fait-il? La paire (a,d) peut prendre 4 valeurs, elle fixe le résultat ad. b peut alors prendre 2 valeurs mais e est fixé pour obtenir le même résultat, pareil pour c et f. Au final donc, 4*2*2 = 16 configurations initiales possibles
Question 2. considérons les autres équations u = zadcy w = zab x = dyzab v = dcy On peut choisir des valeurs arbitraires pour la paire (y,z) on pourra tout de même éteindre nos lampes (il suffira de lever ou de ne pas toucher au u,v,w et x suivant ce qu'on trouve; mais leur valeurs sont fixés par le coix de y et z). Il y a donc 4 combinaisons différentes.
Question 3: on reprend les mêmes équations, on va fixer y = z = 0 pour simplifier grandement tout ça u = acd w = ab x = abd v = cd Or ad = be = cf, simplifions encore u = f w = ab x = e v = cd
En termes plus compréhensibles: 1) J'active u si F est allumée 2) J'active v si C et D ne sont pas dans le même état 3) J'active w si A et B ne sont pas dans le même état 4) J'active x si E est allumée.
#10 - 09-11-2010 14:13:10
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
ySstème de lampes...
Question subsidiaire: à supposer qu'on puisse tout éteindre, peut-on le faire sans toucher ni à u, ni à x?
#11 - 09-11-2010 15:34:03
- Yannek
- Passionné de Prise2Tete
- Enigmes résolues : 10
- Messages : 60
Syystème de lampes...
Merci de vos réponses, argumentées. Ma solution est celle de Scarta :
Le problème se résume à un système affine sur les corps des booleéns (c'est l'ensemble {0,1} munis de la multiplication usuelle et de l'addition suivante : 0+0=0, 1+0=0+1=1 et 1+1=0, qui a pour conséquence a=-a). On le résoud par la méthode du pivot de Gauss.
La lampe A d'état initial a (0 pour éteinte, 1 pour allumée) a un état final égal à u+v+z+a (u=0 en position basse, 1 en position haute) car les interupteurs agissant sur A sont u,v,z. Ainsi le problème équivaut à [TeX]\left\{ \begin{array}{lllllllllllll} u &+&v& & & & & & &+&z&+&a&=0\\ u &+&v&+&w& & & & & & &+&b&=0\\ ~& &v&+&w&+&x& & & & &+&c&=0\\ ~& & & &w&+&x&+&y& & &+&d&=0\\ ~& & & & & &x&+&y&+&z&+&e&=0\\ u& & & & & & &+&y&+&z&+&f&=0\\ \end{array}\right. [/TeX] On passe les termes a,b,c,d,e,f de l'autre côté (sachant -a=a), puis on remplace L6 par L6+L1+L2+L4, on remplace L5 par L5+L1+L3+L4, on remplace L2 par L2+L1 et enfin L3 par L3+L4. On obtient le système équivalent [TeX]\left\{ \begin{array}{lllllllllll} u &+&v& & & & & & &+&z&=a\\ ~& & & &w& & & & &+&z&=a+b\\ ~& &v& & & & &+&y& & &=c+d\\ ~& & & &w&+&x&+&y& & &=d\\ 0& & & & & & & & & & &=a+d+b+e\\ 0& & & & & & & & & & &=a+d+c+f\\ \end{array}\right. [/TeX] Enfin, on remplace L'1 par L'1+L'3 (et on tient compte de L'6 : f=a+c+d), on remplace L'4 par L'4+L'2 (et on tient compte de L'5 ; e=d+b+e. On passe les y et les z de l'autre côté et on obtient : [TeX]\left\{ \begin{array}{llllll} u=&y&+&z&+&f\\ v=& & &z&+&a+b\\ w=&y& & &+&c+d\\ x=&y&+&z&+&e\\ 0=& & & & &a+d+b+e\\ 0=& & & & &a+d+c+f\\ \end{array}\right. [/TeX] Question 1 Ce système a des solutions si et seulement si a+d+b+e=0 et a+d+c+f=0. Si a et d valent la même chose, cela impose que b et e sont identiques ainsi que c et f. Si a et d on pour somme 1, cela impose la même chose pour b+e et c+f, on obtient donc la condition suivante (cf Scrablor ou Milou le viking, et le dessein de Luthin) : "on peut éteindre toutes les lampes si et seulement l'état initial est symétrique ou anti-symétrique" qui compte bien 16 cas (2*2*2+2*2*2* n'est pas égal à 12 comme je l'ai d'abord prétendu dans la case solution (merci Scrablor et Khyros...)
Question 2 On peut choisir les positions de y et z arbitrairement, donc lorsqu'il y a des solutions, elles forment un sous espace affine de dimension 2 (qui compte 4 éléments)
Question 3 cf. Scarta. Pour éteindre une configuration donnée, suivre les indications du dernier sytème... Par exemple, activer u si f est allumée, x si e est allumée, v si les lampes a et b ne sont pas dans le même état, et w si les lampes e et f ne sont pas dans le même état. L'algorithme de dylasse permet d'y arriver plus rapidement dans certains cas.
Question subsidiaire de scarta : je vous laisse réfléchir, mais on ne peut choisir n'importe quelle inconnue pour le pivot... (si e et f sont d'états contraires...)
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |