Puzzles

par **Doraki** » 14 Déc 2009, 14:24

On s'intéresse aux puzzles dont les pièces carrées représentent des lignes droites ou bien des virages, comme ci-dessous à gauche :

Chaque modèle de pièce a une couleur (ici, blanc ou gris) sur ses 4 bords.
En permettant de mettre côte à côte deux pièces bordées par une même couleur, on peut construire des formes plus grandes.
Ici on peut paver un rectangle de côtés blancs avec les 6 pièces données en le remplissant avec des courbes fermées.
(on ne peut pas faire tourner les pièces)

Pouvez-vous donner un ensemble de couleurs et un jeu de modèles de pièces pour lequel les pavages possibles d'un rectangle (dont chacun des bords doit être d'une couleur uniforme prédéfinie) avec des pièces de votre modèle correspondent aux dessins représentant une seule courbe fermée qui remplit le rectangle ?
Il faut donner un jeu de pièces qui permette de paver TOUS les dessins formés d'une seule courbe, et SEULEMENT ceux là, donc il doit exclure l'exemple ci-dessus.

par **Ben314** » 14 Déc 2009, 20:23

La taille du rectangle est-elle fixée ?
(i.e. si on a 12 pièces, faut il étudier toutes les possibilitées de faire un rectangle 3x4 et un 2x6 ou bien une seule des deux)

Sinon, la première soluce qui me vient, c'est 4 angles et 2n traits horizontaux (ou verticaux !!!) ....

Mais je n'est pas bien compris ce qu'il falait "maximiser" (nb de pièces ?)

par **Doraki** » 14 Déc 2009, 21:06

Non, la taille du rectangle n'est pas fixée.
Il faut donner les modèles des pièces, et on suppose qu'on dispose d'une infinité de pièces de chaque modèle.

Et j'ai pas été assez précis dans le problème.
Pour chaque dessin d'une seule courbe fermée qui remplit un rectangle, il faut pouvoir trouver un pavage avec des pièces de tes modèles qui le réalise.
Et réciproquement, toute solution avec des pièces de tes modèles doit représenter une seule courbe fermée.

Il faudra que la couleur du bord haut du rectangle soit différente de la couleur du bord bas du rectangle, et pareil pour les bords gauche et droit, sinon on pourrait recoller des solutions entre elles pour former un pavage avec plusieurs courbes.

par **Ben314** » 15 Déc 2009, 16:49

On peut avoir plus de 6 modèles différents ?

par **Doraki** » 15 Déc 2009, 19:26

Tu peux avoir autant de modèles que tu veux, sinon tu pourrais pas faire grand chose.

par **nodgim** » 15 Déc 2009, 20:35

Doraki a écrit:Tu peux avoir autant de modèles que tu veux, sinon tu pourrais pas faire grand chose.

J'ai besoin de précision, combien de couleurs de bord autorisées ?

par **Doraki** » 15 Déc 2009, 22:03

Autant que tu veux.

par **nodgim** » 16 Déc 2009, 18:26

Je ne comprends pas : il suffirait de remplacer une couleur par un nombre, représenté seulement sur 1 bord de 2 carrés, et le tour est joué. Quant à la représentation de la courbe fermée, où est le problème ?

par **Doraki** » 16 Déc 2009, 21:17

Je comprends pas ta solution, tu peux me décrire ou me dessiner les modèles de tes pièces, et expliquer pourquoi ils ne permettent pas par exemple de reproduire mon premier exemple, où il y a 2 courbes fermées ?

Y'a beaucoup d'incompréhension pour le moment, vous voulez une définition vraiment formelle du problème ?

par **ffpower** » 16 Déc 2009, 21:32

Moi non plus j ai pas tout pigé, je veux bien l énoncé epsilonique^^

par **Benjamin** » 16 Déc 2009, 21:36

A chaque nouveau message sur ce fil, j'avais le secret espoir avant de lire d'enfin comprendre ce problème LoL. A chaque fois, raté :P
Je pense que bien que n'ayant pas dépassé la Spé en maths, je comprendrais aussi davantage l'énoncé epsilonique ^^

par **ffpower** » 16 Déc 2009, 21:50

Moi non plus j ai pas tout pigé, je veux bien l énoncé epsilonique^^

