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

 #1 - 24-08-2010 00:36:22

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echces 5

J'ai parlé il y a quelque temps des petites tours qui se déplacent sur les échiquiers comme leurs grandes soeurs mais d'une seule case à la fois tongue

On laisse une petite tour gambader un moment sur un échiquier , son territoire est l'ensemble des cases qu'elle a traversé . Si le territoire de la petite tour contient un nombre pair de cases 2n , montrer qu'on peut paver celui-ci avec n dominos ( rectangulaires ) de dimensions quelconques .

Un territoire de 10 cases pavé avec 5 dominos :

http://img841.imageshack.us/img841/885/illustration.jpg

Amusez-vous bien smile

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 26-08-2010 07:31:02

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Echecss 5

Il n'y a pas beaucoup de réponses, je ne dois pas être le seul à patauger dans des démonstrations un peu fumeuses... mais bon, j'amorce la pompe pour faire réagir Vasimolo et récupérer un p'tit indice...

J'ai pensé à une démonstration par récurrence :
pour n=1 : c'est évident.
pour n=2 : les territoires possibles sont ... les pièces de Tétris que l'on peut toutes former par 2 dominos de tailles 1 et 3 ou 2 et 2.

Pour n>= 3, on suppose que la propriété est vraie pour n-1.
Je vais tenter de montrer que l'on peut toujours couper le territoire Tn de taille 2n en 2 territoires de taille paire.

1. On recherche sur le territoire une case C1 n'ayant qu'un coté adjacent avec le reste de Tn.
1. Si on en trouve une. On identifie C2 la case adjacente.
1.1. : si on retire le domino C1-C2 et que le reste des case de Tn forment un seul territoire, celui-ci est de taille 2(n-1) : c'est bon.
1.2. si on retire C1-C2 et que le reste des cases forme 3 territoires : l'un de ces territoires est de taille paire, donc lui et le reste de Tn est un découpage recherché.
1.3. si on retire C1-C2 et que le reste des cases forme 2 territoires, T1 et T2 (on notera T1 le plus grand)
1.3.1. Si T1 est de taille paire, T1 et le reste de Tn est un découpe recherché.
1.3.2. Si T1 est de taille impaire, ....

et je suis obligé d'arrêter car j'ai trouvé un T4 que je ne peux pas découper en 2 territoires pairs :
http://www.prise2tete.fr/upload/dylasse-echec5.jpg

La récurrence imaginée n'est donc pas valable !

Ou alors, il faut envisager les territoires impaires,
montrer qu'un territoire impair de taille 2n+1 se pave de au plus n+1 dominos (facile territoire pair à 2n + 1 case).
puis montrer que si un découpage de Tn n'est possible qu'avec 2 territoires impairs (2p+1) et (2q+1) alors à la frontière des 2, on pourra trouver des dominos alignés qui pourront n'en former qu'un sur Tn qui aura en tout p+1+q+1-1=p+q+1=n dominos...

Y'a plus simple ????!!!

 #3 - 26-08-2010 12:37:21

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Ehcecs 5

Un petit indice pour motiver les troupes .

Indice : Spoiler : [Afficher le message] Le territoire peut être recouvert par des dominos 1Xk tous horizontaux ou bien tous verticaux .

Je n'ajoute pas de temps pour le moment smile

Vasimolo

 #4 - 27-08-2010 09:45:23

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1935
Lieu: 86310

evhecs 5

Je propose une démonstration par récurrence.

Cas 1
2 cases seulement sont par définition adjacentes et peuvent être ici facilement couvertes par un traditionnel domino 1x2.

Cas n → n+1
Soit un labyrinthe (ou parcours erratique) contenant 2n cases comme décrit dans l’énoncé. On suppose que les 2n cases puissent être couvertes par n dominos du type 1xk. Deux cases sont ajoutées au parcours formant un parcours de 2(n+1) cases.

http://www.prise2tete.fr/upload/franck9525-echec5.png

Si ces cases sont adjacentes (Ex1), elles peuvent être recouvertes par un domino 1x2 et le nombre total de dominos est n+1

Si les cases ne sont pas adjacentes, plusieurs cas existent en fonction de la case de connexion ; j’appelle case de connexion une case existante du parcours à laquelle est connectée une nouvelle case :
- Une des deux cases de connexion est 1x1 => elle devient 1x2 et un domino 1x1 est ajoute => n+1 dominos
ou
- Les 2 cases de connexion appartiennent à des dominos d’une longueur de deux cases ou plus (1xk avec k>1).
  - L’une des cases ajoutées est dans l’axe (Ex2). Le domino de connexion 1xk
    devient 1x(k+1) => n+1 dominos
  ou
  - Les deux cases ajoutées sont sur le coté de dominos 1xk (Ex3a ou Ex3b). Dans ce cas, les deux cases ajoutées peuvent former un domino 1x2 avec leur case de connexion. Le parcours d’origine moins les 2 cases de connexion est donc de 2(n-1) cases et, par définition, peut être recouvert par (n-1) dominos ce qui donne un total de (n+1) dominos pour couvrir 2(n+1) cases. CQFD cool

