Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 29-10-2016 08:54:22

Roro
Membre expert
Inscription : 07-10-2007
Messages : 1 550

Nombre de points dans une couronne

Bonjour,

J'ai une collection de billes qui ne s'aiment pas trop : entre chacune d'elle, il y a une distance d'au moins 1 (mètre).
Je dois ranger le plus de bille possible dans la couronne suivante : [tex]C = \{x \in \mathbb R^d~;~ 1<|x|<2\}[/tex] ([tex]|\cdot|[/tex] désigne la norme euclidienne). Ma question est la suivante : combien puis-je en mettre dans cette couronne ?

En dimension [tex]d=2[/tex], je peux en ranger [tex]12[/tex] mais je ne sais pas si c'est le maximum (j'en suis persuadé mais je ne l'ai pas démontré) !

La vraie question est de savoir ce qu'il se passe en dimension [tex]d=3[/tex]... avec une preuve ?

Roro.

Hors ligne

#2 15-12-2016 16:23:04

PTRK
Membre
Inscription : 14-12-2016
Messages : 101

Re : Nombre de points dans une couronne

Bonjour !

Idée
Dans un espace de dimension n, on va calculer le volume de la couronne, que l'on va diviser par le volume que prend une bille, cad le volume autour d'un bille dans lequel il n'y a pas d'autre .

Alors le volume d'une hyperboule de rayon $r$ de l'espace $\mathbb R^n$ est donné par $ V(n,r) = \dfrac{\pi^{n/2}r^n}{\Gamma(n/2+1)}$ (https://fr.wikipedia.org/wiki/N-sph%C3%A8re)
Donc si on veut que deux billes soient distancées d'au moins d, alors elles délimitent deux hyperboules de rayon d/2 dans lesquelles il n'y a aucune autre bille :
$ V_b(n,d) = \dfrac{\pi^{n/2}(d/2)^n}{\Gamma(n/2+1)}$
Le volume de la couronne tel que $ a < ||x||_{L^2} < b $ est $V_C(n,a,b) = V(n,b)-V(n,a) = \dfrac{\pi^{n/2}(b^n - a^n)}{\Gamma(n/2+1)}$
_________
EDIT:
Le bon majorant du nombres de billes est : $ N_b(n,a',b',d) = N_b(n,a-d/2,b+d/2,d) =  V_C(n,a',b') / V_b(n,d)  = \dfrac{b'^n-a'^n}{(d/2)^n}$ arrondi à l'entier inférieur.$
Cf plus bas

   n     $ N_b(n,1,2,1)$
    1.     4.       
    2.     24.       
    3.     124.       
    4.     624.     
    5.     3124.

Dernière modification par PTRK (05-01-2017 08:40:10)

Hors ligne

#3 16-12-2016 21:30:19

Roro
Membre expert
Inscription : 07-10-2007
Messages : 1 550

Re : Nombre de points dans une couronne

Bonsoir,

Merci PTRK pour ces remarques - je commençais à désespérer de ne voir aucune idée de réponse...

Par contre, j'ai quelques remarques à apporter :

1/ Ta méthode ne semble pas donner le nombre de billes mais seulement un majorant. Il se trouve qu'en dimension 2, on arrive effectivement à placer 12 billes...

2/ Ton raisonnement est basé sur le fait que tu associes à chaque bille, une boule de rayon 1/2 (car les billes sont distantes les unes des autres de 1), mais rien ne me dit que cette boule de rayon 1/2 doit être inclue dans la couronne. D'ailleurs dans le cas de la dimension 2, pour arriver à mettre 12 billes dans la couronne, j'en place certaines (beaucoup) sur le bord ! (car mes billes sont "ponctuelles", ce ne sont pas des boules de rayon 1/2)

Roro.

Dernière modification par Roro (17-12-2016 19:02:54)

Hors ligne

#4 03-01-2017 14:26:18

PTRK
Membre
Inscription : 14-12-2016
Messages : 101

Re : Nombre de points dans une couronne

Roro a écrit :

1/ Ta méthode ne semble pas donner le nombre de billes mais seulement un majorant. Il se trouve qu'en dimension 2, on arrive effectivement à placer 12 billes...

C'est vrai :/

Roro a écrit :

2/ Ton raisonnement est basé sur le fait que tu associes à chaque bille, une boule de rayon 1/2 (car les billes sont distantes les unes des autres de 1), mais rien ne me dit que cette boule de rayon 1/2 doit être inclue dans la couronne. D'ailleurs dans le cas de la dimension 2, pour arriver à mettre 12 billes dans la couronne, j'en place certaines (beaucoup) sur le bord ! (car mes billes sont "ponctuelles", ce ne sont pas des boules de rayon 1/2)

Oups ! En effet j'ai répondu à coté de la plaque.  En effet, je suppose que mes boules sont strictement à l'intérieur et comme tu le dis, les billes pouvant être placées au bords, il faudrait que je considère le volume à l'intérieur est l'extérieur du domaine pour celle se trouvant à une distance plus petite que 1/2 des bords.

Par contre, considérer les billes ponctuelles ou délimitant un volume ne change rien, tant que l'on soustrait le bon volume, ce que j'ai n'ai pas fait.  Mais je t'assure que dire que 2 points doivent être distants de 1, et que deux boules de rayons 1/2 ne peuvent se chevaucher correspond à la même chose.

Allez, au moins, je donne le bon majorant :
Mes billes sont toujours à $d/2$ du bord ? Qu'à cela ne tienne, considérons la couronne $ a'=a-d/2 < ||x|| < b'=b + d/2 $; Dans cette configuration, mes billes seront sur les bords de la premières couronnes.

$ N_b(n,a',b',d) = V_C(n,a',b') / V_b(n,d)  = \dfrac{b'^n-a'^n}{(d/2)^n}$ arrondi à l'entier inférieur.

Dans ton cas : $ N_b(n,0.5,2.5,1) = \dfrac{2.5^n-0.5^n}{0.5^n} = 5^n -1$.

Dernière modification par PTRK (05-01-2017 08:36:14)

Hors ligne

#5 04-01-2017 22:50:17

Roro
Membre expert
Inscription : 07-10-2007
Messages : 1 550

Re : Nombre de points dans une couronne

Bonsoir,

Effectivement, ma question revient au même que de déterminer combien il est possible de mettre de boules de rayon 1/2 à l'intérieur d'une couronne de rayons (1/2, 5/2). Ce qui ne fait pas vraiment avancer le schmilblick puisque la méthode que tu proposes en faisant le quotient des volumes dans ce cas fournit le majorant 24 dans le cas de la dimension 2...

Après réflexions, en dimension 2, j'ai cru que je ne pouvais ranger que 12 billes dans la couronne. Maintenant je pense plutôt pouvoir en ranger 18.

Si d'autres ont des idées !

Roro.

Hors ligne

#6 05-01-2017 08:35:27

PTRK
Membre
Inscription : 14-12-2016
Messages : 101

Re : Nombre de points dans une couronne

A défaut de démontrer, je confirme si n=2, avec un arrangement "CFC", on peut en mettre 18.

Hors ligne

Pied de page des forums