Un maximum de côtés

[Imod]

Je profite de la présence de Ben , Doraki , Nodgim , ...

Pour relancer un problème que j'ai déjà proposé aux mathématiques.net mais la lassitude a envahi tout le monde :zen:

Voilà la question :

Quel est le nombre maximal de côtés que l'on peut donner à un polygone convexe ayant ses sommets aux noeuds d'un quadrillage carré ?



On peut trouver "aisément" à la louche , une borne au nombre maximal de côtés du polygone et curieusement cette borne est réalisée pour toutes les premières valeurs de .

En bref peut-on prouver que cette borne est toujours atteinte ou trouver un contre-exemple ?

Imod

PS : ceux qui n'ont pas envie de chercher la formule peuvent se référer directement au site sus-nommé .

[Ben314]

Bon, juste pour dire que si je poste pas, c'est pas que je cherche pas, mais c'est ... que je trouve pas :cry:

J'ai l'impression que la borne est 2n, mais je trouve pas la preuve que c'est un majorant (bien qu'il soit "à la louche"... :mur: )
ET je trouve pas de polygone convexe avec 14 cotés dans un carré 7x7 alors que pour 2,3,4,5,6 j'ai des polygones à 4,6,8,10,12 cotés...


Donc... je continue à chercher...

[Imod]

Tu es sûr d'avoir 10 côtés pour 5X5 ?

Imod

PS : ne t'affoles pas trop si le problème te semble compliqué , il est fort possible qu'il soit ouvert :zen:

[nodjim]

En fait, Ben, le ratio c/n diminue avec n. Pour n=3000, un max a été trouvé à 733.

[Ben314]

Tu es sûr d'avoir 10 côtés pour 5X5 ?

Imod

PS : ne t'affoles pas trop si le problème te semble compliqué , il est fort possible qu'il soit ouvert :zen:

Non : je me suis gourré (et sans doute sur d'autres) : j'ai pris un carré de 5x5 (donc un quadrillage de 6x6...)

[Ben314]

Perso, j'en suis là :
En considérant "un quart" du bord, on a une série de vecteurs (a1,b1), (a2,b2), ... , (ak,bk) [ai dans N, bi dans N*] tels que : b1/a1 < b2/a2 < ... < bk/ak
Ce qui nous intéresse, c'est que k soit le plus grand possible pour a1+a2+...+ak+b1+b2+...+bk=S fixé (la somme des 4 "S" correspondant au 4 "quarts" du bord du polygone doit être égal au périmètre du carré, c'est à dire 4(n-1))...

S=1 -> 0/1 (k=1)
S=2 -> 1/1 ou 0/2 (dans les 2 cas, k=1 donc pas mieux que S=1)
S=3 -> 0/1<1/1 (k=2)
...
S=6 -> 0/1<1/2<1/1 (k=3)
...
S=9 -> 0/1<1/2<1/1<2/1 (k=4)
...

[Ben314]

Un "test" pour voir :
Avec un quadrillage de 20x20, je met au max un polygone à 25 cotés.
Et avec un 100x100, je met au max un polygone à 76 cotés.
C'est O.K. ?

[Imod]

Ton approche a l'air juste Ben sauf que la symétrie peut-être brisée dans de nombreux cas .

Une façon particulièrement efficace d'aborder le problème est de considérer la distance "Manatthan" , le périmètre du polygone pour cette distance fourni immédiatement une borne pour le nombre de côté .

Après il faut voir si cette borne est toujours atteinte .

Imod

[Ben314]

La "distance de manatthan", c'est bien ce que j'utilise (c'est ai+bi et c'est ça que je somme).
Mais je vois toujours pas comment en déduire un majorant "simple" du nombre de cotés.

C'est principalement lié au fait que je ne sais pas combien il y a de fractions irréductibles p/q avec p,q>0 et p+q=n fixé...
Modulo de calculer ces nombres (avec un petit programme), j'arrive à trouver des majorant du nombre de coté.
Je vais regarder ce que je trouve pour n=3000...

[Imod]

Le majorant simple est bien celui que tu annonces .

Je n'ai pas dit que son calcul était simple mais que l'idée de la majoration était naïve . Après en effet il faut voir si cette borne vraiment grossière est toujours atteinte , personnellement j'en doute .

Imod

[Ben314]

Donc, je retente mon coup :
pour n=41, mon majorant "calculatoire" est 2x10+2x11=42 mais je sais aussi qu'on ne peut pas faire de polygône à 42 cotés (i.e. que mon majorant consiste en une construction "non réalisable")

