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
[+]

 #51 - 13-10-2012 19:19:59

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

rchecs 2

Oui mais une grille est un graphe biparti bien particulier. Sait-on jamais ?

#0 Pub

 #52 - 16-10-2012 00:21:29

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

Echec 2

J'étais en train de relire ta démo du point 2.

N'y a-t-il pas un problème quand tu dis que T-X est pavable par des dominos ?

En effet, on sait seulement que T-X est perdant pour le joueur qui commence à une case voisine de X, mais on ne sait pas que T-X est perdant pour le joueur qui commence à la case où il veut. sad

 #53 - 16-10-2012 18:42:48

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Ehcecs 2

En effet il y a un problème smile

Il me semble qu'on peut le corriger de la façon suivante .

On considère une position P avec une seule case gagnante pour le joueur 1 que l'on pave avec un maximum de dominos . Alors toute case hors dominos est gagnante . En effet à chaque étape le joueur 2 va devoir entamer un domino que le joueur 1 va compléter . Le joueur 2 ne peut pas sortir du circuit de dominos . Supposons qu'il le fasse sans laisser de cases hors dominos pour que le joueur 1 continue son chemin alors en décalant les dominos sur le circuit parcouru on crée un nouveau domino sans en supprimer : impossible . Si au contraire il sort du circuit en laissant une case libre hors domino pour le joueur 1 , on pose un domino sur les deux dernières cases : toujours impossible .

Après c'est facile s'il n'y a qu'une case hors dominos on décale un domino voisin vers cette case et on crée une nouvelle case gagnante .

Je crois que je vais retourner aux gâteaux lol

Je plaisante , merci Titou smile

Vasimolo

 #54 - 16-10-2012 19:56:16

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

echexs 2

Ouf ça marche ! Bravo !

Je dirais que le joueur2 ne peut pas sortir des dominos, car sinon en décalant on peut ajouter un domino. Pas besoin de distinguer deux cas.

 #55 - 16-10-2012 20:05:08

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

zchecs 2

En fait je ne cherchais pas à être bref mais plutôt explicatif car le problème est plus complexe qu'il en a l'air smile

Vasimolo

 #56 - 21-10-2012 00:23:04

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

ecjecs 2

Pour en revenir à la recherche des grilles pavables par des dominos.

J'essayais de trouver un algorithme qui n'explose pas avec le nombre de cases.

On sait qu'une CN pour être pavable c'est d'avoir autant de cases noires que de cases blanches sur chacune de ces composantes connexes.

On note le degré de chaque case (le nombre de cases voisines). On repère les culs-de-sac (cases de degré 1), que l'on retire avec leur voisin. Puis on recommence sur la nouvelle grille obtenue...

Je me demande si une grille connexe avec autant de cases blanches que de cases noires et n'ayant pas de cul de sac est forcément pavable. Je ne trouve pas de contre-exemple...

 #57 - 28-10-2012 09:27:21

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

EEchecs 2

En voici un smile

http://img696.imageshack.us/img696/4231/nonpavable.jpg

Peut-on faire plus simple ?

Vasimolo

 #58 - 28-10-2012 10:17:53

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Ehecs 2

Nombre impair de cases ici, Vasi.

 #59 - 28-10-2012 10:22:06

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,471E+3

echecq 2

Pas là  (quoique j'en compte 24 sur l'exemple de vasimolo)
http://www.prise2tete.fr/upload/gwen27-echec2bis.jpg

 #60 - 28-10-2012 10:38:07

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Ececs 2

Ah d'accord, je n'avais pas compris les "trous" du milieu...

 #61 - 28-10-2012 10:42:35

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Ecchecs 2

Oui et 26 pour Gwen donc la question reste ouverte : peut-on faire avec moins de 24 cases ?

Vasimolo

 #62 - 28-10-2012 10:42:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

echecq 2

En fait, au lieu de terme "cul de sac" il serait préférable de parler de chemin divergent. Et en effet, dans les figures de Vasi et Gwen, on a des chemins divergents.

 #63 - 28-10-2012 10:56:21

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Ehcecs 2

Je ne vois vraiment aucun moyen simple de caractériser les terrains non pavables . D'ailleurs l'idée de Gwen n'est pas la même que la mienne .

Pour la figure de Gwen le remplissage de la ligne du bas crée un blocage dans les  rectangles du haut . Mon idée était de "coller" deux morceaux présentant des déficits dans les couleurs opposées .

Ce qui est sûr c'est que s'il existe une caractérisation elle ne peut pas être uniquement locale .

Vasimolo

 #64 - 28-10-2012 13:38:38

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

cEhecs 2