A la relecture je me rends compte que dans le cas ou les cases ajoutees ne sont pas adjacentes alors on peut directement appliquer le raisonnement de la derniere hypothese ce qui fait une demonstration beaucoup plus courte.


The proof of the pudding is in the eating.

 #5 - 28-08-2010 01:16:11

blaxe
Habitué de Prise2Tete
Enigmes résolues : 27
Messages : 12

Echcs 5

Une limite peut meme etre imposée ! N'utiliser que des dominos de 1, 2 ou 3 cases !

 #6 - 28-08-2010 01:37:07

blaxe
Habitué de Prise2Tete
Enigmes résolues : 27
Messages : 12

echecd 5

Voici ma démonstration très peu mathématique, mais je pense assez explicite !
Spoiler : [Afficher le message] Appellons "case isolée" une case qui n'en touche qu'une seule autre. On peut techniquement rassembler toutes les cases en groupement de 4 ou de deux ! Pour les cases qui touchent au moins deux cases non isolées, c'est facilement compréhensible ! Pour les autres, imaginons toutes les possibilités :
- une case qui touche une case isolée : on obtient alors une forme en L, en Z ou en T (que nous verrons plus tard).
- une case qui touche deux cases isolée : on obtient une forme en T avec deux cases pour la barre verticale
- une case qui touche trois cases isolée : on obtient une forme en T aussi !
Prenons donc ces groupements séparément : un groupement de 2 cases n'a besoin que d'un domino ( logique !). Pour les groupements de 4, il existe 4 formes différentes :
-une forme en "T" (c1, c2, c3, d2), dans ce cas, on peut mettre un domino de 3 cases sur la ligne des c et un domino "monocase" en d2
-une forme en "Z" (c1, c2, d2, d3) (Ce n'est pas vraiment un Z, j'avoue...). Dans ce cas, deux dominos, un en c, un en d, suffisent
-une forme en I (c1 à c4) qui n'a pas besoin d'être détaillée...
-une forme en L (c1, c2, c3, d3) composé d'un domino pour les 3 et d'un domino pour c1 et c2
Dans ce cas, on voit bien que chaque groupement de 2 ou de 4 cases pris séparément n'a besoin que de 1 ou 2 dominos, soit la moitié du nombre de cases ! Donc chaque groupement de cases en nombre paire peut etre recouvert par un nombre de domino deux fois plus petit !
CQFD !

 #7 - 28-08-2010 12:26:26

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echecss 5

Je ne suis convaincu par aucune des explications ci-dessus mais c'est parfois un peu difficile à lire et j'ai pu passer à côté de bonnes idées .

Le problème avec une récurrence sur n c'est qu'il faut retirer deux cases adjacentes sans casser la connexité du domaine ce qui n'est pas toujours possible comme le montre le dessin de dylasse . On peut essayer de corriger en regardant toutes les figures possibles obtenues en retirant deux cases mais c'est très vite inextricable . On peut toutefois conserver la connexité en enlevant une seule case bien choisie .

Je ne donne pas ma solution complète mais seulement l'idée principale smile

On fait bien une récurrence mais sur le nombre c de cases ( pair ou impair ) . On désigne par H le nombre de rectangles horizontaux de longueur maximale et largeur 1 permettant de paver le domaine et V le nombre de rectangles verticaux ...

Par récurrence on a H+V < c+2

Il n'y a plus qu'à conclure dans le cas où c est pair .

Merci pour la participation smile

Vasimolo

 #8 - 28-08-2010 15:38:40

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

checs 5

Moi je me pose la question du "domino", qu'appelles-tu un domino?


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

 #9 - 28-08-2010 17:44:28

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echcs 5

C'est vrai que j'aurais pu préciser smile

Ici il s'agîssait d'un rectangle à côtés entiers posé en suivant les lignes du  quadrillage donc pas nécessairement 2X1 ni même nX1 .

Vasimolo

 #10 - 28-08-2010 18:04:45

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

Echec s5

Merci car pour moi un domino est fait de 2 cases, comme pour ton énigme avec les points à jouer alternativement.

ça devient vraiment compliqué ces histoires de dominos


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)
 

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 : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 2 par Vasimolo
11-08-2010 Enigmes Mathématiques
P2T
Echecs 22 par Vasimolo
20-08-2013 Enigmes Mathématiques
P2T
Echecs 19 par Vasimolo
29-10-2012 Enigmes Mathématiques
P2T
Echecs 1 par Vasimolo
08-08-2010 Enigmes Mathématiques
P2T
Echecs 16 par titoufred
05-10-2012 Enigmes Mathématiques
P2T
Echecs 13 par Vasimolo
26-08-2012 Enigmes Mathématiques
P2T
Echecs 23 par Vasimolo
20-04-2018 Enigmes Mathématiques
P2T
Echecs 3 par Vasimolo
16-08-2010 Enigmes Mathématiques
P2T
Echecs 18 par Vasimolo
19-10-2012 Enigmes Mathématiques
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques

Mots clés des moteurs de recherche

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