Edit : ma démonstration n'est pas valide (voir les posts suivants), inutile de lire ce post

Il semble que je sois condamné à détaille mes explications à chaque fois

A l'avenir, essayer de préciser quel point pose problème, ça m'évitera de tout réexpliquer à chaque fois.

Dans ma démonstration par l'absurde, il faut considéré que je prends les cotés dans l'ordre croissant des longueur (ce qui ne change rien), sans me soucier de fermer le polygone avant le 733eme coté. La seule contrainte que doit vérifier le "prépolygone" est qu'un coté doit posséder au plus un autre coté parallèle pour assurer la convexité à la fin.

On peut toujours définir la notion de périmètre pour ces prépolygones convexes comme la somme des |a|+|b| où les (a,b) sont les cotés.

Pour un prépolygone convexe de N cotés quelconques, on peut minimiser son périmètre en réduisant chaque couple (ka,kb) en (a,b) où a est premier avec b, ça légitime le fait de ne considérer que les a premier avec b pour minimiser le périmètre.

Ensuite, toujours pour minimiser le périmètre, on prends les N cotés dans les N premier couples (a,b) rangés par longueur |a|+|b| croissante.

Dans ces conditions pour N=732 cotés, ma liste dans mon premier post (+ leurs 4 ou 8 variations) satisfont à ces conditions de minimalité. Donc le périmètre minimal d'un prépolygone de 732 cotés est bien 4*2993.

Les seul libertés pour choisir ce prépolygone minimal de 732 cotés est le choix des derniers cotés parmis ceux de longueurs 25. On a vite fait de voir que pour que le prépolygone reste encadré dans un carré de 3000 de coté, la seule manière de faire est de choisir ces cotés de longueur 25 de manière à ce qu'on forme un polygone convexe inscrit dans un carré de 2993 de coté.

On ne peut bien entendu pas rajouter un 733eme coté à ce polygone sans sortir du carré 3000.

Mais peut être qu'il existe une solution de 733 cotés valide mais ne respectant pas la stratégie de minimisation du périmètre. Dans ce cas les 732 cotés les plus courts forme un prépolygone non optimal de périmètre forcément > 4x2993.

Le 733eme coté (le plus long) est au moins de longueur 25. Si la longueur ou la largeur du prépolygone était déja de 3000, le 733eme coté devrait être de type (0,x). Cela signifierais qu'un des couples de type (0,1) n'est pas utilisé à cause de la contrainte du maximum de 2 cotés parallèle. Cela décalerait les couples choisis dans la liste en rajoutant au moins 25-1=24 au périmètre minimal de 4x2993 du prépolygone de 732 cotés (il n'y aurait plus que 4 de marge avant 4x3000, pas de quoi caser le 733eme coté).

Donc le 733eme coté rajoute au moins 1 à la largeur et à la hauteur du prépolygone (si on utilise un couple du type (1,x) avec x>=24). Donc le prépolygone doit nécessairement être inclus dans un carré de 2999 de cotés.

Le cotés le plus court du rectangle dans lequel est inscrit le prépolygone est donc supérieur à (2993x4-2999x2)/2, donc au moins de longueur 2988.

Enfin, en rajoutant le 733eme coté à ce prépolygone, une des composantes sera au moins de longueur 13 (avec le couple (12,13)).
2988 + 13 = 3001.
CQFD

Cette fois j'espère que tout est claire

Bien vu gwen, je me suis piégé moi même avec mon astuce de prendre des polygones incomplet : en rajoutant le dernier coté, en fait on n'augmente même pas du tout la taille! On ne fait que fermer le polygone.

Le mystère reste entier...

Quand tu dis que tu rajoute un exemplaire du 0-1 et du 1-1, tu veux dire que tu rallonge un 0-1 en 0-2, et un 1-1 en 2-2 ?
Parce qu'autrement les 8 couples de type 0-1 et 1-1 étaient déjà tous utilisés dans mon premier polygone.

Je rappelle ce que j'avais fais : pour les couple que listé j'en utilisait dans l'ordre 4,4,8,8,8,...8,4. Toutes les variations de signe et permutation abscisse/ordonnée était utilisé sauf pour le dernier couple 2-23 utilisé 4 fois seulement, alors qu'il existe comme pour les autres (excepté 0-1 et 1-1) 8 variations.

Bravo à tous les deux

Il est rassurant de voir que l'affaire se termine car il semble que nous commencions à agacer sérieusement les plus conciliants

Il est donc temps d'offrir notre cadeau et de passer le relai :



Un grand merci à tous en général et à Gwen et Mathieu en particulier

Pour clore le sujet, j'ai écris un JavaScript pour vérifier et faire les dessins.

Il y a deux dessins :
1)  les vecteurs partant tous du centre de l'image
2) la forme finale à l'échelle 0.3 pixel = 1 point

