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 - 08-03-2017 22:00:45

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

décoration de salle se bain

Bonjour à tous,

je suis en train de refaire ma salle de bain. Je dispose de carreaux de trois sortes, présentés ci-dessous ; et j'aimerais, à l'aide de ces carreaux, représenter les quatre noeuds non triviaux les plus simples.

http://www.prise2tete.fr/upload/Ebichu-carrelage.png

De combien de carreaux au minimum ai-je besoin pour chacun de ces noeuds ?

Voici une table donnant les quatre noeuds non triviaux (le noeud trivial est un simple cercle) les plus simples, ce sont ceux nécessitant 5 croisements ou moins :

http://www.prise2tete.fr/upload/Ebichu-table.png

J'ai donné un exemple pour le noeud de trèfle (le noeud [latex]3_1[/latex]) qui nécessite 21 carreaux. Peut-être pouvez-vous trouver mieux ?

Addendum : cette énigme vous fera travailler avec les noeuds (https://fr.wikipedia.org/wiki/N%C5%93ud … atiques%29). On peut visualiser un noeud en prenant une ficelle, en la faisant se contorsionner, puis en collant les extrémités. Si alors, on déplace la ficelle sans décoller les extrémités, cela reste le même noeud. Ce faisant, le noeud change de forme ; on peut même rajouter des croisements inutiles, tant qu'on ne coupe pas la ficelle, cela reste le même noeud. En particulier, le noeud réalisé en bleu dans mon exemple est bien le noeud de trèfle [latex]3_1[/latex] , mais ce n'est pas immédiat, il faut prendre un crayon et une gomme pour s'en convaincre (ou mieux, une ficelle).

P.S. : cette énigme ne nécessite aucune connaissance particulière en théorie des noeuds, tout le monde peut s'y essayer. Mais la résoudre parfaitement demandera un peu d'astuce. Par ailleurs,  je n'ai pas cherché à prouver que mes solutions étaient optimales, aussi il n'est pas impossible que vous trouviez de meilleures solutions que moi.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-03-2017 23:36:13

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

Décoraiton de salle de bain

P.S. : cette énigme ne nécessite aucune connaissance particulière,

Euh, comprendre l'énoncé, c'est une compétence particulière ?

j'aimerais, à l'aide de ces carreaux, représenter les quatre noeuds non triviaux les plus simples (ceux nécessitant 5 croisements ou moins).

Ton bidule en trèfle, il ne fait pas partie du lot ? (juste 3 croisements)

Alors on les cherche où (sans connaissance) les figures à 5 croisements ?

 #3 - 09-03-2017 00:09:17

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

Décortion de salle de bain

@gwen27 : j'ai mis l'énoncé à jour, est-ce plus clair ainsi ?

Le noeud de trèfle fait partie du lot : 3 croisements, ça fait bien 5 croisements ou moins. Les 4 noeuds à réaliser en carrelage sont bien ceux donnés dans l'énoncé ([latex]3_1[/latex], [latex]4_1[/latex], [latex]5_1[/latex] et [latex]5_2[/latex] sont leurs petits noms).

 #4 - 09-03-2017 16:00:52

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 209

Décoraation de salle de bain

Bonjour,

Voila mes solutions pour les deux premiers

le premier nœud en 13 dalles:
http://www.prise2tete.fr/upload/caduk-noeud31.png

Le deuxième nœud en 17 dalles:
http://www.prise2tete.fr/upload/caduk-noeud41.png

Une petite démonstration de l'optimalité pour le premier nœud:
quelques propriétés:
(1)chaque croisement possède 4 voisins
(2)chaque dalle possède minimum 2 voisins
(3)un circuit passe par un nombre pair d'étapes (si on dame le quadrillage en noir et blanc, chaque déplacement change de couleur de case, il faut un nombre pair de déplacements pour revenir sur sa couleur.

Ici, il y a au moins trois croisement. Si on les place en angle,  d'après (1), on a minimum 10 dalles. En utilisant (2), on en a minimum 12.
Supposons qu'il y ait exactement trois croisements. Alors le nombre de dalles utilisées est impair d'après (3) (3 croisements, donc dalles ou on passe deux fois, donc nbr de dalles + nbr de croisements = nbr de déplacement) donc le minimum est 13.
Si il y en a 4, si on veut rester sur 12 cases, le 4 croisement termine le carré formé avec 3 autres.
Le dessin forme alors un carré de 4 dalles entourés de 8 dalles. Si on entre dans un croisement, on passe forcément par celui aligné. Si on relie de la seule manière possible, on trouve deux fils non reliés, donc pas de nœud. donc le minimum est donc 13.

Pour le deuxième nœud, ça m'a l'air beaucoup plus laborieux

Edit
Bon, j'ai pas trop cherché plus, mais pour les deux derniers, je trouve chacun 19:
http://www.prise2tete.fr/upload/caduk-noeud51.png
http://www.prise2tete.fr/upload/caduk-noeud52.png
On peut démontrer très facilement pour ces deux là que l'on ne peut pas faire mieux que 17, exactement de la même manière. (A savoir qu'en fait, le cas 6 croisements (tout comme le cas 4 croisements pour le 1er noeud) n'a pas besoin d'être traité car si on trace le graphe formé par la ficelle (avec pour sommets les croisements de base) il est planaire, et si on crée un nouveau croisement, on entre dans une face, de laquelle il faudra sortir, donc minimum 2 croisements en plus...
Pour monter à 19, c'est un peu plus chaud...

 #5 - 09-03-2017 16:46:12

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1932
Lieu: UK

Décorration de salle de bain

Salut,

Je propose un nœud 3(1) avec 13 carreaux
ainsi qu'un ... faux nœud

http://www.prise2tete.fr/upload/franck9525-type_3-1_and_0.png


voici un vrai nœud 4(1) avec 17 carreaux, les images à droite montrent le même nœud démêlé, le plus à droite est identique à l'exemple.


http://www.prise2tete.fr/upload/franck9525-type_4-1.png

Merci


The proof of the pudding is in the eating.

 #6 - 09-03-2017 20:01:09

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

décoration de sakle de bain

@caduk : bravo pour ta démo de l'optimalité de ta solution pour le premier noeud !
J'ai trouvé les mêmes solutions que toi, sauf pour [latex]5_2[/latex] où j'ai réussi à faire mieux.

@franck9525 : très bien ! tu as trouvé les meilleurs résultats pour les deux premiers noeuds.

 #7 - 09-03-2017 20:35:48

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 209

DDécoration de salle de bain

Effectivement, on trouve http://www.prise2tete.fr/upload/caduk-noeud522.png qui est donc solution optimale. Avec ce schéma à 7 croisements, il est malheureusement impossible de l'adapter pour le premier. Un début de preuve pour 5.1?

 #8 - 09-03-2017 21:45:42

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

Décration de salle de bain

@caduk : c'est parfait !

 #9 - 10-03-2017 12:43:25

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

décoration de salle de baib

Bonjour,
Si j'ai bien compris, (maintenant), je trouve 13 pour 3 noeuds, 19 pour 5 noeuds et bizarrement, je ne trouve pas mieux que 20 pour 4 noeuds...
http://www.prise2tete.fr/upload/gwen27-noeuds345.PNG

 #10 - 10-03-2017 17:50:47

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

Déocration de salle de bain

@gwen27 : très jolis dessins, très clairs ! C'est bon pour [latex]3_1[/latex] et [latex]5_1[/latex], mais de manière surprenante, on peut faire mieux pour [latex]4_1[/latex] et [latex]5_2[/latex]. Pour cela, il y a une certaine astuce pas évidente à imaginer...

 #11 - 11-03-2017 08:30:36

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

Décoration de aslle de bain

Je ne trouve pas mieux pour 5-2 , il faut surement faire un faux croisement quelque part...

Par contre j'ai un truc rigolo avec 4-1, on doit toujours pouvoir faire au moins aussi bien avec 4-1 qu'avec 5-2:

http://www.prise2tete.fr/upload/gwen27-noeud4152.PNG

Et une petite amélioration de l'un avec 2 faux croisements (et donc de l'autre ) ce qui donne 17 :
http://www.prise2tete.fr/upload/gwen27-noeuds524117.PNG

 #12 - 11-03-2017 16:13:01

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

