Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

R=5 cache-t-il les nœuds ?

Posté par
Imod
10-07-24 à 10:52

Bonjour à tous

Un exercice qui peut faire penser aux cercles de Soddy ou d'Apollonius ou au théorème de Descartes mais on peut participer sans rien connaitre de ces problèmes .

On veut recouvrir l'ensemble des points à coordonnées entières du plan euclidien muni d'un repère orthonormé avec des disques d'intérieurs disjoints . Les disques n'ont pas forcément la même taille mais leurs rayons doivent tous être supérieurs ou égaux à un R donné . Pour R=1 , le recouvrement est possible :

R=5 cache-t-il les nœuds ?

En augmentant R les choses vont nécessairement se compliquer , alors où faut-il ranger R=5 ?

Comme toujours on s'amuse sans blankage inutile

Imod

Posté par
Zormuche
re : R=5 cache-t-il les nœuds ? 11-07-24 à 00:30

Les disques doivent-ils être centrés sur des poitns à coordonnées entières ?

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 08:37

Non les centres des disques sont n'importe où . Les disques peuvent être tangents extérieurement et leurs rayons ne peuvent pas être strictement inférieurs à 5 .
Imod

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 11-07-24 à 10:27

Bonjour,
Pour R = 2, j'y arrive.
Après, je cale

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 10:55

La recherche du rayon limite est sans doute très compliquée . J'ai choisi R=5 car j'ai une démonstration assez simple niveau lycée qu'on peut certainement affiner .
Il n'est pas interdit d'illustrer le cas R=2 pour ceux qui peinent
Il a déjà été dit que les centres des disques ne sont pas forcément des nœuds du quadrillage mais en plus leurs rayons ne sont pas limités supérieurement  ce qui complique encore la tache .
Le problème est très ouvert et il n'est pas interdit de traiter des cas particuliers en ajoutant des contraintes
Imod

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 11-07-24 à 11:44

R=5 ne cache pas tous les noeuds.

En effet, lorsque 3 disques de rayon 5 ou plus sont tangents (extérieurement), il reste entre eux un espace contenant plus qu'un carré unitaire.
Agrandir les disques ne fait qu'agrandir cet espace entre eux.
Ce carré unitaire contient au moins un sommet du quadrillage.
Ce sommet n'est donc pas couvert.

Une façon simple de montrer qu'il y a un carré unitaire est de calculer le rayon du plus grand cercle dans l'espace entre les disque. On obtient r \ge 5(2/\sqrt{3}-1).
Ce rayon est plus grand que 1/\sqrt{2} le rayon du plus petit cercle autour d'un carré unitaire.

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 11-07-24 à 13:19

On peut calculer une valeur plus précise pour le r minimal en encadrant un carré unitaire par 3 cercles de rayon r.

On obtient |r \times (1, \sqrt{3}-1) - (1/2, 1)|^2=(r-1/2)^2+((\sqrt{3}-1)r+1)^2  = r^2 \Rightarrow r \approx 4.01748

Donc pour R > 4.0175 on est sûr qu'il y a des points non recouverts. En dessous, c'est pas sûr

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 11-07-24 à 13:29

Apparemment la forme exacte de r_{min} est \frac{4 + 3 \sqrt{3} + \sqrt{23 + 14 \sqrt{3}}}{4}

Posté par
Zormuche
re : R=5 cache-t-il les nœuds ? 11-07-24 à 15:57

LittleFox Peut-on voir une réalisation pour un tel rayon ?

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 17:16

Attention à ne pas se montrer trop expéditif . Il est clair que si on considère un recouvrement avec des disques de même rayon on perd en efficacité en augmentant ce rayon mais rien ne dit à priori qu'on n'a pas intérêt à panacher avec des rayons différents . Sinon l'idée de regarder si on peut caser un disque de rayon  \frac 1{\sqrt{2}}  est la bonne .

Il est clair qu'il faut illustrer un petit peu