Le résultat affiché dans la console me dit:
"cotés : 733, périmètre : 11988, largeur : 2997, hauteur : 2997, sommeX : 0, sommeY : 0"

Je m'étais donc un peu trompé (j'avais compté en double (0,1) et (1,1)) mais de toute manière il n'y a pas de quoi rajouter un coté supplémentaire avec une marge de 40 au lieu de 28 pour le périmètre.
Du coup il y a sûrement encore plus de solutions à 733 cotés.

Pour afficher les résultats et dessiner les images :
-pour Chrome Ctrl+Maj+J
-pour Firefox Ctrl+Maj+K
coller le code dans la console et exécuter le en appuyant sur entrée.
Scroller en bas de la page pour voir les images.

var all=[ [1, 2], [1, 3], [1, 4], [2, 3], [1, 5], [1, 6], [2, 5],
  [3, 4], [1, 7], [3, 5], [1, 8], [2, 7], [4, 5], [1, 9], [3, 7], [1, 10],
  [2, 9], [3, 8], [4, 7], [5, 6], [1, 11], [5, 7], [1, 12], [2, 11],
  [3, 10], [4, 9], [5, 8], [6, 7], [1, 13], [3, 11], [5, 9], [1, 14],
  [2, 13], [4, 11], [7, 8], [1, 15], [3, 13], [5, 11], [7, 9], [1, 16],
  [2, 15], [3, 14], [4, 13], [5, 12], [6, 11], [7, 10], [8, 9], [1, 17],
  [5, 13], [7, 11], [1, 18], [2, 17], [3, 16], [4, 15], [5, 14], [6, 13],
  [7, 12], [8, 11], [9, 10], [1, 19], [3, 17], [7, 13], [9, 11], [1, 20],
  [2, 19], [4, 17], [5, 16], [8, 13], [10, 11], [1, 21], [3, 19], [5, 17],
  [7, 15], [9, 13], [1, 22], [2, 21], [3, 20], [4, 19], [5, 18], [6, 17],
  [7, 16], [8, 15], [9, 14], [10, 13], [11, 12], [1,23], [5, 19], [7, 17],
  [11, 13], [1, 24]],
except=[[5,19],[23,1]],
add=[[-7,18],[17,9],[18,-7],  [2, 23],[-2,-23],[23,2],[-23,-2],   [0,1],[0,-1],[1,0],[-1,0],  [1,1],[-1,-1],[1,-1],[-1,1]],

canvas = document.createElement('canvas'),
g=canvas.getContext('2d'),
sommeX = 0,
sommeY = 0,
W=0,
H=0,
perimetre=0,
cotes = 0,

ratio = 20;

