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 : 1403
Lieu: Coutiches

Allumer la maisonn

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 : 3168

Allumer l 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 : 5,679E+3

Allumre la maison

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 : 1746

amlumer 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 : 3168

allumer la maisob

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 : 5,679E+3

Allumer la maisn

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 : 1403
Lieu: Coutiches

Allumer lla maison

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 : 1403
Lieu: Coutiches

Allumer la maion

@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 : 1403
Lieu: Coutiches

alluler la maison

Et voici pour les 4xn :

 #35 - 21-04-2013 16:30:33

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1403
Lieu: Coutiches

Allumer l maison

Et voici pour 5xn :

 #36 - 21-04-2013 19:26:22

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

lAlumer la maison

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 : 1403
Lieu: Coutiches

Allumer la mison

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 : 5,679E+3

allumzr la maison

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 : 701

Allumer lla maison

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 : 5,679E+3

Allumer la amison

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 : 1746

allumet 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 : 1403
Lieu: Coutiches

llumer 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 : 1746

allumrr la 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 : 1746

Allumer a maison

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 : 1746

Allumer la miason

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 : 1403
Lieu: Coutiches

allumer la laison

Merci Titou !

Pour 6xn (zoomable):

 #47 - 23-04-2013 15:32:06

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1403
Lieu: Coutiches

Allumer lla maison

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 : 701

Allumer lla 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 : 701

allumee 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 : 1746

llumer la maison

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 à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
21-10-2009 Enigmes Mathématiques
17-03-2009 Enigmes Mathématiques
P2T
23-04-2010 Enigmes Mathématiques
P2T
07-12-2007 Enigmes Mathématiques
18-11-2007 Enigmes Mathématiques
P2T
Magie 4 par Vasimolo
09-09-2012 Enigmes Mathématiques
P2T
Problème de société... par SaintPierre
08-05-2011 Enigmes Mathématiques
P2T
Gâteau 124 par Vasimolo
27-07-2016 Enigmes Mathématiques
P2T
Quadrigolo par lequadrigolo
29-04-2011 Enigmes Mathématiques

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