Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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 !

#0 Pub

 #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 hmm .

 #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. big_smile

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 hmm .

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 :

Code:

ABC
DEF
GHI

A=110100000
B=111010000
C=011001000
D=100110100
E=010111010
F=001011001
G=000101110
H=000010111
I=000001011

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.

Code:

111-
11-1
1-11
-111

11-1-----
111-1----
-11--1---
1--11-1--
-1-111-1-
--1-11--1
---1--11-
----1-111
-----1-11

Code:

11--1-----------
111--1----------
-111--1---------
--11---1--------
1---11--1-------
-1--111--1------
--1--111--1-----
---1--11---1----
----1---11--1---
-----1--111--1--
------1--111--1-
-------1--11---1
--------1---11--
---------1--111-
----------1--111
-----------1--11

Pour 17 de côté, il va falloir quelqu'un qui connait le sujet, pas moi en tout cas lol

 #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 +" big_smile

D'où l'insistance inutile du dernier post roll

 #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

http://www.prise2tete.fr/upload/titoufred-allumer_1xn.png

m=2 : 2 motifs

http://www.prise2tete.fr/upload/titoufred-allumer_2xn.png

motif 1 : n = 4k, 4k+2 ou 4k+3
motif 2 : n = 2k+1 (4k+1 ou 4k+3)

m=3 : 3 motifs

http://www.prise2tete.fr/upload/titoufred-allumer_3xn.png

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

http://www.prise2tete.fr/upload/titoufred-allumer_4xn.png

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

http://www.prise2tete.fr/upload/titoufred-allumer_5xn.png

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
http://www.prise2tete.fr/upload/masab-allumer-17.jpg
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 ? smile

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 ?

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Vecteurs (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete