Un défi par semaine

Mai 2020, 4e défi

Le 22 mai 2020  - Ecrit par  Ana Rechtman Voir les commentaires (11)
Lire l'article en  

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante. Le calendrier 2020 est en vente !

Semaine 21

Dans le plan cartésien on dessine toutes les lignes droites passant par le point $(0,0)$ et les points de coordonnées $(x,y)$ où $1\leq x \leq 10$ et $1\leq y \leq 10$ sont des nombres entiers.

Combien de droites distinctes dessine-t-on ? (par exemple, la droite passant par $(1,2)$ est la même que celle qui passe par $(2,4)$).

Solution du 3e défi de mai :

Enoncé

Considérons tout d’abord les quatre petits carrés situés dans les coins. Il y a $2^4=16$ colorations initiales différentes de ces quatre petits carrés, toutes équiprobables. Analysons les quatre cas possibles :

  • Tous les coins sont noirs. Il y a alors une seule possibilité de coloration initiale des coins, à savoir $NNNN$, et après l’opération, tous sont noirs.
  • Il y a un coin blanc. Il y a alors quatre possibilités de coloration initiale des coins, à savoir $BNNN$, $NBNN$, $NNBN$ et $NNNB$. Après l’opération, les quatre coins sont noirs puisque le coin blanc se retrouve nécessairement sur un coin noir et est donc peint en noir.
  • Il y a deux coins blancs. Il y a alors six possibilités de coloration initiale des coins. Dans les cas, $NBNB$ et $BNBN$, tous les coins deviennent noirs après l’opération et dans les cas $BBNN$, $NNBB$, $NBBN$ et $BNNB$, un des petits carrés reste blanc.
  • Il y a trois coins blancs. Il y a alors quatre possibilités de coloration initiale des coins et après l’opération, deux coins restent blancs.
  • Tous les coins sont blancs : une seule possibilité et évidemment, dans ce cas, tous les coins restent blancs.

Au final, sur les $16$ colorations initiales possibles des coins, tous
les coins deviennent noirs dans sept cas, ce qui nous donne une
probabilité de $\frac{7}{16}$. De même, pour les quatre autres petits
carrés situés sur le bord du grand carré, ils deviennent tous noirs
avec une probabilité de $\frac{7}{16}$. Quant au petit carré central,
il ne bouge pas après la rotation. Il sera donc noir après l’opération
si et seulement si il l’était au début, c’est-à-dire avec une
probabilité de $\frac{1}{2}$. Au total, la probabilité que l’intégralité du grand carré devienne noire estde $\frac{1}{2}\times(\frac{7}{16})^2=\frac{49}{512}$.

La solution est $\dfrac{49}{512}$.

Post-scriptum :

Calendrier mathématique 2020 - Sous la direction d’Ana Rechtman, avec la contribution de Nicolas Hussenot - Textes : Serge Abiteboul, Charlotte Truchet. 2019, Presses universitaires de Grenoble. Tous droits réservés.

Disponible en librairie et sur www.pug.fr

Partager cet article

Pour citer cet article :

Ana Rechtman — «Mai 2020, 4e défi» — Images des Mathématiques, CNRS, 2020

Crédits image :

Image à la une -
  • HARVEPINO / SHUTTERSTOCK

