Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermé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
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 :/
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
Pages : 1
Discussion fermée