par **Ben314** » 16 Déc 2009, 21:58

Alors là, je vais en surprendre plus d'un .....
Bon, j'ai évidement pas la solution, mais au moins, j'ai fini par comprendre l'énoncé.... (enfin je crois.... :doh: )
Il faut que tu "colorie" les bords de façon à rendre impossible tout remplissage d'un rectangle par autre chose qu'une courbe fermée simple...

par **Benjamin** » 16 Déc 2009, 22:11

AAAAAAAAAAAAAAHHHHHHHHHHHHHHHHHHH
Ca doit être ça :D

par **Doraki** » 16 Déc 2009, 22:26

Euh..
Bravo Ben314 ^^'

C'est pas un énoncé epsilonique c'est un énoncé juste moche comme tout :

On se donne un alphabet A de lettres, (ou de carrés).
Ici notre alphabet a 6 éléments, les 4 virages et les 2 lignes droites.
Un dessin de longueur m et de hauteur n est une application de

.

Un automate bidimensionnel (bon dans la littérature ça désigne autre chose mais bon), est un .. heptuplet

où :
Sh et Sv sont deux ensembles finis, dont les éléments sont appelés les états horizontaux et états verticaux. (mais je préférais les noter avec des couleurs).

; ce sont les états initiaux.

; ce sont les états finaux.

est une partie de

.

Un dessin de longueur m et de hauteur n (une application

) est accepté par un automate

lorsqu'il existe un "coloriage"

, tel que :

.

Le but est de proposer un automate qui reconnaisse exactement les dessins qui représentent une seule courbe fermée.

par **Doraki** » 22 Déc 2009, 11:44

Bon un petit up (je savais que ça ferait peur un énoncé comme ça)

Le problème est de donner un jeu de pièces qui permette de paver TOUS les dessins formés d'une seule courbe, et SEULEMENT ceux là, donc qui ne permettent pas de former le dessin que j'ai mis en exemple dans mon premier post

par **ffpower** » 22 Déc 2009, 13:08

En effet, on va en revenir aux couleurs finalement :we:
Est-ce que le bord du rectangle doit forcément etre blanc? Car si c est le cas, j ai l impression que si on a une config de courbe fermée, on peut en accoller plusieurs a la suite, et donc obtenir une config avec plusieurs courbes fermées...

par **Doraki** » 22 Déc 2009, 13:23

Non justement, il faut mettre une couleur différente entre le bord droit et le bord gauche, et de même pour les bords bas et haut.

par **Ben314** » 22 Déc 2009, 13:50

Bon, comme je cherche (un peu) et que je trouve pas, je met quand même un post. pour pas que doraki croie que je fout rien.
Je dessine tout les rectangles possibles et tout les pavages par des courbes fermées (c'est dénombrable) et je met des couleurs différentes absolument partout (sauf évidement pour ceux qui se touchent).
J'obtient un ensemble dénombrable de piéces coloriées avec un ensemble dénombrables de couleur et ça vérifie clairement la propriété demandé.

Bon, évidement, je me demande si, sur la quantité de pièces et de couleur on pourait pas faire légèrement mieux (tient, par exemple, j'ai fastoche une soluce avec 12 pièces de moins et 4 couleurs en moins :id: )

par **Doraki** » 22 Déc 2009, 14:02

euh pas mal ...
mais c'est pas très informatif et j'aurais préféré un automate fini ^^'.

Je vais réfléchir si je peux te demander un automate qui reconnaît aussi des dessins infinis (ceux pour lesquels tout sous-rectangle fini est inclus dans un rectangle fini qui est un bon dessin d'une seule courbe ; ou bien alors ceux qui représentent une courbe connexe, ah j'hésite j'hésite). Juste pour que tu te prennes un ensemble de couleurs non dénombrable. (Aussi ça m'amènerait à regarder éventuellement des automates de bucchi bidimensionnels)

A titre informatif, savoir si deux automates/jeux de pièces sont équivalents (acceptent les mêmes dessins) est un problème indécidable (ce qui veut dire que je risque de galérer pour comparer vos solutions à la mienne), et qu'il y a probablement plein de manières de construire un automate qui réponde à la question.

Puzzles

puzzles

Qui est en ligne