décoration de sallz de bain

@gwen27 : parfait !

 #13 - 12-03-2017 12:14:08

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 474

décoeation de salle de bain

Merci et félicitations aux participants. La subtilité de l'énigme, c'est que pour trouver la solution optimale de [latex]4_1[/latex] ou [latex]5_2[/latex], il faut recourir à des croisements inutiles, ce qui est assez surprenant.

 #14 - 12-03-2017 14:45:38

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 209

décoratuon de salle de bain

Pour le 4, j'ai finalement réussi à le démontrer, mais je ne posterai pas la démonstration dans le détail parce que c'est beaucoup d'études de cas.
On peut remarquer qu'il suffit de démontrer le résultat pour seulement 4 croisements, car sinon, il faut minimum 6 croisements, et on a démontré qu'à partir de 5 croisements, on ne pouvait pas faire mieux que 17.

Ici,  ┼ désigne un croisement, o une dalle avec seulement deux extrémités, * une dalle à déterminer(pas un croisement),
On peut essayer de trouver quelques propriétés:
1)On ne peut pas avoir une boucle de 4 cases avec un croisement au début de la boucle (sinon, le nœud peut se simplifier en déroulant cette boucle (voir le "faux nœud" de franck, chacune des extrémités est une boucle qui peut être déroulée, et au final, on a pas le nœud 4) Cette propriété fonctionne car on étudie le cas 4 croisements, donc chaque croisement est essentiel dans le nœud.
2)le shéma
┼*┼
se simplifie en:
┼─┼
3)le schéma:
┼*┼
*┼*
est impossible
4)le schéma
┼*
  ┼
