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).
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.
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.
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 
Accueil
