|
#26 - 19-04-2013 01:08:40
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumerr la maison
Pour les gourmands, en revoilà 6 de plus !
#27 - 19-04-2013 22:33:27
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Allumr la maison
Bon, apparemment la méthode Gwen ne marche pas. Essai de la méthode avec 5 cases de largeur: les boutons tournés 10001 et 01010 conduisent à appuyer sur le même bouton à la ligne suivante: 00100. Ce n'est pas bijectif. Du coup, on va aboutir à une séquence qui n'allume jamais toutes les lampes: 10001 donne 00100 puis à nouveau 10001. Et apparemment , toutes les combinaisons de départ tombent dans ce piège.
#28 - 20-04-2013 11:13:59
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Allumer la maisn
Faux, ce n'est effectivement pas bijectif mais :
10001 allumera toutes les lampes pour un tableau de 2 15 18 ou 23 lignes sauf erreur.
01010 allumera toutes les lampes pour un tableau de 6 14 15 ou 23 lignes...
Quel que soit le nombre de ligne je trouve de une à 32 solutions pour attaquer la première ligne et remplir le tableau à la fin.
D'ailleurs c'est très curieux : Avec un tableau de 5 colonnes et 23 lignes, si on applique la méthode, j'ai bien l'impression que le tableau sera rempli quelle que soit la combinaison choisie en ligne 1 .
#29 - 20-04-2013 11:25:44
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allume la maison
Wah, golgot, c'est beau !
J'aime bien le chateau-fort pour le carré 9x9.
Pour ma part, je reste modeste avec les rectangles 3xn, en essayant de repérer des motifs qui peuvent s'arrêter ou se répéter à l'infini.
Voici ce que j'ai trouvé :
3x1:
# O O
3x2:
#O OO O#
## ## OO
3x3:
#O# O#O #O#
3x4:
#### #OO# ####
3x5:
####O #OO#O ####O
#O#OO O#OO# #O#OO
##OO# ##OOO OOO#O
3x6:
O####O O#OO#O O####O
3x7:
OO#O#OO #OO#OO# OO#O#OO
3x8:
##OO#OOO ##OOOO## OOO#OO##
#OO##OO# OOO##OOO O#OOOO#O
3x9:
#O#OOO#O# O#OO#OO#O #O#OOO#O#
3x10:
####OO#### #OO#OO#OO# ####OO####
3x11:
####OO####O #OO#OO#OO#O ####OO####O
#O#OOO#O#OO O#OO#OO#OO# #O#OOO#O#OO
##OO#OOOO#O ##OOOO##OOO OOO#OO##OO#
Ce qui se généralise à :
3x(6k+1), 3x(6k+5) et 3x(6k+3) :
(O O)#O# OO O#O# OO ... (# O)O#O O# OO#O O# ... (O O)#O# OO O#O# OO ...
3x(3k+2):
(## O)O# OOO O#O O## OO# OOO ... (## O)OO O## OOO O## OOO O## ... (OO O)#O O## OO# OOO O#O O## ...
3x(6k+4), 3x(6k+5) et 3x6k :
(O)#### O O#### O ... (O)#OO# O O#OO# O ... (O)#### O O#### O ...
#30 - 20-04-2013 12:08:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
allumer la maisin
gwen27 a écrit:Faux, ce n'est effectivement pas bijectif mais :
10001 allumera toutes les lampes pour un tableau de 2 15 18 ou 23 lignes sauf erreur.
01010 allumera toutes les lampes pour un tableau de 6 14 15 ou 23 lignes...
Quel que soit le nombre de ligne je trouve de une à 32 solutions pour attaquer la première ligne et remplir le tableau à la fin.
D'ailleurs c'est très curieux : Avec un tableau de 5 colonnes et 23 lignes, si on applique la méthode, j'ai bien l'impression que le tableau sera rempli quelle que soit la combinaison choisie en ligne 1 .
Oui Gwen: l'analyse de l'éclairement d'une pièce d'une ligne se fait sur 2 lignes, ce que j'avais omis de faire. En conséquence, une situation de départ peut aboutir sur une situation gagnante, mais avec un nombre de lignes fixe modulo quelque chose. C'est compliqué à démontrer que ça marche toujours....
#31 - 21-04-2013 12:35:50
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Allumer la maisno
Dans une grille de dimension quelconque : on peut affecter des valeurs à une case :
Exemple pour 3x3 :
Si on appuie partout, on a donc
T=343454343 (équivalent à 101010101)
Il faut donc retirer : 010101010 (modulo2 à chaque rang)
a,b,c,d,e,f,g,h,i le fait d'appuyer ou non sur la case :
a+b+d=1 ou 3 a+b+c+e= 1 ou 3 ....
Bon 3x3 ça va vite, il en ressort une solution unique : a c e g i
Bizarrement, c'est l'inverse de ce qui était à trouver et l'équivalent de la grille, mais ça doit être une coïncidence. Mais bon, n équations et n inconnues ça devrait être jouable pour d'autres dimensions.
#32 - 21-04-2013 15:33:40
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer la maiso
Grace à l'observation de Gwen, je suis parvenu à lister toutes les solutions pour les petites grilles carrées, et les résultats sont assez étranges :
Pour des carrés de côté x, il y a y solutions différentes (aux rotations et symétries près) : x -> y 1->1 2->1 3->1 4->5 5->1 6->1 7->1 8->1 9-> une petite centaine !!! 10->1 Ensuite les essais commencent à prendre beaucoup de temps...
#33 - 21-04-2013 15:53:20
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer la masion
@titou : Voici ce que je trouve pour les formes se répétant à l'infini en rectangles de 3xn, et ce sont les seules (zoomable):
#34 - 21-04-2013 16:11:20
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer la maiison
Et voici pour les 4xn :
#35 - 21-04-2013 16:30:33
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
allumer la mzison
Et voici pour 5xn :
#36 - 21-04-2013 19:26:22
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allumer la mmaison
Pour revenir sur l'exemple 3x3 traité par gwen, la matrice [TeX] M=\begin{bmatrix} 1&1&0&1&0&0&0&0&0 \endline 1&1&1&0&1&0&0&0&0 \endline 0&1&1&0&0&1&0&0&0 \endline 1&0&0&1&1&0&1&0&0 \endline 0&1&0&1&1&1&0&1&0 \endline 0&0&1&0&1&1&0&0&1 \endline 0&0&0&1&0&0&1&1&0 \endline 0&0&0&0&1&0&1&1&1 \endline 0&0&0&0&0&1&0&1&1 \end{bmatrix}[/TeX] est inversible dans [latex]\mathbb{Z}/2\mathbb{Z}[/latex] et un logiciel nous calcule [TeX] M^{-1}=\begin{bmatrix} 1&0&1&0&0&1&1&1&0 \endline 0&0&0&0&1&0&1&1&1 \endline 1&0&1&1&0&0&0&1&1 \endline 0&0&1&0&1&1&0&0&1 \endline 0&1&0&1&1&1&0&1&0 \endline 1&0&0&1&1&0&1&0&0 \endline 1&1&0&0&0&1&1&0&1 \endline 1&1&1&0&1&0&0&0&0 \endline 0&1&1&1&0&0&1&0&1 \end{bmatrix}[/TeX] On peut donc obtenir n'importe quelle configuration de lumière, et d'une façon unique. En particulier il y a une unique façon d'allumer toutes les lumières : [TeX] M^{-1} .\begin{bmatrix} 1 \endline 1 \endline 1 \endline 1 \endline 1 \endline 1 \endline 1 \endline 1 \endline 1 \end{bmatrix} = \begin{bmatrix} 1 \endline 0 \endline 1 \endline 0 \endline 1 \endline 0 \endline 1 \endline 0 \endline 1 \end{bmatrix}[/TeX] ce qui correspond à la solution
#O# O#O #O#
Pour d'autres dimensions que 3x3, il se peut que la matrice ne soit pas inversible et l'on aura alors plus de solutions, toujours une puissance de 2.
#37 - 21-04-2013 20:22:24
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer al maison
Mais alors, ça donnerait quoi pour le carré de 17 de côté ?
Voila 3 jours que je m'acharne dessus, je pense que la solution est unique...
#38 - 21-04-2013 21:03:04
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Allumer la maiison
Je ne connais rien aux matrices mais elles sont toutes drôlement similaires... De là à penser que ce qui est valable pour une l'est pour les autres.
Pour 17 de côté, il va falloir quelqu'un qui connait le sujet, pas moi en tout cas
#39 - 21-04-2013 21:24:13
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
Allumer la mmaison
Pour un carré de coté n, le nombre de solutions est donné par
n=1,2,3,6,7,8,10,12,13,15,18,20 une seule solution
n=4 16 solutions n=5 4 solutions n=9 256 solutions n=11 64 solutions n=14 16 solutions n=16 256 solutions n=17 4 solutions n=19 [latex]2^{16}[/latex] solutions
#40 - 21-04-2013 22:23:59
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Allumer la maiso
titoufred a écrit:Pour d'autres dimensions que 3x3, il se peut que la matrice ne soit pas inversible et l'on aura alors plus de solutions, toujours une puissance de 2.
J'avais lu "on n' aura plus de solution" au lieu de "on en aura +"
D'où l'insistance inutile du dernier post
#41 - 21-04-2013 22:57:58
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
almumer la maison
masab, tu trouves ça avec le rang de la matrice M je suppose ? Quel logiciel, tu utilises pour programmer ça ?
#42 - 22-04-2013 10:56:03
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
allumrr la maison
@Masab : Tu es sûr de tes résultats, je suis presque sûr qu'il n'y a qu'une solution pour un carré de 5, toutes sont des rotations de la même... (de même pour le carré de 4, où je ne distingue que 5 formes distinctes)
#43 - 22-04-2013 16:16:51
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allumer al maison
masab considère juste que ce sont des solutions différentes.
#44 - 23-04-2013 02:39:06
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allumer la mmaison
Je résume et complète mes messages précédents pour les rectangles de hauteur m : je donne les motifs se répétant à l'infini fournissant toutes les solutions pour les rectangles mxn, aux symétries près. Pour cela il faut couper la frise en 2 endroits : on commence après une rangée de O et l'on finit avant une autre rangée de O.
m=1 : 1 motif
m=2 : 2 motifs
motif 1 : n = 4k, 4k+2 ou 4k+3 motif 2 : n = 2k+1 (4k+1 ou 4k+3)
m=3 : 3 motifs
motif 1 : n = 6k, 6k+4 ou 6k+5 motif 2 : n = 3k+2 (6k+2 ou 6k+5) motif 3 : n = 2k+1 (6k+1, 6k+3 ou 6k+5)
m=4 : 5 motifs
motif 1 : n = 5k, 5k+3 ou 5k+4 motifs 2, 3 et 5 : n = 5k+4 motif 4 : n = 5k+1, 5k+2 ou 5k+4
m=5 : 5 motifs
motif 1 : n = 24k, 24k+6, 24k+7, 24k+8, 24k+14, 24k+15, 24k+16, 24k+22 ou 24k+23 motifs 2 et 3 : n = 12k+3, 12k+7 ou 12k+11 (24k+3, 24k+7, 24k+11, 24k+15, 24k+19 ou 24k+23) motif 4 : n = 24k+2, 24k+4, 24k+7, 24k+10, 24k+12, 24k+15, 24k+18, 24k+20 ou 24k+23 motif 5 : n = 24k+1, 24k+5, 24k+7, 24k+9, 24k+13, 24k+15, 24k+17, 24k+21 ou 24k+23
Cela confirme les résultats de golgot. Mais je vois pas comment étendre les motifs pour d'autres dimensions...
#45 - 23-04-2013 02:54:07
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allumer la maisson
golgot, voici l'unique solution (aux rotations près) pour le carré 17x17 :
##OOOO#OO#OO##OOO ##O##OOOOOOO##O## OO###OO##O#OOO### O###OOO###OOO###O O##O##OO####O##O# OOOO##O#O#O##OOOO #OOOOO#OO#OO##O#O OO##O#O#O#O#O##OO OO###OOO###OOO### #OO###########OO# OO#O#OOO###OO#### OOOO##O#O#O##OOOO ##OOO##OO#O###OOO ##O##O##O##O##O## OO###OO##O#OOO### O###OO#O#O#OO###O O##O#OOO###OO##O#
#46 - 23-04-2013 15:15:36
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer la mison
Merci Titou !
Pour 6xn (zoomable):
#47 - 23-04-2013 15:32:06
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Allumer l amaison
J'ai fait 7xn mais il y a 28 "dessins" différents. Je les présenterai si vous les voulez.
#48 - 23-04-2013 17:05:00
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
Allumerr la maison
On suppose que l'on a un rectangle (p,q). J'ai indiqué dans mon 1er message que résoudre le problème revient à résoudre un système linéaire de [latex]p\,q[/latex] équations à [latex]p\,q[/latex] inconnues, à coefficients dans le corps [latex]\{0,1\}[/latex] (on a donc [latex]1+1=0[/latex]). Il en résulte que s'il existe au moins une solution, alors le nombre des solutions est une puissance de 2 (JE NE DIS PAS : le nombre de solutions à rotation ou symétrie axiale près).
Pour résoudre un tel système, j'ai utilisé la méthode de Gauss. Autrement dit j'ai fait des opérations élémentaires successives sur les équations du système ; une opération élémentaire consiste ici à ajouter à une équation d'autres équations.
Lorsqu'il y a une unique solution (là aussi je ne dis pas à rotation ou symétrie axiale près), alors cette solution est de façon évidente invariante par rotation ou symétrie axiale. Donc si l'on colorie en vert les cases des interrupteurs à ouvrir, on obtient de belles configurations.
Voici le pdf des solutions uniques pour les carrés de côté [latex]1,2,3,6,7,8,10,12,13,15,18,20[/latex].
#49 - 23-04-2013 17:35:21
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
allumzr la maison
Voici l'une des 4 solutions du carré de côté 17
Cette configuration est symétrique par rapport à l'une des diagonales. Les 3 autres solutions s'en déduisent par rotations d'angles 90, 180 ou 270 degrés (la rotation d'angle 270 degrés donne la solution indiquée par titoufred).
#50 - 23-04-2013 18:31:16
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Allumer la maisonn
C'est booooooooooo ! C'est un papillon, on est d'accord ?
Tu l'obtiens comment ton dessin ? Et toi golgot ? J'en ai marre de faire des trucs tout moche...
golgot, pour les rectangles 7xn, je n'ai trouvé que 27 motifs (avec un programme). T'en aurais pas 2 identiques par hasard ?
Mots clés des moteurs de recherche
|
|