1. Enoncé
Voici un problème provenant du passionnant site
Diophante et proposé par Michel Lafond.
Dans un carré de 10 cm x 10 cm, tracer une ligne continue L = A ... B de longueur minimale, telle qu'aucun point du carré ne soit à plus d'un centimètre de L. Une façon moins formelle de présenter le problème pourrait être : un robot doit trouver toute trace de métal dans un carré de 10 mètres de côté à l'aide de son détecteur embarqué d'une portée de 1 mètre. Afin d'éconimiser l'énergie, on cherche à définir le chemin le plus court possible. Philippe Fondanaiche, responsable du site Diophante m'a assuré qu'il existe une solution de longueur inférieure à
54.47 cm. Pour faciliter les recherches, vous pouvez consulter la
page de test.
2. Proposition
2.1. Spirale épineuse
On peut essayer une spirale en jouant sur l'écart entre les traits et en paufinant pour les angles. Par exemple la ligne suivante a une longueur de 49 cm, mais elle ne répond pas à l'énoncé puisqu'il existe des régions où les points sont à plus d'un cm du trait le plus proche.
Dans cette figure on a agrandi la partie inférieure gauche et marqué en vert les régions où les points respectent l'énoncé. Il reste juste de toutes petites zones en forme de deltaplane qu'il nous faut recouvrir. Pour cela, il suffirait de passer par un point situé à 1 cm de la pointe du deltaplane.
Nous allons donc ajouter un aller retour en diagonale de
cm.
Le tout dernier trait utilise le même procédé, mais évite un aller-retour pour gagner sur la longueur. Au final, on aura une ligne de longueur totale :
56.6274 cm.
Il faut noter que si la ligne n'était pas nécessairement continue, nous n'aurions pas à doubler la longueur des pointes dans les coins de la spirale et nous obtiendrions alors une longueur de : 53.3137 cm.
2.2. Serpentin piquant
Nous allons chercher une forme de base plus courte. Le «
radiateur » à gauche mesure 50 cm ce qui est plus long que la spirale, mais en contrepartie, il nécessite une pointe de moins. La longueur de la courbe, dans ce cas, est :
56.6274 cm.
On obtient exactement la même longueur, mais on peut optimiser les allers-retours des pointes en en reliant les bouts comme dans le dessin ci-contre dont la longueur tombe alors à
55.66 cm.
Pour voir s'il est possible de faire mieux, nous allons tenter de déplacer les pointes et calculer la longueur résultante. Vous pouvez vous faire une idée de ce déplacement dans l'animation ci-contre. Calculons la longueur de la ligne en fonction de l'angle que fait le segment allant du centre du cercle vert à la pointe.
Et puisque le point variable décrit un cercle de rayon unité, on a :
et
. Il vient donc :
Nous procédons par dichotomie pour trouver le meilleur angle grâce à un petit programme en Python.
[voir le code source]import math
def g(a):
S = math.sin(a)
C = math.cos(a)
return 2 - C + math.sqrt(3 - 2*(C + S))
def f(a):
S = math.sin(a)
C = math.cos(a)
return S - (C - S)/math.sqrt(3-2*(C + S))
def findZero(precision):
a = 0
b = math.pi/2
fa = f(a)
fb = f(b)
while fb - fa > precision:
c = (a + b)/2.0
fc = f(c)
if fc < 0:
a = c
fa = fc
else:
b = c
fb = fc
return (a + b)/2
zero = findZero(0.000000001)
a = 1 - math.cos(zero)
b = 1 - math.sin(zero)
print "a = %.9f" %(a)
print "b = %.9f" %(b)
Et cela nous amène à une longueur de moins de
54.79 cm.
Mais il est encore possible d'améliorer la situation en remarquant que les segments horizontaux (qui relient des pointent) recouvrent une zone de 2cm d'épaisseur et que cela nous permet de déplacer les coins à la base des pointes comme le montre l'illustration à droite.
On passe alors à une longueur inférieure à
54.61 cm. Pour affiner encore un peu, il faut regarder les extrémités de notre courbe. Peut-être que le dernier segment serait plus court s'il n'était pas horizontal.
Voici les différentes mesures des segments rouges sur le schema de droite. Les valeurs de
et
sont déduites de la valeur de l'angle optimal des pointes calculé plus haut par dichotomie :
-
-
-
-
-
Actuellement, le dernier segment de notre ligne a une longueur de
. En le déplaçant dans l'axe
, il devient
. On arrive alors à une longueur inférieure à
54.52 cm.
Il est peut-être possible d'aller plus loin puisque nous avons optimisé les deux derniers segments de notre ligne l'un après l'autre. Que se passe-t-il si nous tentons une optimisation simultanée. On a vu qu'une fois l'avant dernier point placé (le point
), il suffit que le dernier segment soit aligné sur
pour qu'il soit le plus court possible. Sa longueur dépend biensûr de la position du point
qui se déplace sur un cercle de rayon unité centré en
.
Point | abscisse | ordonnée |
| | |
| | |
| | |
| | |
| | |
Voici les coordonnées des différents points en fonction de l'angle
(l'axe des ordonnées est dirigé vers le bas). L'ordonnée de
vaut au maximum 2. Pour calculer la longeur des deux derniers segments, il ne faut pas oublier d'ajouter une partie verticale qui descent sous
. Nous l'arrêterons à l'ordonnée 2.
Ainsi la longeur (en fonction de
) est composée de trois sections :
- le dernier segment de longueur ,
- le segment CD et
- la partie verticale de longueur .
On obtient la fonction
, de dérivée
Une nouvelle dichotomie nous donne la valeur de
. On a encore gagné un dixième de milimètre :
54.51 cm. On constate que le segment
n'est plus parallèle à
. On peut donc essayer de déplacer le point
pour tenter de raccourcir encore le parcours. On est soumis aux contraintes suivantes :
Point | abscisse | ordonnée |
| | |
| | |
| | |
| | |
| | |
- les points et sont fixes,
- l'ordonnées de est variable, mais sont abscisse doit rester égale à ,
- la distance entre et la droite doit être de 1 cm,
- ne doit pas être trop verticale pour ne pas perdre en recouvrement.
Pour calculer
, il faut trouver la distance de
à la droite
d'équation
et dire qu'elle vaut 1 cm. Il faut donc résoudre :
Puisque la droite
ne peut pas être verticale, on peut se ramener à une équation simplifiée
en posant
. Ainsi, il suffit maintenant de résoudre :
Une étude graphique montre que la longueur est minimale quand
vaut approximativement
radians. Encore une fois, c'est un programme Python qui nous es venu en aide.
[Code source] import math
Mx = 5.173056575
My = 0.562285134
def f(alpha, precision):
S = math.sin(alpha)
C = math.cos(alpha)
Kx = 2.0 + C
Ky = S
a = (Ky - My)/(Kx - Mx)
aa = math.sqrt(a*a + 1.0)
c = My - Mx*a
Lmin = 0.0
Lmax = 3.0
valLmin = abs(3*a - Lmin + c) - aa
valLmax = abs(3*a - Lmax + c) - aa
if valLmin > valLmax:
valLmoy = valLmin
valLmin = valLmax
valLmax = valLmoy
while valLmax - valLmin > precision:
Lmoy = (Lmin + Lmax)/2
valLmoy = abs(3*a - Lmoy + c) - aa
if valLmoy < 0:
Lmin = Lmoy
valLmin = valLmoy
else:
Lmax = Lmoy
valLmax = valLmoy
Ly = (Lmax + Lmin)/2
length = math.sqrt((Mx - Kx)**2 + (My - Ky)**2) + math.sqrt((Kx - 3)**2 + (Ky - Ly)**2) - Ly
return (Ly, length)
min = 0
max = math.pi/2
steps = 1000
step = 0
zx = 1
lengthMin = 10.5
lengthMax = 2.7
alphaMin = 0
zy = 1000/(lengthMax - lengthMin)
while step < steps:
alpha = min + ((max - min)*step)/steps
(Ly, length) = f(alpha, 0.000000001)
if length > lengthMax: lengthMax = length
if length < lengthMin:
lengthMin = length
alphaMin = alpha
x = step*zx
y = 1000 - (length - lengthMin)*zy
print "L%.3f,%.3f" %(x, y),
if step %5 == 0:
print
step = step + 1
print
print "alpha = %.9f, length = %.9f" %(alphaMin, lengthMin)
print "x = %.3f" %((1000.0*alphaMin)/(math.pi/2.0))
On en déduit donc que
et
. Et on tombe alors à
54.49 cm.
Il suffit alors de généraliser cette dernière optimisation à toutes les pointes et on obtient alors une longueur égale à
54.44180 inférieure à :
54.45 cm. Nous nous arrêtons là faute d'idée nouvelle, mais il est probable qu'on puisse encore faire mieux. En effet, nos optimisations n'ont jamais été globales à la ligne entière : on a toujours optimisé en fixant des points que l'on a fait varier dans une seconde étape.