Commentaire sur l'article

  • Mai 2020, 4e défi

    le 22 mai à 09:27, par Elrigo

    Pour x = 1, on a déjà 10 droites en prenant successivement les 10 valeurs entières de y.

    Ensuite, pour x supérieur ou égal à 2, en incrémentant x de 1, le point (x ; y) donne une nouvelle droite si et seulement si x et y sont premiers entre eux.

    Si je ne me trompe pas, cela donne 64 droites en doute.

    Répondre à ce message
    • Mai 2020, 4e défi

      le 22 mai à 09:28, par Elrigo

      *en tout*, et non en doute...
      un lapsus...

      Répondre à ce message
      • Mai 2020, 4e défi

        le 22 mai à 09:36, par François

        Mon logiciel Maple n’en a compté que 63 ! Il a compté le nombre de paires (x,y) où x et y étaient premiers entre eux . Si (x,y) convient alors (y,x) convient et (1,1) convient aussi. Cela fait un nombre impair !

        Répondre à ce message
    • Mai 2020, 4e défi

      le 22 mai à 10:02, par bistraque

      Le nombre est forcément impair puisque symétrique par rapport à la droite y=x. Le calcul précédent semble compter deux fois cette droite. La réponse est donc 63.

      Répondre à ce message
  • Mai 2020, 4e défi

    le 22 mai à 10:04, par Al_louarn

    Il suffit de compter les couples $(x,y)$ tels que $1 \leq x < y \leq 10$ et $x$ et $y$ premiers entre eux. Ensuite on multiplie par $2$ pour compter les symétriques $(y,x)$, et on ajoute $1$ pour compter le point $(1,1)$. Par définition, le nombre de $x$ inférieurs à $y$ et premiers avec $y$ est $\phi(y)$, où $\phi$ est la fonction indicatrice d’Euler. Ainsi le nombre de droites est :
    \[N =1+2(\phi(2) + \phi(3) + ... + \phi(10))\]
    Avec la convention $\phi(1)=1$, cette fonction présente quelques propriétés facilitant les calculs.
    D’abord on a $\phi(p)=p-1$ pour tout nombre premier $p$.
    Ensuite $\phi(nm) = \phi(n) \phi(m)$ si $n$ et $m$ sont premiers entre eux.
    Ainsi nous avons :
    $\phi(5)=4$
    $\phi(6)=\phi(2)\phi(3)=1 \times 2=2$
    $\phi(7)=6$
    $\phi(10)=\phi(2)\phi(5)=1 \times 4=4$
    Et pour finir utilisons la formule qui nous dit que tout entier $n>0$ est la somme des valeurs de $\phi$ sur tous ses diviseurs : $\Sigma_{d|n}\phi(d)=n$
    Ainsi :
    $\phi(1) + \phi(2) + \phi(4) + \phi(8) = 8$, d’où $\phi(2) + \phi(4) + \phi(8) = 7$
    $\phi(1) + \phi(3) + \phi(9) = 9$, d’où $\phi(3) + \phi(9) = 8$
    Il ne reste plus qu’à rassembler les morceaux :
    \[N =1+2(4+2+6+4+7+8)=63\]

    Répondre à ce message
    • Mai 2020, 4e défi

      le 22 mai à 10:58, par Al_louarn

      On peut essayer de généraliser pour $n$ à la place de $10$, mais il semble qu’aucune formule simple ne soit connue pour $\Phi(n)=\phi(1)+...+\phi(n)$, sans doute parce que $\phi$ est trop irrégulière. On sait toutefois que $\Phi(n)$ tend vers $3(\frac{n}{\pi})^2$, donc notre nombre de droites $N(n)$ tend vers $6(\frac{n}{\pi})^2 - 1 = \frac{n^2}{\zeta(2)}-1$, où $\zeta$ est la fonction de Riemann : $\zeta(s)=\frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + ...$
      Ceci nous donne une curieuse façon d’approcher $\pi$ en comptant des droites : $n \sqrt{\frac{6}{N(n)-1}}$. Pour $n=10$ on trouve à peu près $3.11$, bof, pas terrible...

      Répondre à ce message
      • Mai 2020, 4e défi

        le 22 mai à 14:51, par Al_louarn

        Oups ! Erreur de signe, la formule approchant $\pi$ est $n \sqrt{\frac{6}{N(n)+1}}$
        Du coup pour $n=10$ on obtient environ $3.06$, encore pire !

        Répondre à ce message
      • Mai 2020, 4e défi

        le 22 mai à 18:57, par Vincent Lefèvre

        L’expression

        $N(n)$ tend vers $6(\frac{n}{\pi})^2 - 1 = \frac{n^2}{\zeta(2)}-1$

        n’a pas beaucoup de sens, car cela dépend de $n$, et il faudrait connaître le $O$ ou le $o$. Et d’après Euler’s totient function sur Wikipedia, ce qui est négligé n’est pas en $o(1)$, donc le $-1$ est inutile et peut être mal interprété avec le « tend vers ».

        Répondre à ce message
        • Mai 2020, 4e défi

          le 27 mai à 23:21, par Al_louarn

          Merci pour votre remarque
          Donc si je rectifie, on peut juste dire que, par exemple, la limite de $\frac{n^2}{N(n)}$ est $\zeta(2)$ (quand $n$ tend vers l’infini bien sûr)

          Répondre à ce message
    • Mai 2020, 4e défi

      le 22 mai à 15:35, par amic

      Une autre manière de procéder par inclusion-exclusion (cribble).

      On retient toutes les droites de la forme (0,0)→(x,y), en comptant les doublons : 10×10.

      On retire tous les points dont le pgcd des coordonnées est divisible par 2 (les (2x’,2y’) avec 1⩽x’,y’⩽5) : 5×5.
      On retire tous les points dont le pgcd des coordonnées est divisible par 3 (les (3x’,3y’) avec 1⩽x’,y’⩽3) : 3×3.
      On retire tous les points dont le pgcd des coordonnées est divisible par 5 (les (5x’,5y’) avec 1⩽x’,y’⩽2) : 2×2.
      On retire tous les points dont le pgcd des coordonnées est divisible par 7 (les (7x’,7y’) avec 1⩽x’,y’⩽1) : 1×1.

      On rajoute tous ceux dont le pgcd était divisible par 6 (les (7x’,7y’) avec 1⩽x’,y’⩽1, ils ont été retirés 2 fois) : 1×1.
      On rajoute tous ceux dont le pgcd était divisible par 6 (les (7x’,7y’) avec 1⩽x’,y’⩽1, ils ont été retirés 2 fois) : 1×1.

      Au total 100-25-9-4-1+1+1 = 63.

      Répondre à ce message
      • Mai 2020, 4e défi

        le 22 mai à 15:50, par amic

        Cela se généralise, et permet de calculer cette somme des indicatrices d’Euler plus rapidement.

        Si on est malin (et si je ne me plante pas), on peut calculer ça en approximativement n^(2/3) opérations (à un facteur logarithmique près).

        https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method
        https://fr.wikipedia.org/wiki/Formule_d%27inversion_de_M%C3%B6bius#Arithm%C3%A9tique_modulaire

        https://mathproblems123.wordpress.com/2018/05/10/sum-of-the-euler-totient-function/

        Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?