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

 #26 - 13-05-2015 08:52:37

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

Gâteeau 98

Et avec seulement 6 pts, quel est le trajet max ? On supposera un carré de coté 1.

#0 Pub

 #27 - 13-05-2015 12:54:17

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

Gâtea u98

http://www.prise2tete.fr/upload/Vasimolo-Solutiongateau98.png

il me semble que le chemin pourrait se recouper non ?

 #28 - 13-05-2015 13:40:05

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

gâreau 98

Salut Titoufred,
Une chose est sûre, le chemin que tu as choisi n'est pas le plus court !
Je crois que, dans le cas du 6 pts, il faut oublier la méthode par bandes ou par carrés.

 #29 - 13-05-2015 18:30:04

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

gâreau 98

Bonjour Nodgim

Dans cette disposition les parcours rouges et bleus sont de même longueur :

http://www.prise2tete.fr/upload/Vasimolo-Sispoints.png

Si on déplace un point on raccourcit l'un d'entre eux .

Sauf erreur smile

Vasimolo

 #30 - 13-05-2015 18:48:08

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

Gâtea u98

C'est aussi ma solution Vasimolo. Je n'ai pas pu trouver une autre config qui donnerait un chemin plus long, mais je ne prouve pas non plus que ça n'existe pas. Une certitude toutefois: les 4 pts aux sommets du carré.

 #31 - 14-05-2015 01:32:01

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

gâteai 98

Tout d'abord merci à Vasimolo pour son appétissant gâteau, le sujet est très intéressant.

En sortant l'artillerie lourde, il me semble que j'ai une légère amélioration à apporter au problème initial.

En premier lieu, remarquons qu'il n'est pas nécessaire de se soucier des croisements éventuels quand on recherche une solution. En effet, si un chemin passant par tous les points contient au moins un croisement, alors on sait qu'il existe un chemin plus court, comme le montre l'illustration (le raccourci est tracé en rouge, il fournit un chemin strictement plus court par l'inégalité triangulaire).

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

Pour résoudre notre problème, on va déterminer une ligne brisée qui passe par nos 49 points. Pour savoir dans quel ordre on va visiter ces 49 points, nous allons avoir recours à la courbe de Sierpinski.

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

Nul besoin de considérer la courbe de Sierpinski limite, qui s'auto-intersecte, ce qui complique les choses. On la trace juste avec un nombre d'itérations suffisant pour qu'elle passe à une distance suffisamment proche des 49 points, pas plus loin que epsilon, epsilon étant en définitive aussi petit que l'on veut.

Les 49 points sur la courbe de Sierpinski correspondent à 49 nombres de [0;1[. On relie ainsi ces 49 points dans l'ordre des 49 nombres, par des segments. Remarquons qu'il est alors possible que la ligne brisée obtenue s'auto-intersecte, d'où notre remarque en préambule.

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

Nous allons ensuite avoir recours à un lemme pour majorer la longueur de la ligne brisée. Chaque point de la courbe est repéré par un nombre de [0;1[, et on suppose que le carré est de côté 1 pour simplifier les calculs (on ne tiendra compte des 20 cm de côté qu'à la fin).

Lemme : si deux nombres de [0;1[ sont à une distance d (cela boucle : par exemple, la distance entre 0,9 et 0,1 est de 0,2), alors les deux points correspondants sur la courbe de Sierpinski sont à une distance inférieure ou égale à 2*racine(d).

Par exemple, les points repérés par 1/8 et 3/8 sont à la distance 1/4 sur [0;1[, et à la distance 1 sur la courbe, or 2*racine(1/4)=1 (c'est un cas où il y a égalité).

On peut maintenant majorer la longueur de la ligne brisée. Si on appelle d_i les distances entre deux nombres consécutifs sur [0;1[, alors on a somme(d_i)=1, et la longueur de la ligne brisée est <= somme(2*racine(d_i)) par le lemme. Par concavité de la fonction racine, on obtient que cette somme est <= 49*2*racine(1/49).

Enfin, on peut gratter un chouïa en se débarrassant d'une des 49 liaisons entre deux points (autant choisir la plus grande), pour passer d'une courbe fermée à une courbe ouverte. La longueur de la ligne brisée est donc au plus 48*2*racine(1/49)*(20 cm) = 1920/7 cm ~ 274,3 cm. Tout ça pour ça smile

 #32 - 14-05-2015 11:23:59

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

gâtzau 98

Je n'ai pas compris comment sont numérotés les points de la courbe de Sierpinski , il y a une explication simple ou une référence compréhensible sur la toile ?

Vasimolo

 #33 - 14-05-2015 12:47:30

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Gtâeau 98

La construction de la courbe est illustrée ici :

http://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve

Quel que soit l'ordre de la courbe, on pose à 0 le point de la courbe situé juste au dessus du centre du gâteau, puis on tourne autour de la courbe dans le sens des aiguilles d'une montre. Si on sépare le gâteau en 4 carrés plus petits, le carré en haut à droite contient les points entre 0 et 1/4, celui en bas à droite contient les points entre 1/4 et 1/2...

C'est plus clair, ou je précise encore ?

 #34 - 14-05-2015 18:45:24

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

Gâteu 98

D'accord , j'ai compris l'idée . C'est marrant qu'un chemin aussi tordu puisse faire mieux que des bandes des carrés ou des spirales .

Vasimolo

 #35 - 14-05-2015 22:31:31

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

gâtrau 98

S'il est vrai que la courbe de Sierpinski est tordue, elle ne sert qu'à déterminer l'ordre dans lequel les points seront visités. La ligne brisée obtenue n'est elle pas si tordue que ça, cf la 3e illustration.

Et puis, ça ne permet de gagner qu'un micropouième par rapport à la méthode de Promath-...

Je me suis rendu compte a posteriori que l'idée n'était pas si originale que ça : http://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve "it has been used as a basis for the rapid construction of an approximate solution to the Travelling Salesman Problem (which asks for the shortest sequence of a given set of points): The heuristic is simply to visit the points in the same sequence as they appear on the Sierpiński curve".

 #36 - 14-05-2015 23:35:06

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

Gâteua 98

Si on prend un point au hasard et qu'on visite successivement le point le plus proche non déjà visité, on doit arriver sur un bon score. Mais où est la preuve?


Un promath- actif dans un forum actif
 

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 : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 42 par Vasimolo
29-10-2011 Enigmes Mathématiques
P2T
Gâteau 20 par Vasimolo
03-08-2010 Enigmes Mathématiques
P2T
Gâteau 49 par Vasimolo
13-12-2011 Enigmes Mathématiques
P2T
Gâteau 86 par Vasimolo
26-12-2014 Enigmes Mathématiques
P2T
Gâteau 99 par Vasimolo
13-06-2015 Enigmes Mathématiques
P2T
Gâteau 19 par Vasimolo
31-07-2010 Enigmes Mathématiques
P2T
Gâteau 79 par Vasimolo
29-06-2014 Enigmes Mathématiques
P2T
Gâteau 56 par Vasimolo
16-11-2012 Enigmes Mathématiques
P2T
Gâteau 119 par Vasimolo
18-01-2016 Enigmes Mathématiques
P2T
Gâteau 73 par Vasimolo
27-02-2014 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