Je ne vois pas trop la subtilité de ton lien, je vois les choses comme ça :



ABCD est-il un polygone? et si D est à l'extérieur relié par un segment au point A par exemple?

Vu comme ça effectivement mais je ne suis pas d'accord pour tes 12000 côtés.

Et non 12000 justement....

@Cogito : un carré a quatre côtés, on est d'accord ? Or, si on considère qu'il peut y avoir des "points intermédiaires" et des angles plats au milieu, un carré peut avoir n'importe quel nombre de côtés supérieur ou égal à 4. Un peu ennuyeux. Le fait de pouvoir définir le nombre de côtés et de sommets d'un polygone de façon unique exige d'interdire la présence d'une succession de trois points alignés.

Et c'est une façon d'ergoter sur des définitions d'un niveau élémentaire (pour le plaisir de faire passer ta solution absurde comme valide ?)

@shadock : oui mais comme le carré a 4 cotés ...
@Mths-MlndN : Non, si on prend un carré et que on rajout un point intermédiaire alors nous obtenons un pentagone (avec 4 angle droits et un angle plat) et plus un carré (et ce pentagone est unique pour un point intermédiaire fixé).

Sinon j'ai très bien compris que ma solution proposé n'est pas l'objectif de l'exercice, elle n'est pas valide. Je ne pensais pas qu'il y aurait eu tant de controverse sur la définition de polygone.

@Lise-et-Paris : Je ne connaissais pas cette définition. Pardon pour le bruit occasionné.

Peut-être en regardant du côté des distances Manhattan ou Taxi-cab http://fr.wikipedia.org/wiki/Distance_de_Manhattan

Vasimolo

Je vais essayer de répondre aux 3 questions au mieux :

1°) Pourquoi choisir des vecteurs de sens différent ?

Je ne suis pas sûr de la question.

Je précise ma représentation du polygone : je vois un polygone comme une suite de "flèche" mises bout à bout, elles partent d'un sommet du polygone vers le suivant dans le sens de parcours choisi. En soustrayant les coordonnées d'un point au suivant, on obtient les vecteurs qui nous intéresse, représenté par les "flèche" si on fait le dessin.

Forcément chaque fois qu'on s'éloigne du point de départ sur un axe, il va falloir faire le chemin opposé pour retourner au départ : le sens des vecteurs varie. La somme nulle vient de là (le calcul est immédiat en développant la somme des vecteurs avec la différence des coordonnées des points consécutifs)

Mais je pense que vous aviez compris ça.
Peut être que par "sens différent" vous parlez des 8 variations que je fais subir aux couples (a,b).
Intuitivement, on se dit que pour avoir le plus possible de côté, il faut choisir des vecteurs les plus "petit" possible. Si on en trouve un petit, autant utiliser ses 8 autres variantes qui ont la même "taille" (leur somme est nulle).
Avec la contrainte du quadrillage, si un vecteur s'écrit (ka,kb) alors le segment passera par k+1 point du quadrillage (en faisant varier k dans {0,1,2...k} on tombe sur des coordonnées entières), donc on peut réduire la taille du polygone en transformant (ka,kb) en (a,b), et en faisant de même pour (-ka,-kb) qui devient (-a,-b).
C'est de là que vient la contrainte "a est premier avec b" que je rajoute.

2°) Des vecteurs de somme nulle de sens différents sont-ils nécessairement les côtés d'un polygone convexe ?

Absolument! Et je vous remercie pour l'énigme, car c'est en réfléchissant dessus que j'ai trouvé une preuve : Si on observe un polygone convexe "fléché", les flèches doivent toujours "tourner" dans le même sens.
C'est a dire pour 4 point consécutif A, B, C, D si l'angle (AB,BC) est positif dans [-pi,pi] alors il en est de même pour (BC,CD), sinon les milieux de [AC] et [BD] seraient de part et d'autre du polygone.

Cette propriété est aussi suffisante pour avoir un polygone convexe (ça doit se montrer par récurrence plus ou moins facilement suivant le baguage théorique à disposition sur la convexité)

Pour obtenir un polygone convexe à partir d'un jeu de vecteur de somme nulle, il suffit donc de ranger ces vecteurs par ordre croissant (ou décroissant) suivant l'angle qu'ils font avec un axe quelconque, puis de les mettre bout à bout dans cet ordre. (Il n'y a donc que deux polygones convexe possibles, symétriques l'un de l'autre).

3°) En choisissant les plus "petits" vecteurs de sens différents , quelle taille doit-on donner au quadrillage pour qu'il contienne le polygone ?

Cette question n'est pas très dure. Pour calculer la largeur, on somme tout les "a" de signe positif trouvés dans les vecteurs (a,b), et pour la hauteur, tout les "b" de signe positif.
C'est pour ça que je range les couples suivant les a+b croissants, car un couple ajoute 2(a+b) à la hauteur et à la largeur en sommant les valeurs positives trouvés dans les 8 variantes.

Voilà, ça fait un post un peut long avec plus de pistes que de véritables preuves, c'est pour ça que j'ai hésité à tout rédiger plus tôt...

Pour reprendre la piste donné par Vasimolo, le périmètre "de Manhattan" du polygone convexe inférieur ou égale à 4x3000 = 12000

Sachant que le nombre de cotés ayant la même longueur de Manhattan L est borné grossièrement par 8L, on doit pouvoir majorer le nombre de coté avec ça.

J'essayerai d'affiner la borne et de faire les calcules demain.

De toute façon, tu serais bien en peine de rajouter un segment (2,23), (12;13) ou équivanet vu que cela changerait la parité de ton parcours.

Il faut donc un couple à 26 ou 28, c'est encore pire.

La réponse est facile mais là, tu pollues un sujet qui n'a rien à voir.

Pourquoi ne pas le poster en ton nom ?

Vous n'êtes pas convaincus de grand chose tous les deux...

Je n'ai pas dit que c'était impossible de rajouter un 733è côté.
J'ai  juste dit que la somme des composantes des 732 plus petits vecteurs était de 11972 donc on ne peut pas se contenter d'en rajouter un de 23 vu que cette somme ne peut pas être impaire (il est bien fermé ce polygone ? )

Pour en rajouter un sans dépasser 12000 , soit il fait 26, soit il fait 28 , soit il faut en retirer un de 24 pour en rajouter 2 de 25 de longueur.

Je n'ai pas vraiment compris les raisonnements exposés ici. Mais mon idée était de dessiner une lentille à facettes partant d'un coin du carré au coin opposé. Le parcours retour serait alors symétrique au parcours aller, par rapport à la diagonale ou au point central du carré. En effet, si le parcours aller est optimisé, alors le parcours retour l'est aussi. Ceci impliquerait que le nombre de facettes est pair, mais mon idée de lentille en travers n'est peut-être pas correcte.