Pour ma part, je fais abstraction de la notion "cul de sac" qui ne mènera pas à grand chose à mon avis.
Dans ces conditions, avec 4 cases on construit déja une figure non pavable.

 #65 - 28-10-2012 13:42:30

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

Echec s2

N'oublions pas qu'une CN est d'avoir autant de cases noires que de cases blanches.

 #66 - 03-11-2012 13:18:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Echces 2

Un terrain de 14 cases , bien équilibré , sans trou , sans case isolée et pourtant non pavable .

http://img31.imageshack.us/img31/5205/14cases.jpg

Vasimolo

 #67 - 03-11-2012 13:39:31

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Echeccs 2

J'avais idée, pour caractériser les assemblages pavables, de compter les nombres de cases pour chaque ligne et chaque colonne. Si toutes les colonnes et toutes les lignes ont un nombre pair de cases: pavable.
Les impairs marchent par 2 (car il y a un nombre pair de cases): Si impair sur ligne L et  impair suivant sur ligne L+S, alors il faut au moins S dominos horizontaux chevauchants dans l'intervalle (L;L+S).
Idem pour les colonnes.
Ce comptage est donc un outil d'aide à l'analyse du pavable ou pas, je n'arrive pas à aller plus loin.

 #68 - 03-11-2012 15:14:06

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

echrcs 2

Je reviens du Palais de la Découverte, où j'ai rencontré un animateur des "Récréations Mathématiques" qui proposait des problèmes de dominos.

Le mec m'a fait part de résultats (des critères) hyper simples pour déterminer si des terrains sont pavables ou pas par des dominos. Mais il n'était plus trop sûr de lui. Je vérifie quelques trucs et je vous en fait part dès que j'ai le temps.

 #69 - 03-11-2012 18:33:42

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

Echecss 2

Bon voici les quelques résultats qu'il m'a donnés, qui malheureusement ne sont pas des critères généraux, mais qui permettent tout de même de trancher quelques cas :

-Si le terrain (avec ou sans trous) n'a que des côtés longueur paire, alors il est pavable.

-Si le terrain (sans trous) n'a que des côtés de longueur impaire, alors il n'est pas pavable.

 #70 - 03-11-2012 18:49:27

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

echexs 2

Un critère général est donné par le théorème des mariages .

Le terrain est pavable en dominos si et seulement si le nombre de voisins de tout ensemble de cases d'une couleur donnée est supérieur ou égal au nombre de cases choisies .

Mais la vérification peut être est un peu longue smile

Vasimolo

 #71 - 03-11-2012 19:29:02

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

Ehcecs 2

Le critère n'est intéressant que s'il est facilement applicable.

Si je dis qu'un terrain est pavable si et seulement si c'est une réunion de rectangles de surface paire, ça nous fait une belle jambe !

 #72 - 03-11-2012 19:41:44

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Eches 2

On est bien d'accord mais faute de grives ...

Dans le dernier exemple que j'ai donné le théorème des mariages appliqué aux quatre cases jaunes du haut ou quatre cases blanches du bas permet d'affirmer instantanément qu'il n'y a pas de pavage possible .

C'est quand même assez expéditif  smile

Quand le pavage est possible le plus rapide est certainement de l'exhiber .

Vasimolo

 #73 - 03-11-2012 21:01:48

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

echecq 2

Oui la méthode est intéressante pour montrer qu'un terrain n'est pas pavable.

 #74 - 04-11-2012 10:26:39

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Echecs

C'est marrant ce théorème des mariages. Il faut tout de même colorier toutes les cases, ce n'est pas rien. Quant au critère de Titou, c'est plutôt restreint.

 #75 - 04-11-2012 15:43:35

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

evhecs 2

Voici un article qui parle de dominos si ça vous intéresse : http://dev.ulb.ac.be/urem/IMG/pdf/domin … ominos.pdf

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 : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 19 par Vasimolo
29-10-2012 Enigmes Mathématiques
P2T
Echecs 19 bis par Vasimolo
02-11-2012 Enigmes Mathématiques
P2T
Echecs 10 par Vasimolo
25-11-2011 Enigmes Mathématiques
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques
P2T
Echecs 5 par Vasimolo
24-08-2010 Enigmes Mathématiques
P2T
Echecs 1 par Vasimolo
08-08-2010 Enigmes Mathématiques
P2T
Echecs 4 par Vasimolo
19-08-2010 Enigmes Mathématiques
P2T
Echecs 9 par Vasimolo
15-03-2011 Enigmes Mathématiques
P2T
Echecs 18 par Vasimolo
19-10-2012 Enigmes Mathématiques
P2T
Echecs 14 par Vasimolo
03-09-2012 Enigmes Mathématiques

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