Au moins la moitié
Bonsoir à tous 
Un petit problème très facile à comprendre mais je ne vois pas trop comment l'aborder .
Des points sont placés au hasard dans un carré , l'un d'eux étant le coin inférieur gauche du carré . Il faut alors construire des rectangles disjoints dont les côtés sont parallèles à ceux du carré , dont le sommet inférieur gauche est un des points donnés et dont l'aire totale est au moins égale à la moitié du carré .
Peut-être faut-il imposer que seulement les intérieurs soient disjoints ?
Merci d'avance pour la participation .
Domi
PS : la construction n'est pas demandée , seulement l'existence .
Un petit problème très facile à comprendre mais je ne vois pas trop comment l'aborder .
Des points sont placés au hasard dans un carré , l'un d'eux étant le coin inférieur gauche du carré . Il faut alors construire des rectangles disjoints dont les côtés sont parallèles à ceux du carré , dont le sommet inférieur gauche est un des points donnés et dont l'aire totale est au moins égale à la moitié du carré .
Peut-être faut-il imposer que seulement les intérieurs soient disjoints ?
Merci d'avance pour la participation .
Domi
PS : la construction n'est pas demandée , seulement l'existence .
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je propose une approche par récurrence du problème, :
Admettons que ta figure est une solution pour $n$ points, ajoutons un point $P_{n+1}$
si ce dernier point est placé dans du blanc, pas de problème, tu fais un (petit) rectangle jusqu'à toucher du jaune et tu gagnes de la place.
Mais si le dernier point est placé dans du jaune, ça va perdre de la place :
Zut ! Mon idée de récurrence est-elle à mettre à la poubelle ?
Que non !
Je pense que l'on saura montrer que pour toute famille $P_1; P_2; \ldots ;P_n$ telle que $P_1$ est le coin en bas à gauche, on saura prouver qu'il est possible de construire une famille de rectangles satisfaisant à tes conditions et telle que la somme de leurs aires soit ...
supérieure à $\dfrac 1 2 + \dfrac 1 {2^n}$
On pourra alors essayer de faire une récurrence avec cette proposition.
@ suivre.
Amicalement. jacquot
En disposant les points régulièrement sur la première diagonale ( ce qui semble la condition limite ) j'arrive plutôt à une aire égale à $\dfrac{n+1}{2n}$ .
Mais je n'ai pas l'ombre d'une preuve pour cette limite .
Bonne soirée .
Domi
Bon , je crois que tu voulais dire $\frac12+\frac1{2n}$ , on est donc sur la même longueur d'onde .
On considère un rectangle de côtés $x$ et $y$ avec $n$ points à l'intérieur et on montre que l'on peut recouvrir plus de $\frac{xy}2$ avec les rectangles jaunes . Si $n=1$ c'est évident , sinon on fait glisser l'angle inférieur gauche vers le haut et la droite jusqu'à ce qu'on atteigne un nouveau point . On obtient alors un nouveau rectangle de dimensions $x'$ et $y'$ avec un point dans l'angle et un de moins à l'intérieur , on peut donc en recouvrir plus de la moitié avec des rectangles jaunes . En ajoutant à ce recouvrement le plus grand des deux rectangles bordant ce nouveau rectangle et de sommet le point d'angle initial on obtient plus de $\frac{x'y'}2+\frac{xy-x'y'}{2}=\frac{xy}2$ du rectangle initial qui est recouvert et c'est fini .
On peut même supposer que les rectangles sont disjoints car l'inégalité et stricte .
Domi
En fait, je ne comprends pas ta récurrence.
Bon, ok, ce qui est vrai dans un carré l'est dans un rectangle (une affinité ne modifie pas les rapports d'(aires)
Mais, sur ta figure,
si tu notes $P_0$ ou $P_1$ le point en bas à gauche, quel sera le point suivant en bas à gauche, vers lequel tu fais glisser?
Pourrais-tu, STP, Numéroter les points?
:S . jacquot
Noël + mort de disque dur = beaucoup de retard (td)
J'ai en effet répondu bien trop vite , le problème reste ouvert .
Merci pour ton attention et joyeuses fêtes
Domi
Mes condoléances pour ton disque dur.
La seule chose qui me rassure dans ton message, c'est de savoir que nous sommes (au moins) deux à sécher sur cette question.:-(
Amicalement. jacquot
Je crois que ce problème mérite un petit up pour 2013.
En tous cas, j'y ai beaucoup pensé ces derniers jours, et je sèche toujours.
Voici l'état de mes réflexions ou tentatives infructueuses:
i) L'inégalité à démontrer sera stricte, car quelle que soit une solution, on pourra toujours ajouter un point dans du jaune, de sorte que l'aire jaune diminue.
Je pensais que, pour toute famille $P_0, P_1, ..., Pn$ de points, l'aire jaune est au moins égale à $\dfrac 1 2 + \dfrac 1 {2^n}$
Mais la minoration proposée par Domi me semble meilleure: $Jaune >\dfrac 1 2 + \dfrac 1 {2(n+1)}$
Cette valeur correspond à l'aire jaune pour des points équirépartis sur la diagonale issue de $P_0$
ii) On pourra faire la recherche dans la grille définie par les points $(P_k)_{k\leq n}$.
Comme l'inégalité est stricte on pourra admettre que tous les points ont des coordonnées rationnelles, quitte à les déplacer d'un infime chouia. Dès lors , on pourra travailler , si ça peut aider, dans des quadrillages.
iii) Si tous les points sont d'un même côté de la diagonale du carré issue de $P_0$, on arrivera à montrer l'iégalité soit "en construisant tous les rectangles par la gauche", soit "en construisant tous les rectangles par le bas"
Mais cette méthode ne marche pas forcément si on a des points de part et d'autre de cette diagonale: sur l'exemple qui suit, c'est la troisième figure qui donne J>1/2:
iv) Ayant séché beaucoup sur ce problème, je me suis demandé si la propriété proposée par Domi était bien vraie et si on ne pouvait pas l'infirmer par un contre-exemple:
Sur la figure suivante, on ne peut pas construire de rectangle jaune à partir de $P_0$ dont l'aire soit supérieure à lla moitié de l'aire blanche:
Je me suis alors dit que, puisqu'une affinité ne modifie pas les rapports d'aires, je pourrais fabriquer une fractale en disposant des points de la même façon dans chacun des rectangles jaunes restants, et ainsi de suite...
Mais ça ne suffit pas pour infirmer l'inégalité de Domi, car personne ne nous empêche de construire des rectangles qui seraient à cheval sur les deux rectangles pré-cités...
C'eût été joli, mais je pense sincèrement que l'inégalité de Domi est vraie, quand même!
Si vous découvrez le problème, ne vous laissez pas trop influencer par la direction de mes recherches, si vopus y avez déjà réfléchi, faites nous juste un petit coucou, Domi et moi nous sentirons un peu moins seuls face à ce problème ouvert.
@ bientôt. jacquot
En fait je n'y ai pas réfléchi depuis ma dernière réponse car je travaille sur d'autres problèmes dont je vous ferai part bientôt . L'idée du quadrillage me semble très pertinente , il reste à trouver un moyen de bien l'exploiter .
Bonne année à toi et à tout le forum
Domi
Ma réflexion achoppe actuellement sur la figure suivante, déjà présentée plus haut, que je considère comme une situation critique:
Les points $P_0$ ; $P_1$ et $P_2$ étant ainsi placés, le plus grand rectangle que je puisse construire à partir de $P_0$ est le carré rose. Son aire (0,2025) est inférieure à la somme des aires des deux rectangles blancs (0,22). Il faut donc pouvoir recouvrir nettement plus que la moitié de la partie restante!
Dans les rectangles jaunes, nous savons que si l'on dispose une foultitude de points le long de la diagonale, on pourra recouvrir, dans chacun d'eux juste un chouia de plus que la moitié de la surface par des rectangles...
On comprend donc que nécessairement, il faudra tracer des rectangles ( ici en brun) qui empiètent sur la partie beige, dont il faut recouvrir bien plus que la moitié pour pouvoir rattraper le déficit causé par le tracé du premier rectangle rose.
Comment montrer que ce rattrapage pourra être suffisant quelle que soit la disposition d'une flopée de points dans la partie beige? That's the problem ! ::o
J'aurais aimé en arriver à un beau raisonnement synthétique, mais j'ai bien peur qu'à défaut de le trouver, le traitement de cette situation ne devienne horriblement calculatoire..:S
Je pense que la situation est la plus critique pour $P_1:(\dfrac 1 5 ;\dfrac{\sqrt 5} 5) $ et $P_2:(\dfrac{\sqrt 5} 5 ; \dfrac 1 5 )$.
Mais, même si on arrive à traiter ce cas par le calcul, il faudra encore montrer que toutes les autres répartitions ont aussi une solution.
Dans ce message , j' utilisé un vocabulaire descriptif avec l'espoir que ma détresse soit bien intelligible!
A présent, dans ce désert de réponses, je me demande si ce problème est bein rangé dans la rubrique Géométrie, puisqu'apparemment, il s'agit plutôt d'un problème de Mesure.:D
Amicalement. jacquot
Le problème n'est sûrement pas géométrique dans le sens où on l'entend habituellement ici , mais a-t-il plus sa place ailleurs ? Il y a peu de participation car personne n'a trouvé une idée originale . Quand on est un peu paumé , on n'a pas forcément envie de dire que c'est intéressant mais qu'on ne trouve rien
Je vais essayer de m'y remettre ce soir après avoir décortiqué ton message .
Amicalement ,
Domi
j'ai laissé reposer le problème ( j'aime bien prendre mon temps ) . Il me semble bien que la solution soit dans le quadrillage . En décalant légèrement les points on peut supposer qu'aucun d'entre eux n'a la même abscisse ni la même ordonnée tout en conservant des coordonnées rationnelles . On peut alors former une grille régulière avec au plus un point par ligne et par colonne . Rajouter des points ne peut que diminuer la surface recouverte par les rectangles , on peut donc supposer qu'il y a exactement un point par ligne et par colonne et choisir de ne construire que des rectangles de largeur 1 ( un carreau du quadrillage ) . Si les points sont disposés sur la première diagonale la solution est évidente avec deux choix pour chacun des rectangles .
Il me semble ( mais je n'ai pas de stratégie pour le vérifier ) qu'en partant du sommet supérieur droit , en descendant sur la diagonale du carré et en récupérant au passage les points perpendiculairement à cette diagonale avec un rectangle de largeur 1 on arrive à dépasser la moitié du carré .
Rien n'est vraiment finalisé mais il faut bien proposer quelque chose
Domi
Je ne comprends pas tout, il me semble qu'il y a des affirmations contestables (l'ajout dun point à une distribution ne diminue pas forcément la plus grande aire réalisble)
L'idée de la descente le long de la diagonale en partant d'en haut à G est intéressante. Faut-il récupérer les points perpendiculairement à cette diagonale ou parallèlement aux côtés du carré? A préciser...
En fait , nous aimerions montrer que pour n points, la disposition donnant la plus petite aire maximale possible est l'équirépartition sur cette diagonale.
Je vais me coucher.B-)
Je pense que nous saurons avancer à deux.... mais tout renfort est bienvenu.
J'espère que tu n'as pas passé trop de temps à décrypter mes délires ( Il faut que j'aille jusqu'au bout de mes âneries avant de commencer à décoller X:-( ) .
Une nouvelle idée :
La formule $F\geq \frac 12 +\frac 1{2n}$ semble vraie pour tout rectangle ( $F$ est la fraction de la figure qui peut être recouverte par les petits rectangles pour $n$ points ) . On devrait pouvoir démarrer une récurrence en enlevant une bande en haut ou à droite ( c'est encore une idée en l'air ) , attaquer le problème par le coin supérieur droit , c'est tout ce qu'on peut , à la rigueur , retenir de mon message nocturne .
Merci Jacquot pour ton soutien
Domi
Pour ceux qui n'auraient pas vu ou oublié
Domi
Toute aide sera bienvenue ! (voir énoncé initial)
J'ai réfléchi à un raisonnement (de récurrence ) descsendant le long de la 1ère diagonale, mais je rencontre les mêmes difficultés que pour les tentatives de récurrence montant le long de cette même diagonale.
Je partage avec toi l'intuition que $F\geq \frac 12 +\frac 1{2n}$
Ce minimum correspond à n points équirépartis sur la 1ère diagonale qui devient, en quelque sorte "infranchissable"
Je retiens aussi notre idée démonstration par récurrence partant du coin inférieur gauche.
Malheureusement, le passage du rang n au rang suivant n+1 n'est facile à établir que lorsque le Point Px1 différent de Po et d'abscisse minimal et le point Py1.............. d'ordonnée minimale sont un seul et même point.
Si ce n'est pas le cas, je ne sais pas établir ce passage actuellement, (voir ma "figure critique"), mais je ne désespère pas !
Je réfléchis actuellemnt à la question suivante;
Que vaut $F$ pour une réunion de deux rectangles d'intersection non vide telle que celle-ci?
Discuter éventuellement selon leurs dimensions respectives...
Bien sûr, une récurrence avec disjonction de cas et peut-être récurrence dans la récurrence, ce n'est guère aguichant...
Je rêve toujours d'un argument-massue qui nous premettrait d'assommer le problème.
Amicalement. jacquot
@ suivre
J'étais un peu sur une autre idée même si elle n'est pas très loin de la tienne . Le problème est clairement discret donc on peut placer définitivement les points aux noeuds d'un quadrillage . On pourrait essayer de démarrer une récurrence sur la taille du carré ( ou du rectangle ) ou l'on place les points , le nombre de points serait une variable secondaire . La grosse difficulté est de réduire la figure à une figure plus petite ayant les mêmes propriétés pour faire fonctionner la récurrence .
Une petite question annexe que je me pose ( elle est peut-être sans intérêt ) , dans un rectangle $m\times n$ quel est le nombre minimal de cases que l'on peut couvrir quel que soit le nombre de points choisis dans ce rectangle ( les points toujours sur les noeuds ) .
Merci pour ta ténacité (tu)
Amicalement
Domi
Cher Domi,
Bien que nos recherches ne partent pas exactement dans le même sens, elles peuvent être complémentaires.
Pour résumer, je crois que nous cherchons à prouver que la distribution pour l'aire jaune est minimale est l'équirépartition des points rouges sur la 1ère diagonale.
Expérimentalement, on peut le constater pour des carrés 2x2, 3x3, 4x4, etc.
On voudrait pouvoir généraliser. Récurrence?
Ensuite, faudrait soigneusement expliquer pourquoi un traitement discret est suffisant.
Je ne sais pas exactement pourquoi tu te poses la question des rectangles m x n.
Il me semble que là aussi, l'aire est minimale quand les points rouges sont disposés sur les noeuds du quadrillage, au plus près de la 1ère diagonale.
Par ailleurs, un rectangle n'est toujours qu'un carré étiré, mais la diagonale ne coupe plus les noeuds du quadrillage si m et n sont premiers entre eux...
Bref, rien de bien construit dans mon bla-bla-bla du jour, mais toujours une lueur d'espoir d'arriver à la démo un de ces quatre matins.
Le WE prochain, je pars prendre l'air en montagne. Mais j'emporterai un crayon et un petit carnet à papier quadrillé.
Domi
S'il n'y a aucun point dans la partie blanche est-on assuré de pouvoir recouvrir les trois quarts du grand rectangle/carré ?
Domi
PS : les points rouges sont disposés aléatoirement dans le rectangle/carré .
Il y a bien sûr plein de points d'interrogations dans tout ça :S
Domi
Edit : j'ai de gros problèmes de latéralisation, j'essaie de remettre les droite et gauche à l'endroit...
je découvre ce fil et vais très probablement dire des bêtises. Mais bon.
D'entrée Domi dit que les points sont tirés au hasard et on voudrait nous faire croire qu'il y en a un qui tombe toujours pile poil sur le coin inférieur gauche! Choquant.
Il demande d'abord que ça fasse au moins la moitié. Soit.
Mais ça ne lui suffit pas, pas plus qu'à Jacquot: ils pensent que c'est carrément plus!
Tu pars de ce fameux point G en-bas à gauche (salut Remarque) et t'as que deux choix (sauf à vouloir perdre!): ou le "rectangle horizontal "ou le "rectangle vertical" de G (on a " quadrillé", on devrait dire "rectangularisé", le carré en traçant horizontale et verticale qui passent par chaque point et à chaque point on associe ses deux rectangles "longiligne et "longicolonne" dont il est le coin sud-ouest).
Ne pas préférer systématiquement le plus gros car il y a une suite.
Et la suite c'est pour demain!
Bien à vous trois
Paul
Paul, faudrait que tu lises bien l'énoncé de ce problème sur lequel nous sèchons.
Mon idée ne marche pas comme le montre ce contre-exemple :
On place des points ( rouges ) à l'intérieur d'un rectangle l'un d'eux en étant le coin inférieur gauche . On suppose en plus que l'on peut relier tous les autres points en escalier comme sur le schéma ci-dessous :
On construit alors un rectangle vert d'aire maximale s'appuyant sur le sommet en bas à gauche et n'intersectant pas l'escalier jaune . Pour les aires , est-on assuré que 2.Vert+Jaune>Rectangle .
J'en doute de plus en plus mais je n'ai pas de preuve .
Domi
Domi
Domi
Il faut montrer que x1y1+x2(y2-y1)+x3(y3-y2)+...+L(l-y_k)-U(L-V)<Ll/2.
Domi
Domi
On aurait alors U(L-V)=min(U,L-V).max(U,L-V) et Ll=min(L,l).max(L,l).
soit U(L-V)>Ll/4.
La somme des aires des rectangles vert et jaune est minimale quand le coin supérieur droit du rectangle vert est au milieu du grand rectangle, auquel cas elle vaut la moitié de l'aire du grand rectangle. Donc les surfaces colorées initiales recouvrent plus de la moitié du grand rectangle. Non ?
On part du bord gauche et du bord inférieur du rectangle que l'on fait glisser respectivement vers la droite et vers le haut . Il y a alors deux cas de figures
1°) Les deux droites bloquent sur un point du réseau : on a un escalier à une seule marche .
Domi
Je suis au ski. J'ai emporté du papier quadrillé avec l'espoir de résoudre le problème par récurrence sur des carrés n x n.
Il me semble que, dans de tels carrés, l'aire est la pmus réduite si les points sont équirépartis sur la 1e diagonale.
Peut-on l'établir par récurrence? Une difficultése présente pour le prolongement des rectangles qui tou vent les bords.
Pour le passage au continu, nous saurions argumenter, nest-ce pas, Domi?
Domi