canvas.height=canvas.width=50*ratio;
g.fillStyle = "red";
function line(x,y,w,l){
    g.beginPath();
    g.strokeWidth=1;
    g.moveTo(x*ratio,y*ratio);
    g.lineTo((x+w)*ratio,(y+l)*ratio);
    g.stroke();
    g.beginPath();
    g.strokeWidth=0;
    g.arc((x+w)*ratio, (y+l)*ratio, 2, 0, Math.PI*2, true); 
    g.fill();
}
function vect(x,y){
    line(25,25,x,y);
    cotes++;
    sommeX+=x;
    sommeY+=y;
    if (x>0) W+=x;
    if (y>0) H+=y;
    perimetre+=Math.abs(x)+Math.abs(y);
}
g.strokeStyle = "#aaaaaa";
for (var i=0; i<50; i++){
    line(0,i,50,0);
    line(i,0,0,50);
}
var x,y;
for (var v in all) {
    x=all[v][0]; y=all[v][1];
    add.push([x,y],[-x,-y],[-x,y],[x,-y],[y,x],[-y,-x],[-y,x],[y,-x]);
}

add.sort(function (v,w) {return Math.atan2(v[0],v[1])-Math.atan2(w[0],w[1]);});

g.strokeStyle = "black";
for (var v in add) {
    x=add[v][0]; y=add[v][1];
    if ((x!=5 || y!=19) && (x!=23 || y!=1))
        vect(x, y);
}
document.querySelector('body').appendChild(canvas);
canvas.parentNode.style.textAlign = "center";

ratio = 0.3;
var c2 = document.createElement('canvas');

c2.height=c2.width=3000*ratio;
g = c2.getContext('2d');
g.fillStyle = "red";
g.strokeStyle = "black";
var xx=2999,yy=1508;
for (var v in add) {
    x=add[v][0]; y=add[v][1];
    if ((x!=5 || y!=19) && (x!=23 || y!=1))
    {
        g.beginPath();
        g.moveTo(xx*ratio,yy*ratio);
        xx+=x; yy+=y;
        g.strokeWidth=0.5;
        g.lineTo(xx*ratio,yy*ratio);
        g.stroke();
        g.beginPath();
        g.strokeWidth=0;
        g.arc(xx*ratio, yy*ratio, 1, 0, Math.PI*2, true); 
        g.fill();
    }
}

document.querySelector('body').appendChild(c2);


"cotés : "+cotes
+", périmètre : "+perimetre
+", largeur : "+ W
+", hauteur : "+H
+", sommeX : "+sommeX
+", sommeY : "+sommeY;

Enjoy !

Le nombre maximum de côtés prévus par la grossière majoration Manatthan :



Au moins jusqu'à [latex]n=9[/latex] ce maximum peut être atteint .



après ...

Vasimolo

Bonjour,
12000 ne me semble pas une bonne réponse, en revanche 3000 conviendrait (plus grand polygone plat) !
Plus sérieusement, il faudrait effectivement essayer de trouver une règle générale, à partir d'exemples plus simples...
Pour le moment, je trouve seulement 220 côtés avec une méthode simpliste consistant à avancer selon des diagonales de rectangles de hauteur 1 et de longueur n, n-1, n-2,...,2,1,0 jusqu'à atteindre la moitié de la hauteur soit 1500 : n(n+1)/2=<1500 pour n=54. Avec le côté verticale, cela donne 55 et en reportant sur les 3 autres quadrants, cela fait 55*4=220.

J'ai beaucoup tardé à poster, ce post je l'avais écrit en tout début d'après-midi je crois ! Vous avez vraiment bien mieux bossé que moi !
En fait, non c'est parce que je n'ai dû lire que la 1ère page de posts...

Ce n'est pas tout à fait ça ce que j'ai dit

Le périmètre d'un polygone convexe inscrit dans un quadrillage [latex]n\times n[/latex] est inférieur ou égal à [latex]4(n-1)[/latex] . Il y a en tout [latex]4\sum_{i=1}^k\varphi(i)[/latex] côtés possibles de longueur inférieure ou égale à [latex]k[/latex] . On cherche alors le [latex]k[/latex] maximal tel que [latex]4\sum_{i=1}^ki.\varphi(i)\leq4(n-1)[/latex] et on divise la longueur restante sur le périmètre pour voir combien de côtés de longueur [latex]k+1[/latex] on peut encore ajouter . C'est le tableau que j'ai joint au message #61 .

La première faille apparaîtrait pour [latex]n=11[/latex] , à confirmer .

Vasimolo