godisdead, d'une part je ne suis pas d'accord pour dire qu'un point ayant une coordonnée commune avec un autre ne peut qu'augmenter la surface que l'on peut couvrir :

Par exemple, sur un carré 8x8 : Avec les points (1,2) et (6,2), on peut couvrir 58 cases, mais si l'on rajoute (6,1), on n'en couvre plus que 56.

D'autre part, cela n'implique en rien que les points doivent se trouver sur la diagonale pour une surface minimale.

Si l'on part d'un carré 8x8 avec les points (1;2), (2;4), (6;1) et (7;2), on peut couvrir 54 cases. Si l'on rajoute (6;3), on ne peut plus en couvrir que 53.

J'ai tenté pas mal d'idées sur ce problème mais aucune n'aboutit.

La seule encore prometteuse de manière simple serait de se dire que l'ensemble des points SUR ou A GAUCHE de la diagonale permet potentiellement de voir plus de la moitié de la zone. (En regardant à droite)

Idem pour les point A DROITE (en regardant vers le haut )

Si on superpose les deux visions, on voit potentiellement plus que le carré complet.

Bon bah moi je vais opter pour un petit raisonnement par recurrence, bon mon hypothèse [latex]\mathcal{H}(n)[/latex] Il existe une construction de n rectangles tel que la somme de leurs aire fasse 1.
Je crois que tout le monde est convaincu de [latex]\mathcal{H}(1)[/latex] ou le rectangle en question est en fait le carré tout entier.
Bon on suppose [latex]\mathcal{H}(n)[/latex], je rajoute cette fois un [latex]n+1[/latex]ème point.
Deux possibilités, soit il est inclus dans un rectangle déjà existant soit pas.
S'il n'est pas inclus c'est trivial (on en a un nombre fini donc il lui reste une place fini à notre nouveau petit rectangle).
S'il est inclus, on se place dans le référentiel tu nouveau rectangle de dimensions [latex]X,Y[/latex].
si on appelle [latex]x,y[/latex] les coordonnées relatives du point, on voit bien qu'on a 2 choix possibles de configuration pour le rectangle en bas à gauche et une possible pour l'autre. On prend [latex]\max(Xy,xY)[/latex] (plus grosse aire)
De cette façon l'aire totale est [latex](X-x)(Y-y)+\max(Xy,xY)=XY-\min((X-x)y,x(Y-y))[/latex].
ce qui vaut dans le pire des cas (pour [latex]x=\frac{X}{2}[/latex] et [latex]y=\frac{Y}{2}[/latex]) [latex]\frac{3}{4}XY[/latex].

On perd donc ainsi dans le pire des cas à chaque itération les 3/4 de notre plus gros rectangle.

On obtient ainsi un graphe binaire qui représente la construction de nos rectangles, chaque nouveau noeud divisant l'aire au pire de 3/4.
On obtient ensuite que l'aire totale est minorée par la somme des produits des diminutions faites à chaque noeuds. Le nombre total de diminutions étant le nombre d'itérations soit [latex]n-1[/latex].

EDIT, bon malheureusement je me suis un peu perdu...
Je crois pas pouvoir prouver que cette méthode marche, même si elle me semble convenir, parce que c'est pas aprce que l'on choisit le pire cas à chaque itération qu'on récupère e pire cas pour n rectangles...

Juste un petit coucou pour dire que le problème est ouvert depuis 40 ans , alors n'y passez pas toutes vos nuits

Je peux donner des références pour ceux que ça intéresse .

Merci à ceux qui ont essayé

Vasimolo

Bonne lecture ( c'est un peu aride ) .