Bonjour,
Quelque chose doit m'échapper. Si j'ai bien compris on prend des cercles de diamètres inférieur à 1 m. Pourquoi ne pourrait on pas recouvrir avec une infinité de cercle  tout le carré ?

Parce que deux points des cercles ne doivent jamais être distants de 1m .

Imod

>Imod
Pourrais -tu nous faire un petit dessin ?

Si j'ai bien compris, pour chaque cercle de rayon r on a un donut centré sur ce cercle de rayon intérieur 1-r et de rayon extérieur 1+r qui ne peut intercepter aucun cercle.

Les cercles ont donc un rayon maximal de 0.5m.

Bonjour
Doit-on comprendre que 2 pts qcq (éventuellement sur un même cercle) sont à plus ou moins d'un mètre mais jamais à un mètre ?

Si c'est le cas les cercles font moins d'un mètre de diamètre et ils sont "éloignés" de plus d'un mètre les uns des autres.

A la limite, les centres des cercles sont sur les sommets de triangles équilatéraux de côtés 2m.

Cercles de diamètre 1m (à la limite)

croquis

J'avoue ne pas du tout comprendre le problème
Un grand cercle qui occupe le carré au maximum occupe les 3/4 de la surface, ça me semble une solution quelle que soit la manière dont je comprend l'énoncé...

Weierstrass, dans un tel cercle on peut trouver des points distants de 1m (une infinité même).

Ok, j'ai compris maintenant...
La solution de derny donne une densité de
On peut améliorer en ajoutant des plus petits cercles dans les trous de l'empilement hexagonal, mais je ne pense pas qu'on atteigne 35%, je vais chercher autre chose.

Je néglige les effets de bord bien entendu, je verrais ça après...

Je vois que ça cogite alors je n'interviens pas .

En plus Derny m'évite la corvée d'illustration ( merci à lui )

Imod

Alors j'ai fait plein de calculs...
Pour l'empilement hexagonal, le trou est trop petit donc on ne peut pas améliorer.
Pour l'empilement carré, le trou est plus grand, mais toujours trop petit pour pouvoir améliorer. J'ai aussi essayé deux empilement hexagonaux avec deux tailles différentes imbriquées (quitte à ce que deux cercles proches ne se touchent pas) , mais l'optimum est réalisé quand les deux tailles de cercle ont la même taille, donc rien de nouveau. De même, pour l'empilement carré, j'ai essayé un empilement avec deux tailles différentes, et je suis arrivé à la même conclusion que pour l'empilement hexagonal.
Je pense donc que la meilleure solution est celle de Derny, pour une densité de 0,227.
On est à des années-lumières de 35%, reste donc à trouver une preuve que les 35% sont impossibles...

>>derny
Merci pour le dessin ..
Au passage tu devrais essayer mon optimisation de balayage au tennis (c'est le genre
que tu aimes)

>Imod

 Cliquez pour afficher

Les cercles sont ils identiques ?
si on oublie le pluriel,on y arrive  35.3553%  (diamètre 998 m)
Ensuite on peut  prendre deux cercles en diagonale  (diam max 585.029 ) ce qui
donne un  pourcentage de 53.762 %

>Imod

 Cliquez pour afficher

Pour un cercle grosse erreur (78.226 %) (j'avais gardé un résultat d'une autre calcul)
Mais pour deux cercles je confirme sauf incompréhension )

Ça doit être moi parce que je n'ai toujours pas compris les contraintes.

Vous n'êtes pas loin de la solution . Il ne faut pas faire une fixation sur le 35% , j'aurais pu dire 33,4%  soit un peu plus que 1/3 et c'est un indice .

Bonne recherche

Imod

Ca y est, je pense avoir trouvé:

 Cliquez pour afficher

Je pense que l'histoire des cercles n'était qu'une distraction du réel problème...
Prouvons d'abord qu'après coloration des cercles, il n'y a jamais deux points distants d'exactement 1 m:
Tout les points à l'intérieur d'un cercle sont distants de moins de 1m car le rayon des cercles est forcément de moins de 1m. Supposons par l'absurde que 2 points appartenant à deux disques différents soient à une distance de exactement 1m. En traçant deux arcs de cercle approprié, on peut construire 2 points sur les cercles extérieurs distants de 1 m, ce qui est absurde.

Il suffit maintenant qu'on ne peut pas colorer plus d'un tiers du plan sans qu'il y ait deux points distants de 1 m.
Pour montrer 50%, on peut découper le plan en bandes d'épaisseur 1. En groupant les bandes successives deux par deux, on peut partitionner le plan en paire de points distants de 1m perpendiculairement aux bandes, chacun des points de la paire étant dans une bande différente d'un même groupe. Au maximum un seul point sur les deux peut être coloré.

