Au moins la moitié
Réponses
-
Jacquot , on croirait du christophe ( le notre , pas le chanteur ) , ces engins sont vraiment des instruments de torture :S
Amuse-toi bien
Domi -
Bonsoir à tous,
je n'abuserai pas du "pardon, j'ai mal lu l'énoncé" vu que je l'ai bien lu! Donc pas de fausse excuse!
mais si "bien lire un énoncé" garantissait qu'on ne dira pas d'affirmation gratuite par la suite, ça se saurait!
J'ai gratuitement assuré qu'on n'avait que deux choix (la longiligne ou la longicolonne): Mon idée, plus que doûteuse (euphémisme) , était qu'il
ne fallait pas se faire appâter par le plus gros rectangle qu'on pouvait trouver depuis P0 car alors on se cassait la possibilité de récurér.
Pire, je pensais que ce n'était pas forcément judicieux de choisir le plus gros parmi le longiligne et le longicolonne: carrément idiot!
Après avoir éliminé la première colonne et la dernière ligne, on se retrouve avec un rectangle qui
a un Pi sur le côté ouest et un Pj sur le cöté sud.
Si i=j, on récure à l'aise; sinon ....
Question: si s est une permutation de 0, n-1 telle que s(0)=0, et si les Pi ont pour coordonnées (i, s(i)), savez-vous déjà que "ça marche" dans le carré de coté n? Pardon si ma question admet une réponse sûrement positive mais triviale!
Bonne nuit.
Paul -
Je m'étais posé la question il y a un moment et la réponse est en effet évidente . Il suffit de prendre par exemple tous les rectangles horizontaux ou verticaux d'un carreau de large pour dépasser la moitié .
Domi -
De retour, je vous livre quelques réflexions:
je me réjouis du renfort de depasse, remarque et Sylvain qui ne sont pas des purs géomètres, mais ils sauront peut-être envisager d'autres façons de considérer le problème.
remarque a évoqué des intégrales de fonctions en escaliers....
Le "canular" de Domi en jaune et vert rejoint ce que j'avais appelé "figure critique"
plus de 52%
ce qui nous renvoie vers mes rectangles d'intersection non vide (voir figure dans ce message)
Mes essais de récurrence dans des quadrillages sont au point mort parce que je ne maîtrise pas ce qui se passe à droite et en haut...
What else? -
Bonjour
La propriété en question est fausse,il y'a un contre-exemple. -
@ jacquot : l'histoire des intégrales ne concernait que le cas des points formant un escalier. Ce cas a été réglé élégamment par l'idée de Sylvain, mais ne permet pas d'aller plus loin... :-(
@ AitJoseph : alors ! Ce contre-exemple ? Le suspense est insoutenable ! -
bonjour,
êtes vous gênés par le flou du protocole "placer un nombre fini de points au hasard dans un carré" ? -
AitJoseph,
J'ai cru tenir un contre-exemple fractal durant quelques heures...
Si t'en as un, montre-z-y voir!
Bienvevue au club en tous cas, AitJoseph, capesard, ... plus on est de fous,... -
Nul en Latex et en dessin, patience SVP,si je me trompe,pardonnez.
Salutations :S -
Bonsoir
@Jacquot : mon "canular" n'était pas volontaire , comme chaque perte d'aire générait un nouveau point rouge , j'ai tenté une autre approche . Je ne pense pas qu'il faut rester crispé sur ta figure "critique" ( sauf si on veut exhiber un contre-exemple ) . Ce qui est assez affolant c'est que le choix des rectangles dépend de la zone à laquelle appartient le point mais aussi des distances entre les différents points : bref à moins d'un contre-exemple , on est très loin du terminus
@AitJoseph : on va patienter
J'ai encore d'autres idées mais je vais arrêter de balancer tout ce qui me passe par la tête , ça sera mieux pour tout le monde .
Domi -
Bonsoir,
Je me mêle de ce qui ne me regarde absolument pas (ça doit être la première fois que j'interviens sur un fil de géométrie), mais tous ces jolis dessins me font beaucoup penser au concept de front de Pareto rencontré en optimisation. Je me demande s'il n'y a pas de connexion avec des calculs de recouvrement déjà faits quelque part. Si j'ai un peu de temps, je regarderai, c'est rigolo !
Merci Domi pour ce problème.
Amicalement, -
Pas de problème Kuja , mon niveau en géométrie s'arrête au collège ( d'aujourd'hui ) mais j'adore . Ici il n'y a pas de conique de projectif ou point de machin , bref un problème ouvert à tous comme je les aime . Bizarrement les experts boudent le sujet ( sûrement trop simple ) .
Bienvenu parmi nous
Domi -
Bonsoir
On peut exiger que le nombre de rectangles n formant la partition est dans N-{0,1},car dans le cas d'un rectangle, il y'a un point qui est forcément le coin gauche en bas,une solution triviale existe qui est le carré entier.
Définition: Soit M un point d'une configuration supposée vérifiant la propriété,on dira que M est atteint s'il existe un rectangle de la partition dont le point à gauche en bas coïncide avec M.
Soit a le côté du carré (voir dessin)qui contient deux rectangles:BCHG et GHED,avec BC=GH=ED=b et GE=HD=c
Contre-exemple: Soit un ensemble non vide de points tous contenus dans le rectangle ouvert coloré, en plus du point F.On suppose :b et c inférieures strictement à a/4.
Supposons la propriété vérifiée
1) cas F n'est pas atteint
Il existe une partition de rectangles contenus dans le rectangle BCED,la surface de la réunion additive est inférieure à celle du rectangle en question qui vaut ab inférieur strictement à a2/4 .Impossible
2) cas F est atteint
F est le sommet à gauche en bas d'un rectangle de la partition,la longueur de ce rectangle est inférieure à a,sa largueur est inférieure strictement à c (sinon il y'a chevauchement) et par conséquent sa surface est inférieure strictement à a2/4.La surface totale de partition serait inférieure strictement à a2/2.Impossible
Sauf erreur ou omission:)
NB/ Résolution idiote -
Las, je ne comprends rien!
C'est trop compliqué pour moi d'imaginer des fractales planquées derrière ton contre-exemple que même sans les fractales je capte pas. -
Des remarques ?
-
Voyons, AitJoseph,
Le point F est bien rouge
Si tu ne balances les autres points que dans GHDE,
Tu peux déjà peindre en jaune tout le rectangle ABEF qui a déjà , à lui seul, une aire supérieure à a²/2
Après, tes points rouges sont tous distincts, donc tu peux construire une famille de petits carrés disjoints sur chacun de ces points pour compléter la famille de rectangles
Je crois que nous n'avons pas compris l'énoncé de la même façon.:S -
OK,pardon.
-
Bonsoir
A chaque fois que je lis l'énoncé,je comprend une chose différente.
Cordialement -
Je ne vous oublie mais je reste sec; plus précisément, j'atteins des moments de bonheur : eureka! toujours suivis d'une déprime: putain!, j'ai pas vu ce cas là!
Je ne vous apprends rien sur notre jouissance à tous! -
Bonjour,
je profite de la gentillesse de Domi (qui ne m'a pas répondu "c'est trivial!" alors que je posais une question très neuneu) et je risque donc d'en poser d'aussi sottes!
Je continue à ne m'inquiéter que du cas où j'ai un carré de n x n et une permutation s de 0 , n-1 telle que Pi a pour coordonnées (i , s(i)) avec s(0)= 0.
Domi (m') a prouvé qu'on peut trouver deux coloriages "en jaune" , et ce quelque soit s , où n ( n + 1) / 2 "cases carrées" sont coloriées et donc démontré la conjecture dans le cas où les cases sont carrées. Ca marche aussi dès qu'elles sont des rectangles identiques.
1) Peut-on faire mieux que n(n+1)/2 ?
2) Peut-on faire pire que n(n-1)/2 ? ( bien sûr : on peut ne rien colorier du tout! ) Ah! donc je dois préciser que je n'envisage que les coloriages maximaux.
3) Dans un coloriage (maximal), la case en haut, à droite est-elle toujours coloriée?
Au moins, je participe!
Cordialement
Paul -
Bonjour Paul (depasse) & bonjour la compagnie.
Je ne saurais qu'encourager tes recherches dans les quadrillages n x n ,
>>>>>>>>>>>>>>>>>1) Peut-on faire mieux que n(n+1)/2 ?
Je ne comprends pas bien ce "mieux"
Mon sentiment est que
En d'autres termes, que toute autre répartition permettra de colorier une surface jaune (strictement) supérieure à n(n+1)/2Proposition a écrit:Pour toute répartition de points à coordonnées entières dans [0; n[ x [0; n[ contenant (0;0), on arrivera au moins à colorer n(n+1)/2
et ce coloriage (minimal) est obtenu seulement quand les points (rouges) sont placés sur la diagonale [(0;0) (n;n)[
J'en ai l'intime conviction, mais ne suis pas (encore) arrivé à le démontrer.
Q'uen est-il si deux points ont même abscisse ou même ordonnée?
Je ne comprends pas ta question 2)
>>>>>>>>>>>>>>>3) Oui je pense , pour tout coloriage maximal, la case ne haut à droite sera jaune. (pas le temps de le démontrer ce matin
)
Je t'encourage à faire des dessins dans des 4x4; 5x5 ; etc.
Avons nous perdu AitJoseph ? (quels sont tes interrogations par rapport à l'énoncé ?)
Il me semble que tu sois toujours des nôtres
Le renfort de Kuja est aussi bienvenu: j'ai fait remarquer assez tôt à Domi, que ce problème de mesure intéressera plus les analystes que nos éminents géomètres.
Amicalement. jacquot -
Bonjour à tous
Il y a un moment que je ne suis pas intervenu ( je n'avais pas grand chose à dire ) mais comme ça commence à bouger un peu ...
D'abord , où j'en suis .
J'ai repris mon escalier sur quadrillage régulier
Le rectangle vert n'occupe pas forcément la moitié de la partie inférieure-gauche mais ce n'est pas grave si on n'arrive à recupérer suffisament de surface dans les rectangles jaunes ( je suppose toujours , qu'hormis le coin inférieur-gauche il n'y a pas de point rouge à l'extérieur des rectangles jaunes ) . Bref il faut trouver une bonne minoration de la surface pouvant être recouverte dans un rectangle $n\times m$ quel que soit le nombre de points rouges qu'il contient . J'ai commencé avec des rectangles de largeur 1 , 2 , 3 , 4 ... , rien ne m'a sauté aux yeux , mais j'y crois toujours . Bien sûr , il n'est pas interdit d'essayer autre chose .
@Jacquot : pratiquement tous les sujets qui me passionnent sont à la frontière des différentes disciplines qui font les mathématiques et je sais que je ne suis pas le seul , même le grand Pappus indécrotable géomètre "avoue" apprécier particulièrement les problèmes qui vont picorer dans les autres branches des mathématiques . J'ai pris mes habitudes sur ce forum et je ne me sentirais pas chez moi parmi les analystes
Bonne recherche à tous .
Domi -
Bonsoir
Rien ne laisse croire que les rectangles touchent tous les points comme extrêmité gauche en bas .
@Jacquot: La récurrence ne donne rien ?
Cordialement -
Le problème complet me semblant définitivement trop compliqué , j'ai commencé à lister les cas les plus défavorables pour un rectangle avec $n \times m$ avec $n\geq m$ entiers , sauf erreur :
$n\times 1$ : $I(n,1)=n$
$n\times 2$ : $I(n,2)=\lceil \frac{3n}{2}\rceil$
$n\times 3$ : $I(n,3)=\lceil \frac{3n+6}{2}\rceil$ si $n>3$ et $I(3,3)=6$ .
...
Le carré semble le cas le plus défavorable ( ce qui est assez intuitif ) . Le cas $m=4$ devient compliqué car on commence à voir se dessiner l'escalier à marches variables .
Peut-on tirer quelque chose de simple de tout ce fatras ?
Domi -
Bonsoir Domi & compagnie
Les carrés nous intéressent, mais pourquoi les rectangles?
Je voudrais soumettre la figure suivante à votre réflexion:
$P_0 ; P_1; P_2$ étant placés, quel que soit le rectangle construit sur $P_0$,
on pourra colorer 9 carreaux au maximum, tandis que 12 resteront blancs.
Si tu scindes la surface bleue restante en 2 rectangles, tu n'arriveras pas à prouver que quelle que soit une distribution de points rouges dans cette surface, on pourra en colorer au moins la moitié.
Il faut considérer cette surface bleue comme une entité avec ses deux points rouges à la base.
Mon, score minimum est 45, soit largement plus que la moitié de la surface bleue (60)Exercice a écrit:Disposer dans cette surface bleue une giclée de points rouges ( sur les intersections du quadrillage) de sorte que la surface que l'on pourra jaunir ait une aire minimale.
Le fait d'avoir deux points de base $P_1$ et $P_2$ augmente considérablement la surface jaune potentielle....
Qu'en pensez-vous?
Pour AitJoseph, je précise que j'ai essayé plusieurs démonstrations par récurrence , mais que j'ai rencontré une difficulté pour chacune. :-(
@ bientôt., amicalement. jacquot -
Bonsoir Jacquot
Je suis entrain de contempler la figure.Personne n'a donné suite à ma demande de préçision.
Amicalement -
@AitJoseph : c'est une donnée du problème que l'on prenne des rectangles qui s'appuient en bas à gauche sur un point rouge. Je ne sais pas si c'est la précision que tu attendais.
-
Bonsoir AitJoseph,
Tes questions mettent en évidence que l'énoncé n'est pas clair pour toi.
Je pense que Domi ne m'en voudra pas si je le reformule en apportant quelques précisions.Enoncé repris. a écrit:n+1 points sont placés dans un carré , l'un d'eux, Po, étant le coin inférieur gauche du carré, les autres étant placés au hasard . On peut alors construire n+1 rectangles disjoints dont les côtés sont parallèles à ceux du carré, et tels que le sommet inférieur gauche de chacun d'eux soit l'un des points donnés .
Montrer que quels que soient les points donnés, on peut construire une telle famille de rectangles de sorte que la somme de leurs aires soit supérieure ou égale à la moitié de l'aire du carré
Est-ce plus clair, AitJoseph? -
Jacquot : Je n'ai aucune idée neuve à apporter pour la résolution de ce joli problème, mais je ne suis pas sûr que la précision "au hasard" (déjà présente dans l'énoncé de Domi) apporte grand chose à la compréhension de l'énoncé, ce n'est pas un problème de probabilités. On peut la reformuler en un "pour tous $P_1,...,P_n$ dans l'intérieur du carré" ; d'ailleurs tu le dis toi même : "quels que soient les points donnés, ...".
-
Ait Joseph : il y a autant de rectangles que de points. J'imagine que Domi autorise les rectangles réduits à un point, même si c'est contre-productif.
-
Sérieusement ?
Je suis sur une piste.
Merci -
Bonsoir à tous
Ca me gène toujours un peu d'intervenir pour dire que je n'ai trien trouvé mais que je suis toujours là , mais bon , je suis toujours là et je n'ai rien trouvé . J'ai abandonné mes comptes d'apothicaire ( trop pénibles ) .
Une petite remarque , il semble qu'un ensemble de rectangle maximal pour $n$ points donnés , peut toujours être complété avec $n-1$ rectangles pour recouvrir le carré . On n'a pas l'inégalité sur les aires mais sur le nombres de rectangles .
Je crois qu'on n'est pas au bout du bout .
Amicalement
Domi -
Ah bah et alors ! Moi non plus, je n'ai rien trouvé !
-
Personne ne tient au sérieux ma question,moi,je résiste et je suis sur une piste.
-
Mais de quelle piste parles-tu AitJoseph ?
Domi -
AitJoseph a écrit:Et réciproquement ? Est ce que chaque point est point gauche en bas d'un rectangle ?
Oui, sinon, tu pourrais inclure des points rouges non utilisés dans un rectangle. En fait, il suffirait de mettre le carré entier basé sur son coin inférieur gauche et ça ne serait pas rigolo. -
@AitJoseph
eggoroffski t'a bien répondu sur la question de la réciproque: il y a autant de points (rouges) que de rectangles, alors...
Si tu tiens une piste, creuse-la !
@eggorofski: tu as raison, il vaudrait mieux ne pas invoquer le hasard dans l'énoncé, ce n'est pas un problème de probas.
Je me réjouis de ta participation.
@ tous: j'espère que ce dernier épisode de la mise au point de l'énoncé ne vous a pas fait perdre de vue le petit exercice que je vous ai proposé plus haut...
Comme AitJoseph, je crois que je tiens une piste, mais ça ne fait toujours qu'un mois que j'ai ce sentiment! -
Bonjour
Sérieusement,j'y travaille.Il me faut environ trois jours.Comme je ne maîtrise pas le Latex,je vais la scanner,en cas d'aboutissement.
Je ne suis pas convaincu par la remarque de Remarque.
Cordialement -
Bonjour,
J'ai comme l'impression qu'on ne sait toujours pas d'où vient ce zoli problème à moins qu'il ne soit directement sorti du cerveau créatif et ingénieux de notre ami Domi
Amicalement. -
AitJoseph a écrit:Je ne suis pas convaincu par la remarque de Remarque.
Pourquoi donc ? C'est l'énoncé du problème, c'est tout. Il y a exactement un rectangle par point rouge, éventuellement réduit à ce point. Comme les rectangles ne s'intersectent pas, on ne peut pas faire ce que j'ai dit, qui d'ailleurs enlève tout son sel à l'énigme. -
Voilà où j'ai trouvé le problème :Maths-links
On ne se moque pas de mon anglais.
Je n'avais pas fourni le lien car il n'apporte pas grand chose .
Domi -
Effectivement, ça, on peut facilement le démontrer par récurrence. Peut-être y a-t-il moyen d'exploiter cette remarque :SDomi a écrit:il semble qu'un ensemble de rectangles maximal pour n points donnés , peut toujours être complété avec n-1 rectangles pour recouvrir le carré
Ait-Joseph, l'énoncé en anglais est rédigé un peu différemment. Il pourra peut-êtrenous aider à bien nous comprendre. -
-
J'ai posté trop vite:
Laproposition de Domi n'est pas tout a fait juste.
Il peut y avoir des points sur les bords ou des fractionnements inutiles, mais je crois bien que l'on a "l'inégalité en nombre". -
... Et il ne faut pas se méprendre sur le sens de "maximal"
Bonjour JLT,
Ton intervention est un encouragement.
Sincèrement. jacquot -
Bonjour,
Merci Domi pour le lien, et merci JLT pour avoir déniché ce dur-dur pdf de Dimitrescu et Toth.
Amicalement. -
Chers JLT, bs, Domi and co,
Comme j'ai déjà pu l'exprimer, my english language is very bad, unfortunately.:S
Je ne suis même pas capable de lire si le arxiv donne une solution du problème ou l'état des recherches actuel.
J'ai relevé qu'on a séché durant plus de 40 ans sur ce problème,
Qu'il y est question de fronts de Pareto (bien vu Kuja) et que vers la fin on y joue à deux Alice & Bob.
La fig 7 présente une fractale. S'agit-il d'un contre-exemple?
L'un d'entre-vous voudrait-il (me) faire un petit résumé du document ?
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 58 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres