Plus petit disque contenant au moins $k$ points de $\mathbb{Z}^2$.

Tout est dans le titre: il s'agit de trouver le rayon du plus petit disque contenant au moins $k$ points de $\mathbb{Z}^2$. Je suis tombé sur ce problème en regardant un document sur Sagemath via ce lien http://dl.lateralis.org/public/sagebook/sagebook-1.0.pdf  (dans le chapitre 8 corps finis et théorie des nombres) le document propose un encadrement du rayon.

Réponses

  • zygomathique
    Modifié (5 Jun)
    salut

    soit $A_1, A_2, ..., A_k$ k points de $ \Z^2$

    il y a alors deux cas : 
    il existe deux points $A_m \text{ et }A_n$ tels que $A_mA_n = 2r_k$ ($A_mA_n$ est le diamètre du disque)
    pour tout couple de points $(A_m, A_n) : A_mA_n < 2r_k$ (tous les points sont strictement à l'intérieur du disque

    dans tous les cas $2r_k \ge \max \{A_mA_n / (m, n) \in [[1, k]]^2 \}$

    Ce ne sont pas les signes, les symboles qui constituent la science ; le seul principe qui y domine, c’est l’esprit de sagacité auquel les objets soumis servent d’auxiliaire.                BHASCARA

  • Math Coss
    Modifié (5 Jun)
    Il me semble qu'il y a eu un problème de CAPES sur ce thème dans les années 1990 ou 2000 mais je ne sais plus quand (en 1992, il y a eu des choses vaguement analogues mais ce n'est pas ça).
  • Ça me fait penser à un autre énoncé, qui n'est pas non plus sans intérêt : démontrer que pour tout $k \in \mathbb N$ il existe un disque qui contient exactement $k$ points de $\mathbb Z^2$.
  • plsryef
    Modifié (5 Jun)
    Cette dernière question est peut-être plus simple, cela incite à réfléchir modulo 8 et à utiliser la compacité d'un carré d'aire 1 et à utiliser la compacité d'une partie bornée de $\mathbb{Z}^2$, augmenter le rayon d'un cercle dont le centre est à coordonnées entières d' une unité, rajoute un multiple de 4 aux nombres de points pour des raisons de symétrie. Merci pour cette indication.
  • Chaurien
    Modifié (5 Jun)
    Une autre idée est d'exhiber un point $(a,b) \in \mathbb R ^2$ dont les distances aux points de  $ \mathbb Z ^2$ sont toutes distinctes.

  • Math Coss
    Modifié (5 Jun)
    Pour le problème initial, cf. CAPES 1994 : on y calcule $r_1,\dots,r_6$, on y montre que $r_k^2$ est rationnel, on y majore et on y minore $r_k$ pour conclure que $r_k\sim\sqrt{k/\pi}$ lorsque $k$ tend vers l'infini.
  • plsryef
    Modifié (5 Jun)
    Un point P avec une coordonnée transcendante et l'autre rationnelle, si deux points de $\mathbb{Z}$ sont à égale distance de P, P serait sur une médiatrice dont l'équation est à coefficients dans $\mathbb{Q}$, ce qui est absurde. merci pour les références. (C'est la minoration qui m'inquiétait, le sujet de capes 1994, balise tout ça).
  • Chaurien
    Modifié (5 Jun)
    Très beau, ce problème de CAPES 1994, c'est encore un vrai problème de CAPES, pas du genre « que répondez-vous à un élève qui vous dit ci ou ça » (2017-2).
  • Sans regarder les références (c'est donc probablement redondant).

    Prenons un disque $D(a,r)$ (ouvert) de rayon $r$ et de centre $a$, son aire est $\pi r^2$. Notons $A(a,r)$ l'ensemble des carrés $[p-1/2;p+1/2]\times[q-1/2;q+1/2]$ tels que $p,q \in \Z$ et $[p-1/2;p+1/2]\times[q-1/2;q+1/2] \cap D(a,r) \ne 0$. Par définition $D(a,r) \subset A(a,r)$ et en passant à l'aire on trouve $\pi r^2 \le \lambda(A(a,r))$. Comme l'aire d'un carré est $1$ on voit que $\lambda(A(a,r))$ est le nombre de carrés contenus dans $A(a,r)$ et donc le nombre de points à coordonnées entières contenues dans $A(a,r)$. On trouve ainsi $\# (\Z^2 \cap D(a,r)) \le \# (\Z^2 \cap A(a,r)) = \lambda(A(a,r))$. Maintenant puisque le diamètre d'un carré est $\sqrt 2$ on en déduit que $A(a,r) \subset D(a,r+\sqrt 2)$, d'où $\lambda(A(a,r))\le \pi(r+\sqrt 2)^2$.

    Le même type de raisonnement avec $D(a,r-2\sqrt 2)\subset A(a,r-\sqrt 2 )\subset D(a,r)$ nous donne \[\# (\Z^2 \cap D(a,r))\ge \lambda(A(a,r-\sqrt 2)) \ge \pi(r-2\sqrt 2)^2\] Autrement dit $\# (\Z^2 \cap D(a,r)) = \pi r^2 + \varphi(a,r)r $ où $\varphi$ est bornée uniformément lorsque $r$ tend vers $+\infty$. Ceci suffit à démontrer que $r_k\sim \sqrt{k/\pi}$ pour reprendre les notations de mathcoss.

    Une façon de prolonger un peu le problème serait alors de chercher le terme d'ordre $r$ dans le développement asymptotique de $\# (\Z^2 \cap D(a,r))$. À supposer qu'un tel terme existe.


Connectez-vous ou Inscrivez-vous pour répondre.