Pour montrer 33.33%, on peut faire la même chose, en utilisant le pavage régulier triangulaire. On peut groupes les triangles 3 par 3, et partionner les points en triplets de points formant un triangle équilatéral. Un seul point du triangle pouvant être coloré, on obtient donc que l'on ne peut pas colorer plus d'un tiers du plan.
Cette borne est atteinte en colorant 1/3 d'un pavage hexagonal, où les hexagones sont de diamètre très légèrement plus petits que 1, ou de diamètre 1 en enlevant 3 bords de chaque hexagone pour ne pas qu'ils se superposent.
Pour améliorer la borne dans ce problème là, il faut donc raisonner à partir des cercles, mais je pense que l'on doit pouvoir montrer que la solution de Derny est optimale en utilisant une démonstration similaire à celle de l'optimalité de l'empilement hexagonal

Planté depuis le début,j'aurais du lire les points des disques ....

A la réflexion, je pense qu'il y a une faille dans ma preuve, du style paradoxe de Banach Tarski:

 Cliquez pour afficher

Si on prend un cercle de rayon 1, encerclé par un anneau d'épaisseur 1, on peut trouver une partition en paire de points telle que chaque paire à un point dans le cercle et un point dans l'anneau. En suivant ma logique, l'aire de l'anneau devrait être la même que celle du cercle, ce qui n'est évidemment pas vrai (elle est trois fois plus grande)

On est vraiment très proche .

Si on arrive à ajouter deux copies disjointes des cercles dans un rectangle légèrement plus grand que le carré initial : on a fini .

Imod

Bon, en fait, dans ce cas là, on peut sauver assez facilement ma preuve:

 Cliquez pour afficher

Dans notre cas, la partie colorée est une union de compacts.  Il suffit de remplacer les paires de points par des appariement de compacts formant une partition. Pour deux compacts, un seul d'entre eux peut être coloré, donc pas plus de la moitié ne peut être coloré. Ca marche aussi avec les triangles. (j'espère que ma preuve est suffisamment compréensible, car je n'ai quasiment rien détaillé, je peux faire des dessins si vous voulez...)

Bonjour Weierstrass

Je n'ai pas tout compris dans ta démonstration , il faudrait clarifier un peu ( j'ai toujours eu un cerveau extrêmement poussif  ) .

La démo que j'ai est très simple , du niveau d'une classe de seconde

Imod

PS : bien entendu la simplicité est uniquement dans la compréhension de la démonstration (  j'ai déjà donné un indice et j'en donnerai un deuxième au besoin ) .

Non mais evidemment, ma démo est incompréhensible telle que je l'ai exposée, j'avais juste la flemme de faire les dessins

 Cliquez pour afficher

On a un ensemble de compacts colorés.

On pave avec des triangles de côté 1, et on les groupes par 3 de cette manière (2 groupes par hexagone)

Pour chaque groupe, on duplique les traits afin que chaque triangle du groupe soit découpé de la même manière.
Par exemple, pour le groupe bleu en haut à gauche de l'image précédente, on obtient le découpage suivant (j'ai eu la flemme de le faire partout ):


Pour une zone d'un groupe, seul un des trois  morceaux identiques peut être coloré.
Ici, si on regarde la zone bleue claire, on en déduit que le coloriage n'est pas correct, car car le morceau bleu du cercle est à une distance de  du morceau bleu du carré.

On ne peut donc colorier que maximum 1/3 du plan avec des compacts.

Je pense que le résultat est toujours vrai avec une coloration quelconque, mais comme je l'ai dit dans mon précédent message, la preuve telle quelle n'est pas rigoureuse. On doit néanmoins pouvoir l'adapter, en utilisant la mesure de Lebesgue

En utilisant ton message du 27 à 18h27, je pense avoir compris quelle est ta preuve:

 Cliquez pour afficher

Autour de chaque cercle, il y a un anneau  d'épaisseur 1.
La bande à une aire au minimum 8 fois plus grande que celle du cercle.
Si l'on prend le quartier en haut à gauche de l'anneau du cercle, celui ci à donc une aire au moins deux fois supérieure à celle du cercle. De plus, il est facile de vérifier que pour tout autre cercle coloré, leur quartiers respectifs n'entrent pas en collision. On obtient donc que les cercle ne peuvent pas occuper plus d'un tiers du plan.
Cette preuve est moins générale que pour la mienne, car la mienne marche toujours si l'on utilise d'autres formes que les cercles. Celle ci est néanmoins un peu plus simple...  

Je m'aperçois que la borne 1/3 n'est en fait pas atteinte dans le cas général d'une collection de compacts. L'exemple que je donnais était faux. Je conjecture même que l'arrangement optimal est obtenu avec uniquement des cercles, et que c'est celui donné par derny...

@Weierstrass

J'ai relu en détail ton message du 28/08/19 à 19H40 . En fait nous avons deux approches très voisines

 Cliquez pour afficher

Même si ce ne sont pas les premières transformations qui viennent à l'esprit , on peut conclure sans effort en utilisant deux translations bien choisies ( elles sont en filigrane sur tes dessins ) .

A propos de ma deuxième preuve, je remarque qu'elle est complètement fausse.
Déjà, les quartiers de deux cercles peuvent entrer en collision, et l'anneau n'a pas une épaisseur de 1, mais une épaisseur du rayon du cercle. (et l'anneau n'est alors pas collé au cercle.

Cependant, en cherchant à contourner ce problème, j'ai trouvé une borne de 25% dans le cas où on impose que le rayon soit supérieur à 1/2, en prenant les moitiés intérieures des anneaux.... A suivre, peut être que l'on pourra l'adapter pour tout les rayons, mais ça me semble compliqué.

Imod Je n'arrive pas à trouver tes translations, à moins de découper les cercles de la même manière que moi...

Juste un dessin pour ne pas tout dire :

 Cliquez pour afficher

Il doit me manquer quelque chose, en suivant tes translations, les copies des cercles peuvent se superposer...

Tu es sûr ?

Imod

Ah oui, effectivement, ils ne vont pas se toucher, et ta démonstration se généralise également pour tout types de figure, je ne comprends pas pourquoi j'ai cru qu'ils pouvaient s'intersecter...

Bonsoir
Imod et Weierstrass, je n'ai pas compris votre démarche. Pourrait-on avoir un exemple (croquis) d'un tel pourcentage de remplissage ?

Bonsoir Derny

Je ne parle que pour moi  ( Weierstrass a proposé d'autre pistes ) . On part d'un remplissage quelconque du carré et on fait subir à l'ensemble de la figure les deux translations décrites plus haut . On obtient alors trois fois l'ensemble des cercles ( tous disjoints ) dans un rectangle un peu plus grand que le carré initial . Le reste n'est que du calcul sur lequel je vais faire l'impasse .

On doit pouvoir s'approché un peu plus de 1/3 ( je laisse ça aux amateurs , je suis allergique aux inégalités ) .

Imod

Imod, ce qui semble évident pour toi ne l'est pas pour moi. Qu'est ce que ce rectangle ? Ne pourrais-tu pas faire un croquis ?

Désolé , je pensais que les translations étaient évidentes :



Les cercles rouges sont ceux de départ et les bleus et verts les images par les translations dont le vecteur a 1 m de long . Tous les disques sont disjoints et l'ensemble est contenu dans un rectangle un poil plus grand que le carré initial : on obtient une borne légèrement supérieure à 1/3 . Le résultat est clairement le même si on remplace les cercles par des lacets respectant la contrainte initiale .

Imod

Bonjour
Imod, j'avais compris pour les translations mais je ne vois pas en quoi les cercles verts et bleus répondent aux demandes de l'énoncé.

Il est clair que les bleus et les rouges ne vérifient pas les contraintes initiales mais ce n'est pas ce qu'on leur demande . Les rouges vérifient les contraintes dans le petit carré , on ajoute deux copies de ces disques dans un rectangle légèrement plus grand avec tous les disques disjoints  . On a donc on a trois fois la surface rouge dans le rectangle , c'est exactement ce qu'on voulait

Imod

Je ne comprends toujours pas. M'enfin, on a des points (et même "beaucoup") à 1m d'un cercle vert (par exemple) par rapport au cercle rouge (ou bleu) voisin ?

Donc l'énoncé n'était pas clair à mon avis.

Si , l'énoncé et la solution sont très clairs , tu dois passé à côté de quelque chose

Imod

derny Les points considérés sont tous les cercles rouges. Les cercles bleu et vert servent juste à montrer que que la zone rouge ne peut pas recouvrir plus de 1/3 du plan.
Ceci dit, cela aurait été bien aussi de mettre des cercles de différentes tailles dans le dessin, car l'énoncé les autorise. La propriété de non recouvrement reste toujours vraie (et même si on n'a pas que des cercles)

Bonsoir
Merci Weierstrass pour tes éclaircissements. Mais je reste encore septique sur la limite de 1/3 de remplissage à cause des vides entre les cercles. J'aimerais bien voir un cas concret (croquis) qui, sans atteindre 1/3, fasse mieux que ce que j'avais dessiné rapidement sans trop chercher.

Je suis quasiment convaincu que la solution que tu avais donné est optimale. Le problème est de le prouver, et c'est beaucoup plus difficile. Une idée serait peut-être de regarder la preuve de l'optimalite de l'empilement hexagonal et de l'adapter. Mais j'ai carrément l'impression que cette solution est optimale même si on ne prend pas que des cercles. À voir... Il est fortement possible que ce problème ait également été traité dans la littérature