Imod

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 11-07-24 à 17:46

Citation :
Il n'est pas interdit d'illustrer le cas R=2 pour ceux qui peinent
J'illustre :
R=5 cache-t-il les nœuds ?

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 18:10

J'illustre aussi mes réticences :

R=5 cache-t-il les nœuds ?

Pourquoi r serait minimal quand a = b = c ?

Il y a un aspect local et un aspect global du problème .

Imod

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 18:33

@ Sylvieg : si je ne m'abuse ton exemple montre qu'on peut même  aller jusqu'à R=\sqrt{5}
Imod

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 11-07-24 à 18:36


A, B et C ne sont pas fixes, on a intérêt à les rapprocher au maximum pour diminuer r.
Le plus proche qu'ils puissent être est quand a,b,c sont minimum et donc quand ils sont égaux à R.
On peut regarder du côté d'Apollonius si l'intuition ne suffit pas.

@Zormuche
Je dis qu'il n'y a pas de réalisation au delà de ce rayon.
Je ne dis pas qu'il y a de réalisation à ce rayon. Je pense d'ailleurs qu'il n'y en a pas.

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 11-07-24 à 18:46

LittleFox : tu regardes le problème par le petit bout en te fixant sur le point O  mais le déplacement des points A , B et C  a une influence sur l'entourage .  Je ne dis pas que tu as tort mais il ne s'agit pas d'un "simple " problème à quatre disques
Imod  

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 11-07-24 à 19:28

Imod @ 11-07-2024 à 18:33

@ Sylvieg : si je ne m'abuse ton exemple montre qu'on peut même aller jusqu'à R=\sqrt{5}
Imod
Tout à fait.

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 12-07-24 à 08:55

Je réponds à la question "R=5 couvre t'il l'ensemble des points à coordonnées entière". Non.
Et oui, je le fais par un argument local. C'est suffisant. Comme Imod le dit: "La recherche du rayon limite est sans doute très compliquée . ".

J'ai déjà été plus loin en donnant une borne supérieure à ce rayon limite. Sylvieg en donne une borne inférieure.
Je ne prétends pas avoir le rayon limite.

Imod Tu as peut-être une meilleure borne supérieure, je suis impatient de voir comment tu t'y es pris

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 12-07-24 à 10:07

