J'oubliais , un immense merci au ch'Ef de nous avoir rendu Latex

Vasimolo

Je ne vois pas trop ce qu'est ton "X" . Il est clair que pour toute valeur de X même très petite on peut trouver un exemple où le recouvrement d'aire 1+X n'est pas possible , mais ça ne contredit en rien ce que je dis

Vasimolo

Bon d'accord je vois ce que tu veux dire

Tu fixes [latex]X[/latex] puis tu augmentes [latex]n[/latex] alors que je fixais [latex]n[/latex] avant de diminuer [latex]X[/latex] ( ce qui semble plus naturel pour le problème ) .

Sinon , comme tu le dis , les deux affirmations sont vraies .

Vasimolo

Indépendamment de la démonstration complète, on peut s'amuser à chercher la surface maximale perdue avec 2 pts, 3pts...
Pour 1 point (celui en bas à gauche) la surface perdue=0
Pour 2 pts, la surface perdue max est =1/4
Pour 3 pts ?
Je n'ai pas encore tenté pour 4 pts.

Si je comprends bien l'hypothèse, si n=3, (2/3)*(1/4)=1/6 de la surface totale ?
Bah...

Là d'accord. Avec les point sur la diagonale.
Pour les points éloignés de la diagonale (placés symétriquement de part et d'autre) j'ai trouvé une perte de 8/27, donc moindre que 1/3.
Je comprends bien la tentation de l'utilisation de la récurrence, mais....

Oui, c'est exactement le problème. La récurrence est malheureusement ici une démonstration insuffisante: Ce n'est parce qu'on a optimisé avec n points qu'il faut partir de cette configuration à n points pour fabriquer la configuration optimale à n+1 points.

Salut.

Ta définition du point "le plus proche du coin en bas à gauche" a l'air bancale.
Précise-la un peu plus.

Ensuite, il faut prouver que tu peux couvrir la moitié de la zone égale au rectangle de départ privé de ce nouveau rectangle, et là tu ne donnes pas beaucoup d'explications.

Prenons un carré 8x8, avec les points (2,2), (4,1), (1,4), et d'autres points plus en haut et à droite de ces 3 là.

Tu vois que ton raisonnement ne s'applique pas :

La carré fait 64 de surface donc il faut en couvrir 32.
Tu prends le rectangle en haut et à droite de (2,2) pour appliquer ton HR : tu obtiens 18. De même, tu appliques l'HR avec les deux rectangles en haut et à droite de (4,1) et (1,4) : tu obtiens 4. Total : 22, et du coup il manque 10 à trouver avec un rectangle de coin (0,0) : impossible, on fait 8 au max.

ok, le problème est très sympa...

Je cherche aussi à l'aide d'un quadrillage, mais sans qu'il soit pour autant régulier.

Je suis sur une approche différente, je vous la livre pour idée...

Je commence avec un seul point, en bas à gauche, et donc mon carré est entièrement plein.

Ensuite je place un point dans le carré, qui, au lieu d'ajouter un rectangle comme dans l'énoncé, me fait enlever un rectangle, soit en haut à gauche, soit en bas à droite, et j'avance ainsi pas à pas en ajoutant des points un à un.

Si j'ajoute un point dans une zone vide, il me rajoute un rectangle. S'il est dans une zone remplie, il m'enlève un peu d'aire.

Une idée parmi les vôtres...

Pour avoir le maximum de vide, j'ai l'impression que toutes les coordonnées X de chaque point ainsi que toutes les coordonnées Y doivent être différentes.
Tout point supplémentaire permettrait de mieux pavé le carré.
En fait, ce point supplémentaire ne peut générer plus de vide que s'il n'était pas là.

Au final, cela nous ramenerait à mettre tous les points sur la diagonale !

Pour illustrer mon propos ci dessus.

Prenons un carré 10 * 10
A(0;0)
B(1;1) par exemple
tout point en (0;X) ou en (X;0) soit bridera le rectangle A mais permettra de faire le complement (et potentiellement faire mieux) soit ne le bridera mais permettra de pavé une autre zone.

Quelque soit l'emplacement de B, le point C ne doit pas avoir une coordonnée commune avec A.
Je pense que cette règle est vraie pour tous les points, donc le cas le plus défavorable reste de mettre tous les points sur la diagonale.
Comme le nombre de point est défini, je pourrais toujours pavé plus de la moitié du carré !