Demonstration

[Nathan27383]

Bonjour,
Dans le cadre d'un projet en math, j'aimerai démontrer la minimalité d'un algorithme permettant de relier deux points à coordonnées entières :
Avec A(0;0) et B(xb;yb), dans un repère orthonormé de vecteur unitaire x et y on se donne l'algorithme suivant : monter de 1. Ensuite, allez à droite jusqu'à rencontrer le droite AB et arrêtez-
vous au point de coordonées entières suivant cette rencontre. Ensuite, montez jusqu'à croiser la courbe et arrêtez vous sur le pt de coordonées entières juste après. Si le point d'arrivée n'est pas B, recommencez ( sans monter de 1 du début bien sur).

On peut aussi définir SR=l'ensemble des sommes de vecteurs tel que \sum{\gamma x+ \beta y} = au vecteur AB
On pose #Sk = \sum{\beta +\gamma }.
Notre algorithme donne un chemin tq #Sk(chemin parcouru par cet algo) = min (ensemble des #Sk)

Je ne sais pas si c'était très clair, mais pour le dire avec des mots cet algo est censé donné le chemin le plus court entre deux pts de coordonnées entières avec un chemin ne s'arrêtant que sur des pts de coordonnées entières.

Quelqu'un aurait-il une idée de comment s'y prendre, sans forcément donner la réponse?
Merci beaucoup et bonne journée à vous

[lyceen95]

Question 1 :
A-t-on l'asssurance d'arriver en B avec cet algorithme ?
Normalement, l'exercice devrait commencer par cette question, ou il devrait préciser : 'on admettra que cet algorithme permet bien d'arriver en B'

Question 2 :
Au final, quelle est la longueur de ce chemin ?

Question 3 :
Peut-il exister d'autres chemins, plus courts , allant de A à B.

[Nathan27383]

Merci, je me doutais de la question 1 mais je n'avais pas pensé à évaluer la longueur du chemin. Je vais essayer ca.