En fait mon approche est sans doute bien plus basique que la tienne même si l'idée de départ est la même . Je cherche le plus grand disque que je peux placer entre les disques recouvrant les nœuds . En translatant et en agrandissant ce cercle on peut considérer qu'il est en contact avec trois des disques recouvrant ( c'est mon dessin précédent ) . Ensuite on ne fait pas dans la finesse , on borne sans se préoccuper du cadre de l'exercice en gardant juste l'idée d'avoir un rayon supérieur ou inférieur à \frac 1{\sqrt{2}} . Deux remarques initiales : l'un des angles en O est inférieure ou égal à 120°  ( disons AÔB ) et comme les cercles sont d'intérieurs disjoints , AB est inférieure ou égale à a+b .  Après si on note M la borne supérieure des rayons , Pythagore généralisé donne 12r^2\geq (M-3r)^2 . Sauf erreur , avec cette méthode , la valeur extrémale de M est \sqrt{6}+\frac 3{\sqrt{2}}\approx 4,57 . Je suis bien  au dessus de ton estimation

Imod

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 12-07-24 à 14:55

@Imod,
J'ai un peu de mal à tout comprendre dans ton message
Entre autres ceci :

Citation :
comme les cercles sont d'intérieurs disjoints , AB est inférieure ou égale à a+b .

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 12-07-24 à 18:06

Si on relie A et B on traverse le rayon  a , un segment puis le rayon b .
Imod

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 12-07-24 à 18:14

Donc AB est supérieure ou égale à a+b . Les inégalités je les prends à l'envers une fois sur 2
Imod

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 13-07-24 à 18:32

J'ai fait le calcul autrement en cherchant le rayon r du plus grand disque que l'on peut coincer entre trois disques de rayon R . On trouve r=(\frac 2{\sqrt{3}}-1)R et si on prend r=\frac 1{\sqrt{2}} alors R=\sqrt{6}+\frac 3{\sqrt{2}}  , qui est exactement le résultat obtenu avec l'autre méthode , je ne vois pas comment LittleFox arrive à un résultat inférieur . De toute façon on peut pas recouvrir tous les nœuds avec des disques de rayons supérieurs ou égaux à 5 .  De plus le pavage du plan avec des disques de même rayon s'embrassant mutuellement ne s'accorde pas vraiment avec le pavage carré : il reste donc pas mal de pain sur la planche .
Je ne sais pas si on peut aller beaucoup plus loin dans le problème même si la marge entre le  \sqrt{5} de Sylvieg et celui que je propose laisse largement assez de place pour une démonstration à la Fermat
Imod

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 13-07-24 à 19:54

J'ai été plus loin que le cercle entourant un carré unitaire.
J'ai encerclé directement un carré unitaire par 3 cercles de rayon R

Un des cercle est tangent au milieu d'un côté du carré et un autre touche un sommet opposé à ce côté.
Les centres des 3 cercles forment un triangle équilatéral.

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 13-07-24 à 23:01

Il faudrait préciser un peu le cadre dans lequel tu te places , personnellement je ne comprends pas
Imod

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les n?uds ? 14-07-24 à 15:07

Bonjour,
Je coince pour comprendre comment on peut trouver la minoration par \; \sqrt{6}+\dfrac 3{\sqrt{2}} \;
J'utilise la figure d'Imod\; r \leq \dfrac{1}{\sqrt{2}} \;.

R=5 cache-t-il les n?uds ?
Au début tout va bien :

Citation :
l'un des angles en O est inférieure ou égal à 120° ( disons AÔB )
AB2 = (a+r)2 + (b+r)2 - 2(a+r)(b+r)cos(AÔB)
AB a+b \; et \; -cos(AÔB) 1/2 .
D'où \; (a+b)2 AB2 (a+r)2 + (b+r)2 + (a+r)(b+r)
Ce qui donne bien \; (a-3r)(b-3r) 12r2 .
Remarquer que a-3r et b-3r sont positifs si on suppose les trois rayons a, b et c supérieurs ou égaux à 5.
Si \; a b \; alors \; (a-3r)2 12r2 6 .
D'où \; a 3r + 6 .

Mais quid de c ?

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 14-07-24 à 15:51


On cherche le plus grand R tel que tous les points à coordonnées entières soient couverts.

Il faut au moins que les points (0,0), (1,0), (1,1) et (0,1) soient couverts (condition nécessaire mais pas suffisante).

La disposition optimale pour couvrir ces 4 points est:
R=5 cache-t-il les nœuds ?

En effet:
- Utiliser plus de 3 cercles (pour le même R) libère un des sommets.
- Utiliser des cercles non adjacents libère un des sommets.
- Utiliser un ou plusieurs cercle de rayon > R libère un des sommets.
- Utiliser une autre rotation de l'ensemble des cercles libère un des sommets.

Le point A a pour coordonnées A=(\frac{1}{2}, -\sqrt{R^2-(\frac{1}{2})^2}).
Le point B a pour coordonnées B=A + 2R(\frac{-1}{2},\frac{\sqrt{3}}{2}) = A + (-R,R\sqrt{3})=(\frac{1}{2}-R, R\sqrt{3}-\sqrt{R^2-(\frac{1}{2})^2})
Le point B est à une distance R du point (0,1). On a donc (\frac{1}{2}-R)^2 + ( R\sqrt{3}-\sqrt{R^2-(\frac{1}{2})^2}-1)^2 = R^2.
Cette équation n'est pas simple, une résolution numérique donne R \approx 3.9504.

On a donc que le rayon limite est < 3.9504. En particulier R=5 (ou 4) est trop grand.

Notez que ce n'est qu'une limite supérieure. En effet, par exemple, le point (4,-2) n'est pas couvert.

Note: Cette limite est inférieure à la précédente limite que j'avais trouvée. J'avais, à tord, mis le cercle inférieur tangent au carré.

On peut voir ces contraintes de manière hiérarchique: Couvrir les 4 points < Couvrir le carré (précédente borne) < Couvrir le cercle circonscrit (borne de Imod)

Voilà, j'espère que c'est plus clair

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 14-07-24 à 19:08

J'ai simplement survolé vos messages , je reviens ce soir avec un peu plus de temps

@Sylvieg : Les rayons sont supérieurs à 5 et pas à \sqrt{5} , on a donc immédiatement (5-3r)^2\leq 12r^2 , le reste suit .

@LittleFox : Je ne comprenais pas ton message car le cercle du bas ne passe pas le milieu du segment du bas mais par ses deux extrémités . Il reste un autre point qui mérite d'être éclairci : pourquoi les trois cercles qui titillent les quatre points du carré unité seraient-ils de même rayon ?

Merci à tous les deux pour vos réponses

Imod

Posté par
LittleFox
re : R=5 cache-t-il les nœuds ? 14-07-24 à 20:56

Il me semble évident que tout cercle de rayon plus grand que R ne fait que libérer plus d'espace au centre des 3 cercles:

R=5 cache-t-il les nœuds ?

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 14-07-24 à 22:34

D'accord , j'ai du mal à faire la part des choses entre le local et le global . En fait ici il faut dessiner le plus petit carré dont les sommets sont sur la frontière d'un triangle de Reuleaux inversé .
Imod

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 15-07-24 à 08:47

Citation :
@Sylvieg : Les rayons sont supérieurs à 5 et pas à \sqrt{5} , on a donc immédiatement (5-3r)^2\leq 12r^2
Oui, si les rayons sont supérieurs ou égaux à 5 alors (5-3r)^2\leq 12r^2 donne r2 > 1/2.
Et pas de recouvrement possible.

Tu as cherché à améliorer la valeur 5 en trouvant une valeur plus petite à partir de laquelle on ne peut pas recouvrir.
J'ai choisi d'utiliser 5 car on sait qu'on peut trouver un recouvrement avec R = 5.

Posté par
Sylvieg Moderateur
re : R=5 cache-t-il les nœuds ? 15-07-24 à 09:37

Merci d'oublier mon "Mais quid de c ?" à la fin du message d'hier à 15h07.
A remplacer par :
S'il y a recouvrement alors \; r^{2} \leq \dfrac{1}{2} .
Et \; a \leq 3r + \sqrt{6} \leq \dfrac{3}{\sqrt{2}} + \sqrt{6} .
Un des trois rayons est inférieur ou égal à \; \dfrac{3}{\sqrt{2}} + \sqrt{6} .
On ne peut donc pas recouvrir avec des cercles de rayons tous supérieurs stricts à \; \dfrac{3}{\sqrt{2}} + \sqrt{6} .

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 15-07-24 à 12:20

Dans la figure de LittleFox , la position du carré bleu dans le triangle formé par les centres des cercles mérite d'être étudiée . Il y a trois possibilités équivalentes  selon le côté du triangle que l'on va privilégier mais les angles de la figure sont toujours des multiples de 15° . Ensuite , il y a une multitude de triangles semblables  , une valeur exacte du rayon dans cette situation ne semble pas hors de portée .

Imod

Posté par
Imod
re : R=5 cache-t-il les nœuds ? 18-07-24 à 12:07

Bon , en fait je ne fais pas mieux que LittleFox . Pour abaisser la borne supérieure , il faudrait faire appel à plus de trois disques et là on n'est plus dans la détente . De même la borne inférieure proposée par Syvieg  semble difficile à améliorer sans une construction complexe .
Avis aux amateurs
Imod



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !