Forum de mathématiques - Bibm@th.net

Belibelo

Membre

Inscription : 12-02-2016

Messages : 3

Combinatoire

Bonsoir,

Un chateau est construit sous la forme d`une grille nxn.
Il est compose de nxn chambres.
Chaque chambre possede 4 murs.
Certains murs donnent sur l`exterieur (le jardin) d`autres non. On peut ouvrir une porte donnant sur le jardin.
On exige exactement 2 portes par chambre. Un mur quelconque possede au plus une porte. On ne peut pas construire 2 portes sur le meme mur.

Combien de configurations sont possibles? A exprimer en fonction de la valeur de n.
Pour n=1 6 configurations sont possibles.
Qu`en est-il pour n>=2?
Peut-on trouver une formule donnant exactement le nombre de configurations possibles?
Partant de ces contraintes on souhaite connaitre pour chaque nxn le nombre de configurations avec un nombre minimal de portes.
Par exemple pour n=2 on a une seule configuration possible utilisant 4 portes. n=1 on a 6 configurations possibles et 2 portes comme minimum.

Belibelo

Membre

Inscription : 12-02-2016

Messages : 3

Re : Combinatoire

Personne n`a reussi a trouver une formulation generale pour l`instant.
Quelques solutions partielles :
n=2 pour un chateau 2x2 il y a 82 configurations possibles.
n=3 pour un chateau 3x3 il y a 2064 config possibles.
J`ai trouve un algorithme pour solutionner le probleme suaf que a partir de n > 8 cela devient impossible en temps machine.

Belibelo

Membre

Inscription : 12-02-2016

Messages : 3

Re : Combinatoire

J`abandonne pour le moment et je laisse decanter cette question.