Dix points dans les disques

Domi

Bonjour à tous .

Un problème simple ?

Existe-t-il 10 points du plan euclidien qu’il n’est pas possible d’enfermer dans des disques disjoints de rayon 1 ?

Domi

Soc

Si on arrive à imposer un cercle et que l'on prend deux points extérieurs à ce cercle suffisamment proches entre eux et du cercle, ils vont poser problème.

Reste à trouver une configuration de 8 points qui contraint à prendre un cercle donné (à epsilon près).

bisam

@Domi : Je ne vois pas du tout comment aborder la question, mais ça peut faire un bon TP d'informatique sur le partitionnement de données.

Domi

Merci pour vos réponses.
Même si ce n'est pas indispensable, on peut remarquer que pour un petit nombre de points on pourra toujours trouver les disques et que s'il existe $n$ points qu'on ne peut pas enfermer dans ces disques alors il en existera $n+1$ ayant la même propriété. Reste à savoir à quelle catégorie appartient $n=10$ et pour ce cas je pense avoir une réponse élémentaire et courte (sans disjonctions de cas).
Domi 

[Utilisateur supprimé]

Si tu positionnes 10 points sur un même cercle..

Domi

C'est évident si le rayon du cercle est inférieur à 1 et dans le cas contraire on a par exemple :


Domi

Domi

Le sujet s’endort tout doucement.
L’idée est d’aborder le problème de façon probabiliste. On considère un pavage du plan avec des disques de rayon $1$ disposés de la façon suivante :

 

Si on jette aléatoirement ces disques sur le plan dans lequel on a préalablement choisi un point alors la probabilité pour que ce point soit recouvert est de $\dfrac{\pi}{2\sqrt{3}}\approx 0,91\%$, c’est-à-dire que le nombre moyen de points recouverts est $0,91$. On doit pouvoir admettre que si on place $10$ points dans le plan alors le nombre moyen de points recouverts est $10\times \dfrac{\pi}{2\sqrt{3}}\approx 9,1$. Il existe donc une position des disques recouvrant strictement plus de 9 points.

Domi

JLT

Jolie démonstration ! Pour la rendre rigoureuse, on munit le tore $\R^2/\Z^2$ de la mesure de probabilité uniforme, et on dit que si $A_k$ est l'évènement "le point $k$ n'est pas recouvert", alors $P(A_k)<1/10$ donc $P(A_1\cup\cdots\cup A_{10})<1$.

Reste à voir ce qui se passe pour $11$ points...

Soc

Ici les cercles sont placés et on dispose les points au hasard. Comment vous passez au fait que pour une disposition des points donnée il y a une disposition des cercles satisfaisante ?

Domi

C’est vrai que c’est un peu perturbant mais chaque point peut être est traité indépendamment des autres . Chaque point a une probabilité 0,91 d’être recouvert par la grille de disques posée aléatoirement donc pour n points donnés la grille va cacher en moyenne 0,91n points ( quelle que soit la disposition des points ) .

Domi

Soc

Je ne suis pas convaincu de l'indépendance. Imaginons que ce soit plutôt la grille qui soit placée de façon aléatoire, (selon 2 lois uniformes sur [0;1] pour placer son "centre"), la probabilité qu'un des 10 points donnés soit dans un cercle est bien de 0,91, en revanche il n'y a certainement pas indépendance de la probabilité d'être recouvert entre les 10 points (imaginez par exemple 2 points très proches).

JLT

Soient $M_1,\ldots,M_{10}$ les points donnés. Notons $D=\{(x,y)\in\R^2\mid x^2+y^2<1\}$. Soit $u=(2,0)$ et $v=(1,\sqrt{3})$. Notons $X=\bigcup_{m,n\in\Z} (D+mu+nv)$. Soit enfin $A_k=\{(s,t)\in [0,1]^2\mid M_k\notin (su+tv+X)\}$. Alors $|A_k|<1/10$ (où on note $|A_k|$ la mesure de $A_k$) donc $|\bigcup_{k=1}^{10}A_k|<1$. Par conséquent il existe $(s,t)$ tel que $\forall k$, $(s,t)\notin A_k$, c'est-à-dire $M_k\in su+tv+X$. Ceci signifie que l'ensemble des dix points est recouvert par des disques ouverts disjoints de rayon $1$.

(Si on veut des disques fermés disjoints il faut affiner un peu la démonstration mais ce n'est pas très difficile.)

Domi

Je peux me tromper car je suis totalement incompétent en probabilités mais il me semble que :

1°) lancer 10 grilles sur le plan avec un point donné ;

2°) lancer 1 grille sur le plan avec 10 points donnés

donneront en moyenne autant de points recouverts quelle que soit la disposition des points.

Domi

Soc

Merci JLT c'est plus clair pour moi!

@Domi: J'ai un blocage là dessus, mais oui tu as raison. En fait mon blocage vient de l'appel à l'indépendance qui n'est pas nécessaire ici, une majoration de l'ensemble ne satisfaisant pas suffit. Ton appel à la moyenne cela dit fonctionne bien et pour m'en convaincre j'ai du me dire que si l'on déplace un point, pour toutes les dispositions dont il va sortir il y en a autant pour lesquelles il va rentrer et donc la moyenne ne sera pas affectée.

Domi

La démonstration de JLT montre que l'on peut recouvrir les $10$ points par une simple translation de la grille, ce qui apporte un plus. Sinon j'ai trouvé une vague référence au problème qui indique qu'il serait ouvert avec une fourchette $13\leq n \leq 45$ ($n$ le nombre de points à cacher).
Domi

Soc

S'il y a une position valide de cette grille, elle s'obtient forcément par translation

Pour la fourchette, tu veux dire que la plus petit configuration trouvée que l'on ne peut pas recouvrir contient 45 points?

Domi

Oui , il y a une configuration de 45 points ne pouvant être recouverte



Les points sont sur trois cercles concentriques de rayons $0,1$ ; $0,721$ et $1 ,0001$ .

Domi

Soc

Merci!