se simplifie en:
┼┐
  ┼
etc...

A partir de là, on étudiant chaque configuration de 4 croisements telle que l'application des 3 propriétés de mon premier message reste inférieure à 17, on peut utiliser ces propriétés pour construire les "chemins" surement suivis par la ficelle.
Ensuite, une très courte étude de cas suffit à montrer que si l'on cherche à relier les différents bouts de manière à obtenir un chemin continu passant partout, on ne parvient jamais à le faire en moins de 17 coups. Il n'y a pas tant de cas à analyser que ça, et grâce à ces propriétés, l'étude va très vite...

il ne reste donc plus que le nœud 5.1, ça doit pouvoir se faire de la même manière, mais en un peu plus long (grosso modo, faut tester toute les pièces du jeu blokus, plus les possibilités qui sont reliées par un coin, et 1 ou 2 pas reliées du tout... et ça en fait pas mal!

Sinon, il faut trouver une autre méthode, j'avais tenté un peu de théorie des graphes, mais ça n'a pas donné grand chose...

des prétendants pour les 3 nœuds à 6 croisements?

 

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 : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
19-09-2010 Enigmes Mathématiques
P2T
L'heure du bain par Sydre
29-05-2015 Enigmes Mathématiques
P2T
Enigme mathématique. par John1999
16-06-2013 Enigmes Mathématiques
20-08-2008 Enigmes Mathématiques
P2T
Chute d'assiette par Imingso
20-12-2010 Enigmes Mathématiques
P2T
Une très simple ! par MthS-MlndN
07-01-2014 Enigmes Mathématiques
P2T
Gâteau 37 par Vasimolo
19-04-2011 Enigmes Mathématiques
P2T
Le pâtissier gaucher par Vasimolo
22-08-2009 Enigmes Mathématiques
P2T
Pavages et chemins par Clydevil
01-02-2017 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