[Imod]

C'est le premier point "critique" que tu as obtenu ?

Imod

[Ben314]

Ton majorant, ça consiste pas à dire que
- des cotés dont la "longueur de manhattan" est 1, il y en a au plus 4 x 1
- des cotés dont la "longueur de manhattan" est 2, il y en a au plus 4 x 1
- des cotés dont la "longueur de manhattan" est 3, il y en a au plus 4 x 2
- des cotés dont la "longueur de manhattan" est 4, il y en a au plus 4 x 2
- des cotés dont la "longueur de manhattan" est 5, il y en a au plus 4 x 4
- des cotés dont la "longueur de manhattan" est 6, il y en a au plus 4 x 2
- des cotés dont la "longueur de manhattan" est 7, il y en a au plus 4 x 6
etc...
(évidement, si le coté coupe ailleurs qu'en ces extrémités un point du quadrillage, on compte uniquement la "longueur de manhattan" d'un des segments "irréductible" qui le compose)

Si c'est ça la majoration, alors, oui, je suis à peu prés certain qu'elle n'est pas "atteignable" pour n=42.

[Ben314]

C'est le premier point "critique" que tu as obtenu ?

Imod

J'ai l'impression que oui...

[Imod]

Je verrai tout ça demain à tête reposée mais je te fais confiance :zen:

C'est quand même surprenant qu'un majorant aussi "bête" tienne aussi longtemps . Il est d'ailleurs valable pour une infinité de valeurs du côté du carré .

Bonne nuit :dodo:

Imod

[Ben314]

Recherche des série de vecteurs (a1,b1), (a2,b2), ... , (ak,bk) avec ai dans N, bi dans N* tels que : b1/a1 [/B] k
(je ne met évidement que le plus petit S qui donne ce k là)
2em colonne : (a1+...+ak , b1+...+bk )
colonnes suivantes : liste des ai/bi


si on a un quadrillage de 41 sur 41, le périmètre du carré est 4x40=2*37+2*43 qui donne comme nombre max de cotés de 2*10+2*11=42.
Sauf que pour faire 11 coté, il faut utiliser (19,24) ou (23,20) et que sur les 40 de largeur totale d'un coté, si on en utilise 23 (ou 24), il n'en reste que 17 (ou 16) ce qui est insuffisant pour placer ensuite un (18,19) ou un (19,24) ou un (23,20)...
Par contre, on peut faire un polygone à 42 cotés dans un rectangle de 41x39 (= un quadrillage de 42x40) qui a le même périmètre qu'un carré 40x40 (41=23+18 et 39=20+19)

[Ben314]

Sauf erreur, il y a un "point critique" plus petit : pour un carré 10x10 (un quadrillage 11x11)
le périmètre est 4x10=40=13+9+9+9 mais on ne peut pas faire de polygone de 5+4+4+4 cotés.

[Doraki]

Je suis d'accord avec Ben314 pour n=10.

[Imod]

Je n'ai pas trop compris l'argument qui interdit le polygone à 42 côtés sur un quadrillage 41X41 . Le même argument explique-t-il l'absence de polygone à 17 côtés sur un quadrillage à 11X11 points ?

Merci d'avance .

Imod

[Ben314]

Je n'ai pas trop compris l'argument qui interdit le polygone à 42 côtés sur un quadrillage 41X41 . Le même argument explique-t-il l'absence de polygone à 17 côtés sur un quadrillage à 11X11 points ?

Merci d'avance .

Imod

Oui : en fait la première colonne du tableau ne considère "que" le problème de "distance de manhattan" minimale dont on a besoin pour faire un 1/4 de polygone ayant k cotés.
Donc pour un carré de 10x10, le périmètre est de 40 et le meilleur "découpage" en quatre 1/4 de polygones est 40=13+9+9+9 qui est sensé produire un polygone à 5+4+4+4 cotés.
Sauf que si on regarde les longueur dont on a besoin pour faire un 1/4 de polygone ayant 4 cotés (à savoir 4 cases à l'horizontale et 5 à la verticale ou le contraire) et celle dont on a besoin pour faire un 1/4 de polygone ayant 5 coté ( 5&8 ou bien 7&6), bien que la somme de toutes les valeurs fasse 40, il n'y a pas moyen de les regrouper en quatre groupes de 2 de façon à ce que la somme de chaque groupe soit 10 (= coté du carré)