Jusqu’où peut-on voir à l’horizon ?

C’est bientôt les grandes vacances, et vous allez peut-être profiter du soleil et de la mer durant cette période estivale. Au bord de la plage, les pieds dans l’eau, vous regarderez au loin vers l’horizon… Et là vous vous direz peut-être: mais ce point lointain à l’horizon, à quelle distance se situe-t-il ? Puis-je voir les côtes américaines si je regarde la mer depuis les plages de Bretagne ? C’est à cette question existentielle que nous allons répondre ci-dessous.

La Terre est bleue comme une orange (et ronde comme Maïté)

Comme vous le savez, la Terre est ronde (ou plutôt ellipsoïdale !), donc si vous regardez droit devant vous, il y a un moment où une partie de la Terre va être cachée. Nous allons essayer de préciser où se situe cet endroit géométriquement.

On assimile la Terre a une sphère de centre O et de rayon R=6371km. Imaginons un observateur M de hauteur h situé les pieds dans l’eau et regardant le point P à l’horizon devant lui:horizon_modelisation_du_problemePuisque le rayon lumineux venant de l’horizon qui parvient aux yeux de notre observateur ne touche la Terre qu’en un seul point (l’horizon, justement !), la droite (PM) est donc une tangente à la Terre:

horizon_modelisation_triangle_rectanglePour savoir jusqu’où on peut voir à l’horizon, il nous faut calculer la distance d. Je ne vais pas faire durer le suspense plus longtemps car tout le monde voit qu’il faut utiliser le théorème de Pythagore. En effet, comme le triangle PMO est rectangle en P, on a la relation (R+h)^2=R^2+d^2 qui est équivalente à  d^2= (R+h)^2-R^2. En développant cette dernière, on obtient :

d^2=R^2+2Rh+h^2-R^2

ce qui donne

d^2=2Rh+h^2

et on en déduit ainsi que:

\boxed{d=\sqrt{2Rh+h^2}}

Application numérique

Si on choisit une personne de taille moyenne, c’est-à-dire h = 1,70m, on trouve que la distance d qui la sépare de l’horizon est:

d = \sqrt{2 \times 6371 \times 1.7 \cdot 10^{-3} + (1.7 \cdot 10^{-3})^2} \simeq 4,65km

Donc, quand vous regardez à l’horizon, vous voyez seulement à environ 5km devant vous ! Je ne sais pas vous, mais j’étais persuadé qu’on voyait plus loin que cela. On n’a donc aucune chance de voir les côtes américaines depuis les côtes du Finistère… Quelle déception.

Aller plus haut…

Bon, maintenant qu’on a une formule, autant la rentabiliser. Si vous montez au sommet de la Tour Eiffel, vous verrez évidemment beaucoup plus loin à l’horizon que si vous avez les pieds au sol. Le 3ème étage étant situé à 276m au-dessus du sol, de cet endroit vous pouvez voir à 59 km à la ronde !

Depuis la tour Eiffel, vous pouvez voir jusqu'à environ 60km au loin. Sauf en cas d'alerte pollution de niveau 3 (c'est-à-dire 2 jours par an). Source de l'image: http://fr.wikipedia.org/wiki/Tour_Eiffel

Depuis la tour Eiffel, vous pouvez voir jusqu’à environ 60km au loin. Sauf en cas d’alerte pollution (donc seulement 2 jours par an).
Source de l’image: http://fr.wikipedia.org/wiki/Tour_Eiffel

Et si on monte encore plus haut ? Le monument le plus grand créé par l’homme est la tour Burj Khalifa, située à Dubaï et qui mesure 828 mètres. Le 163ème et dernier étage est situé à une hauteur de 584 mètres. De cet étage, on peut donc voir à 86 km au loin !

Et à la nage ?

Remettons les pieds sur Terre et revenons au bord de la plage. Puisque la Terre est ronde, la distance à la nage et la distance à vol d’oiseau ne sont pas exactement les mêmes. Que vaut donc cette distance à la nage ?horizon_distance_vol_oiseau_distance_nagePour faire le calcul exact de la distance à la nage, il va falloir utiliser un peu de trigonométrie élémentaire:horizon_distance_nage_notationsLe fameux CAHSOHTOA™ appliqué au triangle PMO (qui est toujours rectangle, il n’a pas changé) nous donne

\cos(\theta) = \dfrac{R}{R+h}

La distance à la nage est la longueur d' de l’arc de cercle bleu. On sait que la longueur de cet arc est donnée par la formule  d' = R \cdot \theta. Ainsi,

\boxed{ d'= R \cdot \cos^{-1} \left( \frac{R}{R+h} \right) }

Lorsqu’on fait l’application numérique pour un humain d’1,70m, on trouve que la distance d' vaut environ 4,65 km, ce qui est autant que ce qu’on avait trouvé pour la distance à vol d’oiseau (en fait les distances à vol d’oiseau et à la nage sont égales jusqu’à la 5ème décimale !).

Je ne pense pas que cela étonne grand monde que ces distances soient semblables, mais essayons tout de même de donner une explication mathématique à cela.

Équivalents

Le fait que ces distances soient très proches vient, comme on s’y attend, du fait que la taille d’un homme (ou même de la Tour Eiffel !) est très petite par rapport à celle de la Terre.

Pour le prouver, commençons par donner deux équivalents (au sens mathématique du terme). Si x est voisin de 0 alors:

\sqrt{2x+x^2} \sim \sqrt{2x}

et

\cos^{-1}\left(\dfrac{1}{1+x}\right) \sim \sqrt{2x}

La démonstration de ces deux propriétés est donnée en fin d’article.

Si la hauteur h est très petite devant le rayon R alors le rapport h/R est très proche de 0. Donc on pourra remplacer x par h/R dans les équivalents précédents:

d= \sqrt{2Rh+h^2}=R\sqrt{2 \frac{h}{R}+\left(\frac{h}{R} \right)^2} \sim R \sqrt{2\frac{h}{R}} = \sqrt{2Rh}

et

d' = R \cos ^{-1} \left( \frac{R}{R+h} \right) = R \cos^{-1} \left( \frac{1}{1+ \frac{h}{R}} \right) \sim R\sqrt{2 \frac{h}{R}} = \sqrt{2Rh}

Voilà donc pourquoi ces distances sont du même ordre si h est petit !

Cas d’un satellite

En revanche, si on s’élève très haut dans le ciel, les distances à vol d’oiseau et à la nage vont commencer à ne plus être comparables.

Par exemple, imaginons un satellite géostationnaire, c’est-à-dire situé à une altitude h=36 000 km. La distance à vol d’oiseau est environ de 41 900 km alors que la distance au sol (« à la nage ») est environ de 9 045 de km (autrement dit, si une personne située au sol exactement sous le satellite devait marcher tout droit pour rejoindre le point le plus éloigné que le satellite peut voir, elle marcherait 9 045 km). Comme la hauteur n’est plus négligeable devant le rayon de la Terre, il n’est donc pas étonnant que ces deux valeurs ne soient plus du même ordre de grandeur.

Si on s’élève indéfiniment dans le ciel, la distance à vol d’oiseau va bien entendu tendre vers +\infty alors que la distance à la nage va tendre vers le quart de la circonférence de la Terre, comme on le devine sur l’animation ci-dessous:

En rouge, la distance à vol d’oiseau et en bleu, la distance à la nage. Si on zoome, on peut voir George Clooney dans le satellite, en train de tourner Gravity.

Voilà donc un bel exemple visuel de bijection d’un intervalle de longueur infini vers un intervalle de longueur finie !

Note:

Voici les calculs des équivalents donnés dans l’article.

Publié dans Géométrie | Marqué avec , , , , , , | Laisser un commentaire

La loi de Poisson… avec des poissons

La loi de Poisson (du mathématicien Siméon Denis Poisson) est une loi de probabilité permettant de mesurer le nombre d’événements qui se produisent dans un intervalle de temps donné, lorsque ces événements sont plutôt rares et indépendants. Par exemple, la loi de Poisson permet de décrire plutôt précisément le nombre X de voitures qui passent dans votre rue dans un laps de temps donné (sauf si vous habitez en face du périph’).

Dans le cas d’une loi de Poisson, la probabilité que k événements se produisent dans un intervalle de temps fixé (par exemple, que 10 voitures passent dans votre rue en une heure) est donnée par la formule:

P(X=k)= \dfrac{\lambda^k\text{e}^{-\lambda}}{k!}

\lambda est un paramètre donné.

C’est une formule étonnante et qui a l’air compliquée… la première fois que je l’ai vue, j’ai vraiment eu le sentiment qu’elle sortait de nulle part. Comment une exponentielle et une factorielle peuvent se retrouver à expliquer plutôt correctement des phénomènes rares ?

Nous allons tenter d’expliquer d’où vient cette expression qui semble tomber du Ciel. Et pour cela, quoi de mieux que des poissons pour illustrer la loi de Poisson ?

La cabane du pêcheur

Tous les dimanches, un pêcheur s’installe au bord d’une rivière pour pêcher la truite cendrée. On sait qu’en moyenne il attrape \lambda =2,4 poissons par heure.

Notre pêcheur vient de s’installer à son endroit favori pour commencer sa partie de pêche hebdomadaire. Quelle est la probabilité qu’il attrape k poissons en une heure ? (où k est un entier naturel quelconque).

Ca, c'est de la punchline.

Ca, c’est de la punchline où je ne m’y connais pas en truites.

Découpages temporels

Tout d’abord, on peut raisonnablement faire les hypothèses suivantes sur cette partie de pêche:

  • Le fait d’attraper un poisson à une minute donnée est indépendant du fait d’attraper un poisson à la minute suivante
  • Le pêcheur attrape au plus une truite à chaque minute (le temps de la sortir de l’eau, de la décrocher de l’hameçon et de boire une gorgée de Heineken…)
  • Le pêcheur a autant de chances d’attraper un poisson à chaque minute, donc la probabilité d’attraper une truite à une minute donnée est p=\frac{2,4}{60}.

Si on découpe une heure en 60 minutes, une heure de pêche revient donc à considérer qu’on répète 60 fois de suite et de manière indépendante une même expérience aléatoire à deux issues (« j’attrape un poisson » ou « je n’attrape pas un poisson ») . Vous reconnaissez ainsi une bonne vieille loi binomiale: si on note X le nombre de poissons pêchés en une heure, alors X suit la loi binomiale de paramètres n=60 et p=\frac{2,4}{60}.

Si notre pêcheur attrape 3 poissons en une heure, on peut considérer cela comme 60 expériences d'une minute durant lesquelles soit il attrape un poisson, soit il n'en attrape pas.

Si notre pêcheur attrape k=3 poissons en une heure, on peut considérer cela comme 3 succès lors de 60 expériences aléatoires indépendantes d’une minute chacune.

Si vous vous souvenez de vos années lycée, vous devriez vous rappeler de cette formule pour la loi binomiale:

\displaystyle P(X=k) = {60 \choose k} \left(\frac{2,4}{60} \right)^k \left(1-\frac{2,4}{60} \right)^{60-k}

Mais où sont les exponentielles et les factorielles dont je vous ai parlé au départ ? Elles arrivent, patientez encore un peu…

Chasse, pêche, nature et traditions

Il y a peut-être des spécialistes de la pêche (ils sont nombreux à lire ce blog, je le sais) qui vont me dire qu’il se peut qu’un bon pêcheur puisse attraper plus d’un poisson en une minute. Cela remettrait donc en cause notre loi binomiale précédente.

Pour ne pas les contrarier, nous allons affiner notre raisonnement précédent et, au lieu de découper une heure en 60 minutes, nous allons la découper en 3600 secondes (car je doute fort qu’un pêcheur attrape plus d’un poisson par seconde !).

Autrement dit, le nombre X de poissons pêchés suit là encore une loi binomiale, mais les paramètres sont cette fois n=3600 et p=\frac{2,4}{3600}. Ainsi, la probabilité de pêcher k poissons en une heure est:

\displaystyle P(X=k) = {3600 \choose k} \left( \frac{2,4}{3600} \right)^k \left( 1- \frac{2,4}{3600}\right)^{3600-k}

Mais si on y réfléchit bien, au lieu de découper une heure en 60 minutes ou en 3600 secondes, on peut la découper en n unités de temps quelconques, sans que cela change grand chose si n est assez grand, c’est-à-dire si cette unité de temps est suffisamment petite pour que le pêcheur ne puisse pas attraper plus d’un poisson pendant celle-ci. Ainsi,

\displaystyle P(X=k) = {n \choose k} \left( \frac{2,4}{n} \right)^k \left( 1- \frac{2,4}{n}\right)^{n-k}

Si on considère que plus nos intervalles de temps sont fins (c’est-à-dire plus n est grand), plus notre modèle se rapproche de la réalité, alors on peut affirmer que la probabilité de pêcher k poissons en une heure est:

\displaystyle P(X=k) = \lim_{n \to \infty} {n\choose k} \left( \frac{\lambda}{n} \right)^k \left( 1- \frac{\lambda}{n}\right)^{n-k}

(où \lambda=2,4). Il nous reste à présent à calculer cette limite pour voir apparaître une factorielle et une exponentielle.

Calcul de la limite

La première chose à faire pour calculer cette limite va être d’exprimer le coefficient binomial {n \choose k} en fonction de n et k. Vous n’êtes sans doute pas sans connaître la formule suivante:

\displaystyle {n \choose k} = \dfrac{n!}{(n-k)! k!} = \dfrac{n(n-1)(n-2) \cdots (n-k+1)}{k!}

Nous voyons déjà apparaître notre factorielle. De cela et de quelques manipulations algébriques élémentaires, on en déduit que:

\begin{array}{ccl}  \displaystyle {n \choose k} \left( \frac{\lambda}{n} \right)^k \left( 1- \frac{\lambda}{n}\right)^{n-k} &=& \displaystyle \frac{n(n-1)(n-2) \cdots (n-k+1)}{k!} \left( \frac{\lambda}{n} \right)^k \left( 1- \frac{\lambda}{n}\right)^{n-k}\\  & & \\  & = & \displaystyle \frac{n(n-1)(n-2) \cdots (n-k+1)}{n^k} \frac{\lambda^k}{k!} \left( 1- \frac{\lambda}{n}\right)^{n} \left( 1- \frac{\lambda}{n}\right)^{-k}\\  \end{array}

Pour trouver la limite de cette expression quand n tend vers +\infty, il nous suffit donc de trouver la limite de chacun des facteurs de cette expression.

Tout d’abord, \displaystyle \lim_{n \to +\infty} \frac{n(n-1)(n-2) \cdots (n-k+1)}{n^k} = \lim_{n\to \infty} \frac{n^k}{n^k} = 1 car la limite en l’infini d’une fraction rationnelle est la limite des monômes de plus haut degré.

D’autre part, \displaystyle \lim_{n \to +\infty} \frac{\lambda^k}{k!} = \frac{\lambda^k}{k!} car cette expression ne dépend pas de n.

Ensuite, \displaystyle \lim_{n \to +\infty} \left(1 - \frac{\lambda}{n} \right)^n = \text{e}^{-\lambda} (c’est donc de là que vient notre exponentielle !). On peut prouver cela de manière élémentaire et j’ai mis les détails en fin d’article pour ceux que ça intéresse.

Enfin, \displaystyle \lim_{n \to +\infty} \left(1-\frac{\lambda}{n}\right)^{-k} = 1 car \displaystyle \lim_{n \to +\infty} 1 - \frac{\lambda}{n}=1 (n’oublions pas que k est fixé et que la limite d’un produit (fini) est le produit des limites).

En mettant cela bout à bout, on trouve ainsi que :

\begin{array}{cl}  \displaystyle \lim_{n \to +\infty} \frac{n(n-1)(n-2)\cdots (n-k+1)}{n^k} \frac{\lambda^k}{k!} \left(1- \frac{\lambda}{n} \right)^n \left(1- \frac{\lambda}{n} \right)^{-k}=& \displaystyle 1\times \frac{\lambda^k}{k!} \times \text{e}^{-\lambda} \times 1 \\  &  \end{array}

Nous retrouvons donc bien la formule annoncée au début de l’article:

P(X=k) = \dfrac{\lambda^k \text{e}^{-\lambda}}{k!}

Mais au fait, c’est quoi la différence entre un bon pêcheur et un mauvais pêcheur ?

Notes

Publié dans Probabilités | Marqué avec , , , , , | 7 commentaires

Le théorème de Kuratowski

Choisissez une partie quelconque du plan. A cette partie, on peut lui appliquer deux types d’opérations:

  • Soit on prend son complémentaire;
  • Soit on prend sa fermeture (au sens topologique du terme). Pour ceux qui ne sauraient pas vraiment ce que représente la fermeture d’un ensemble, considérez que cela revient à ajouter son bord à l’ensemble de départ.
lolilolol

Prendre la fermeture d’un ensemble revient à lui ajouter son bord.

Maintenant, appliquez ces opérations autant de fois que vous le souhaitez, dans l’ordre que vous voulez sur la partie du plan que vous voulez. Selon vous, combien d’ensembles différents pourra-t-on obtenir au maximum avec ce procédé ?

Disque rayé…

Pour bien comprendre le problème, voici un exemple. Dans le plan \mathbb{R}^2, on considère le disque ouvert D de centre (0,0) et de rayon 1, c’est-à-dire l’ensemble des points (x,y) tels que x^2+y^2 <1.

theoreme_Kuratowski_disque_ouvertDe ce disque, on peut commencer par en prendre son complémentaire:

theoreme_Kuratowski_complementaire_du_disque_ouvertOn peut aussi en prendre sa fermeture:

theoreme_Kuratowski_fermeture_du_disque_ouvertOn peut itérer ce processus, et à partir de chaque nouvel ensemble obtenu, on prend soit le complémentaire, soit la fermeture. Voici ci-dessous tous les ensembles qu’on obtient lorsqu’on applique ces deux opérations de fermeture (F) et de complémentaire (C) à notre disque initial:

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l'ensemble.

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l’ensemble.

Vous voyez qu’à partir d’un certain moment, on retombe sur des ensembles que l’on déjà vus et il est donc inutile d’aller plus loin. Ainsi, en prenant autant de fois que l’on veut la fermeture et le complémentaire de notre disque de départ, nous avons obtenu 4 ensembles différents.

Peut-on faire mieux que 4 ? Car ce que nous avons fait pour un disque, vous comprenez bien que nous pouvons le faire pour n’importe quelle partie du plan, aussi biscornue et bizarre soit-elle. Essayez par vous-même avec d’autres parties du plan avant de lire la suite (par exemple, avec un triangle plein dont deux des côtés sont exclus, ou bien avec l’ensemble de Cantor pourquoi pas !)

Le théorème de Kuratowski

Le théorème qui va nous intéresser dans cet article, est le théorème démontré par le mathématicien polonais Kuratowski en 1922 qui dit que:

En prenant autant de fois que l’on veut la fermeture et le complémentaire d’une partie A quelconque, on ne peut obtenir que 14 ensembles différents au plus.

Vous pouvez donc partir de n’importe quel ensemble au départ, vous ne pourrez jamais créer plus de 14 ensembles différents juste en prenant la fermeture et le complémentaire !

Au fait, pourquoi 14 ? D’où peut bien sortir ce 14 ?! Lisez attentivement la suite pour comprendre car nous allons démontrer ce théorème.

Quelques notations

Pour dire qu’on prend le complémentaire d’une partie A, on notera C(A) et pour dire qu’on en prend la fermeture, on notera F(A). Puis, pour dire qu’on prend d’abord le complémentaire de cette partie puis sa fermeture, on notera FC(A)  — un peu à la manière de la notation de la composée de deux fonctions.

D’ailleurs, cette notation FC(A) est adaptée à  la langue française, car lorsque l’ont dit « Je prends la fermeture du complémentaire de A », on prend bien d’abord le complémentaire et ensuite la fermeture ! (qui eut crû que le Français utilisait la même structure que celle de la notation d’une composée de fonctions ?).

Enfin, pour alléger les notations, au lieu de noter FC(A), on notera plus simplement FC.

Bref, tout ça pour dire que si j’écris CFCF, ça veut dire: « Je prends la fermeture, puis je prends le complémentaire, puis je prends la fermeture, puis je prends le complémentaire ». Dans cet ordre !

Crise des monoïdes

Nous allons à présent nous intéresser à toutes les combinaisons possibles que l’on peut former avec F et C (en termes plus savants, nous allons étudier le monoïde engendré par F et C). Par exemple, on peut commencer par prendre 10 fois le complémentaire, puis 8 fois la fermeture, puis 34 fois le complémentaire, puis 21 fois la fermeture puis 13 fois le complémentaire. On notera cette suite d’opérations par:

C^{13}F^{21}C^{34}F^{8}C^{10}

Plus généralement, une suite de fermetures et de complémentaires, qu’on appellera opération complexe dans la suite de l’article, peut être représentée par l’une des 4 formes suivantes:

\begin{array}{c}  C^{n_1} F^{n_2} \cdots C^{n_k}\\  ou \\  C^{n_1} F^{n_2} \cdots F^{n_k}\\  ou \\  F^{n_1} C^{n_2} \cdots C^{n_k}\\  ou\\  F^{n_1} C^{n_2} \cdots F^{n_k}\\  \end{array}

Première réduction

Vous aurez sans doute constaté les deux faits suivants:

  • Prendre deux fois de suite le complémentaire revient à ne rien faire;
  • Prendre deux fois de suite la fermeture revient à prendre une seule fois la fermeture.

Ces propriétés sont faciles à comprendre: quand on prend le complémentaire du complémentaire, on revient au point de départ. De même, si j’ajoute le bord alors que je viens de l’ajouter, je ne fais rien de plus !

Si on note Id l’opération qui consiste à ne rien changer, on peut traduire les deux faits précédents de la façon suivante: C² = Id et F²=F.

Cette première réduction montre qu’une opération complexe peut s’écrire comme une simple suite de C et de F. Par exemple, C^{13} = C et C^{34}=Id. De même, F^{21}=F et F^{8}=F. Ainsi,

C^{13}F^{21}C^{34}F^{8}C^{10} = C F Id F Id = CFF= CF

Une opération complexe n’est donc, après réduction, qu’une suite de C et de F qui alternent successivement !

Seconde réduction

On peut montrer que FCFCFCF=FCF. J’ai mis la démonstration de ce fait dans le fichier suivant:

Démonstration

Cette propriété fait bien comprendre que la longueur d’une opération complexe (qui est une suite de F et de C qui alternent comme on l’a vu) ne peut pas dépasser 7 termes après réduction (7 étant la longueur de l’opération complexe FCFCFCF).

Fin de la démonstration

A présent, nous allons utiliser les deux réductions précédentes pour montrer qu’il n’y a que 14 opérations complexes possibles. Le plus simple pour le voir est de faire le graphe de Cayley du monoïde engendré par F et C (ça y est je sors les grands termes !). Il s’agit du graphe obtenu en partant de Id et qui, à chaque étape, ajoute F ou C. Chaque fois qu’on prend le complémentaire, j’ai mis une flèche rouge et chaque fois qu’on prend la fermeture, j’ai mis une flèche bleue:theoreme_Kuratowski_graphe_de_CayleyLa flèche en pointillés de gauche exprime l’égalité FCFCFCF=FCF démontrée plus haut. La flèche en pointillés de droite vient du fait que F(CFCFCFC) = (FCFCFCF)C=(FCF)C=FCFC.

Au final, vous voyez qu’il n’y a que 14 sommets sur ce graphe, donc au plus 14 ensembles différents. CQFD.

Peut-on descendre en dessous de 14 ?

Pour être tout à fait complet, il faudrait se poser la question de savoir si la borne de 14 est optimale, c’est-à-dire s’il existe une partie qui, quand elle est soumise aux différentes opérations de fermeture et de complémentaire donne effectivement 14 ensembles différents. Si vous vous souvenez de notre exemple du disque, nous n’avions obtenu que 4 ensembles distincts, ce qui était loin du compte !

En fait, il existe bel et bien une partie qui donne 14 ensembles différents: il s’agit de la partie A de \mathbb{R} donnée par:

A = ]0;1[ \bigcup ]1;2[ \bigcup \{ 3\} \bigcup \left( [4;5] \bigcap \mathbb{Q} \right)

Voici les 14 ensembles obtenus en partant de A (rappelons que \mathbb{Q} est dense dans \mathbb{R}…):

theoreme_Kuratowski_14_ensembles_differentsComme vous le constatez, il y a bien 14 ensembles différents !

Notes:

Publié dans Topologie | Marqué avec , , , , , , | Laisser un commentaire

Arnaquez vos amis à Pile ou Face

Avertissement: Blogdemaths décline toute responsabilité en cas de perte d’argent ayant été entrainée par la lecture de cet article. En poursuivant la lecture, vous acceptez qu’il est possible de perdre à un jeu de hasard, même quand les probabilités sont en votre faveur. Vous acceptez aussi de me faire don de la moitié de votre fortune personnelle.

Avant de commencer, j’aimerais mettre les choses au clair concernant le jeu de Pile ou Face: si vous lancez une pièce de monnaie bien équilibrée (non truquée, non pipée, tout ce que vous voulez), vous aurez toujours une chance sur deux de deviner le côté de la pièce qui sortira. Tout le monde sait ça. Alors comment donc arnaquer vos amis en jouant à Pile ou Face si on ne peut, de toutes façons, jamais changer la probabilité d’apparition de chacune des faces ?

Ce que tout le monde ne sait pas, c’est qu’il existe une variante de « Pile ou Face » qui, elle, est inéquitable. Et c’est ce que je vais vous montrer ci-dessous…

Place au jeu !

Le jeu auquel nous allons nous livrer est un jeu dans lequel deux joueurs vont s’affronter et qui va consister à lancer plusieurs fois de suite une pièce de monnaie. Avant la partie, chacun des joueurs choisit une séquence de 3 résultats (chaque résultat étant Pile ou Face). Puis, on lance la pièce de monnaie autant de fois qu’il le faut (en notant à chaque fois le résultat) jusqu’à ce qu’une des deux séquences apparaisse.

Par exemple, avant de commencer à lancer la pièce, le joueur 1 choisit la séquence PFP (Pile-Face-Pile) et le joueur 2 choisit la séquence FPP (Face-Pile-Pile).  On lance ensuite la pièce plusieurs fois de suite et voici les issues obtenues successivement:

F P F F P F F F P P

Comme vous le voyez, cette partie a duré 10 lancers et la première séquence sortie est celle du joueur 2, qui est alors déclaré vainqueur. Bien sûr, vous pouvez pimenter la partie en décidant de mettre une petite (ou grosse) mise de départ, le gagnant remportant le pot…

Il y a 2^3=8 choix possibles de séquences pour chaque joueur. A priori, le choixx des séquences est aléatoire, donc les deux joueurs devraient être censés avoir la même chance de gagner… en tout cas, c’est ce que l’intuition nous laisse penser. Mais nous allons voir que ce n’est pas le cas (d’où l’arnaque !), et surtout, nous allons essayer de comprendre pourquoi.

Une première simulation

Pour bien comprendre ce jeu et comprendre pourquoi notre intuition est mise en défaut, la première chose que nous allons faire est une simulation de partie.

Par exemple, on imagine que votre adversaire choisisse la séquence FFP et que vous choisissiez la séquence PFF. On imagine aussi que vous et votre adversaire ne soyez pas pressés et que vous décidiez de faire 10 000 parties (!). Précision: pour chaque partie, votre adversaire aura toujours la séquence FFP, et vous la séquence PFF.

J’ai simulé cette situation à l’aide d’un programme et voici les résultats obtenus à la fin des 10 000 parties:

Pile_ou_Face_FFP_contre_PFF

Lors de cette simulation, votre adversaire a gagné 2526 fois et vous avez gagné 7474 fois. Autant dire que vous l’avez mis minable.

Vous constatez avec surprise (et avidité) que vous gagnez très majoritairement – à vue de nez, dans environ 3 cas sur 4. Puisque nous avons fait un grand nombre de simulations, la loi des grands nombres nous permet de penser que votre probabilité de gagner est de 3/4, donc bien supérieure à une chance sur deux !

Simulations de tous les choix possibles de l’adversaire

Vous allez peut-être me dire que si mon adversaire avait choisit une autre séquence que FFP, alors il aurait peut-être pu gagner. Nous allons donc simuler les 8 cas de figure possibles, correspondant aux huit séquences que votre adversaire peut choisir au départ: FFF, FFP, FPF, FPP, PFF, PFP, PPF, PPP. Et pour chaque choix de votre adversaire, j’ai mis un choix très précis de séquence qui vous fera gagner…

Voici les simulations (cette fois-ci, j’ai mis les fréquences de victoires, plutôt que les effectifs). Chaque diagramme correspond à une simulation de 10 000 parties:

Pile_ou_Face_tous_les_cas_possibles_de_sequencesVous voyez donc que, quelque soit le choix de séquence de votre adversaire, il existe une séquence qui peut vous faire gagner plus souvent en moyenne !

La stratégie gagnante

Voici la stratégie à suivre pour gagner à ce jeu (avec au passage un très joli moyen mnémotechnique):

  1. Attendez que votre adversaire choisisse d’abord une séquence. C’est important car votre choix optimal dépendra du choix de l’adversaire.
  2. Si votre adversaire choisit la séquence A-B-C (où A, B et C sont Pile ou Face), choisissez la séquence (non B)-A-B non B est la face opposée de la face B.

Par exemple, si votre adversaire choisit la séquence PFP, choisissez la séquence (non F)PF c’est-à-dire PPF.

Si vous choisissez votre séquence exactement comme indiqué, alors vous êtes assuré d’avoir une probabilité de gain supérieure à celle de votre adversaire. Voici plus précisément le tableau des probabilités:Pile_ou_Face_Tableau_des_probabilitesComme vous le voyez, votre probabilité de gagner peut aller de 2 chances sur 3 jusqu’à 7 chances sur 8 si votre adversaire a le malheur de choisir une séquence peu gagnante comme FFF… Il nous reste maintenant à comprendre pourquoi certaines séquences battent d’autres séquences et voir comment on peut calculer ces probabilités.

Analyse de deux cas

Nous allons étudier deux exemples: un premier cas dans lequel nous ne ferons aucun calcul mais qui nous servira à comprendre pourquoi une séquence peut l’emporter sur l’autre; et un deuxième cas où nous verrons comment on peut calculer les probabilités de gagner que nous avons données plus haut.

Exemple 1: Votre adversaire choisit FFF et vous choisissez PFF

Commençons par une remarque évidente: pour que votre adversaire gagne, il faut qu’à un moment de la partie Face soit tiré (F) puis que Face soit encore tiré juste après (FF) et enfin que Face soit encore tiré (FFF). A contrario, pour que vous gagniez, il faut qu’à un moment de la partie, Pile soit tiré (P) puis que ce soit Face qui sorte (PF) et enfin que Face soit encore tiré juste après (PFF). Une façon très commode de représenter cela est d’utiliser ce qu’on appelle un graphe d’une chaine de Markov:Pile_ou_Face_graphe_markov_FFF_contre_PFFIci, chaque flèche représente un lancer. En fonction de l’endroit où pointe la flèche, on devine si ce lancer était Pile ou Face.

Ce graphe montre clairement l’asymétrie des séquences. On remarque en particulier qu’à partir du moment où un seul Pile est sorti, on sort définitivement de la branche du bas et donc votre adversaire n’a plus aucune chance de gagner. C’est bien cela qui donne un net avantage à la séquence PFF par rapport à la séquence FFF.

Exemple 2: Votre adversaire choisit PFF et vous choisissez PPF

Là encore, on peut tracer le graphe de Markov associé à cette situation:Pile_ou_Face_graphe_markov_PFF_contre_PPF

Nous voyons qu’une fois la séquence ’Pile-Pile’ sortie, votre adversaire n’a plus aucune chance de gagner, ce qui vous donne une plus grande probabilité de gain. Mais de combien exactement est cette probabilité ? C’est ce que nous allons calculer. Pour cela, nous allons d’abord compléter le graphe précédent:Pile_ou_Face_graphe_markov_PFF_contre_PPF_avec_probabilites_de_transition

Ce graphe doit se lire de votre point de vue (et non celui de votre adversaire): le but est d’arriver au nœud PPF. A côté de chaque nœud, on a placé une lettre (p, x, y) ou un nombre (1, 0). Cela correspond à la probabilité d’arriver au nœud PPF sachant qu’on part de ce nœud.

Par exemple, la probabilité de partir du nœud Début et d’arriver au nœud PPF est de p (c’est donc la probabilité que vous gagniez la partie !). Autre exemple, imaginons qu’à un moment de la partie, la séquence PF soit sortie: la probabilité que vous gagniez la partie sachant que cette séquence PF vient d’être tirée est notée y. (Bon, au final,  ne nous servira pas dans cet article mais il devait nous servir pour vous montrer une deuxième méthode de calcul de cette probabilité. Mais comme l’article commence à devenir trop long…)

Vous remarquez qu’à côté du nœud PPF nous avons mis 1, car une fois cette séquence sortie, vous êtes sûr d’avoir gagné la partie puisque vous avez gagné la partie ! (J’écris des choses très connes sur ce blog des fois…). Je pense que vous avez maintenant compris pourquoi il y a 0 à côté du nœud PFF…

Passons maintenant au calcul de votre probabilité de gagner la partie, c’est-à-dire au calcul de p. On va utiliser les mêmes règles que pour les arbres de probabilités (dont vous avez sans doute plus l’habitude).

Tout d’abord, il est clair que p=x car, comme on le voit sur le graphe, la partie commence réellement à partir du moment où on a rejoint le noeud P.

Pour calculer x, la formule des probabilités totales nous dit qu’il faut faire la somme des probabilités de tous les chemins qui vont de P à PPF. Et comme pour les arbres de probabilités, la probabilité d’un de ces chemins est le produit des probabilités de transition (qui sont toutes de \frac{1}{2} ici).

Un chemin allant de P à PPF se décompose (dans l’ordre) en:

  1. Un certain nombre de fois n le cycle P-PF, qui a pour probabilité (\frac{1}{2} \times \frac{1}{2})^n = \frac{1}{4^n}.
  2. Une fois le chemin P-PP, qui a pour probabilité \frac{1}{2}.
  3. Un certain nombre de fois m la boucle PP-PP, qui a pour probabilité \frac{1}{2^m}
  4. Une fois le chemin final PP-PPF (que j’appelle personnellement le chemin de la gloire) qui a pour probabilité \frac{1}{2}.

Un tel chemin a donc pour probabilité:

\displaystyle \dfrac{1}{4^n} \times \dfrac{1}{2} \times \dfrac{1}{2^m} \times \dfrac{1}{2} = \dfrac{1}{4} \times \dfrac{1}{4^n} \times \dfrac{1}{2^m}

Au final, pour trouver x (et donc p), il faut faire la somme des toutes ces probabilités (c’est bien la formule des probabilités totales !):

\displaystyle p = x = \sum_{n \geq 0, m\geq 0} \dfrac{1}{4} \times \dfrac{1}{4^n} \times \dfrac{1}{2^m} = \dfrac{1}{4} \sum_{n \geq 0} \dfrac{1}{4^n}\sum_{m \geq 0} \dfrac{1}{2^n}

 On reconnaît de gentilles séries géométriques qu’on sait facilement calculer. On a donc

p = \dfrac{1}{4} \times \dfrac{4}{3} \times 2 = \dfrac{2}{3}

Nous retrouvons ainsi un résultat que nous avions vu dans le tableau des probabilités plus haut: si votre adversaire joue PFF et que vous jouez PPF alors vous avez 2 chances sur 3 de gagner.

Une variante pour jouer en pratique

Nous l’avons vu, quelque soit le choix de votre adversaire, vous disposez d’un choix de séquence qui vous donne une probabilité plus grande de gagner. Mais cela reste une probabilité et si vous ne jouez qu’une partie, votre adversaire peut toujours gagner.

Afin d’optimiser vos gains, il serait bien de jouer plusieurs parties de suite et de s’appuyer sur la loi des grands nombres (qui dit que votre fréquence de gain tend à se rapprocher de votre probabilité de gagner… songez aux simulations de 10 000 parties qu’on a vues plus haut). Donc, le plus de parties vous ferez, le mieux ce sera pour vous !

Cependant, en pratique, lancer une pièce de monnaie des dizaines de fois de suite peut se révéler fastidieux… Alors pourquoi ne pas utiliser des cartes à jouer au lieu d’une pièce ? C’est ce qu’ont imaginé deux mathématiciens, Yutaka Nishiyama et Steve Humble.

Prenez donc un paquet de 52 cartes. Chaque joueur choisit une séquence, non pas de Pile ou Face, mais de Rouge ou Noir (les couleurs des cartes !). Retournez chaque carte une à une jusqu’à ce qu’une séquence apparaisse. Et tant qu’il reste des cartes dans le paquet, continuez de les retourner !

Cette variante avec des cartes permet de jouer en moyenne environ 7 parties avant d’avoir épuisé toutes les cartes, ce qui, comme on l’a dit plus haut, est avantageux pour le joueur qui a choisi une séquence qui possède une plus grande probabilité de gagner. Mais il y a mieux: cette variante n’étant pas exactement identique à un lancer de pièce (car par exemple, à un moment donné du jeu, il peut rester dans le paquet plus de cartes Rouges que de cartes Noires ou inversement), on peut montrer en fait que les probabilités de gain sont plus grandes que celles obtenues pour le jeu avec des pièces ! (voir référence à la fin de l’article).

Si tu veux devenir riche, commence donc par prendre un paquet de cartes !

Références:

Publié dans Probabilités | Marqué avec , , , , , | 6 commentaires

2015, année palindromique

Une nouvelle année commence, et qui dit nouvelle année, dit nouvelles propriétés ! Étonnamment, les articles que j’avais écrit en 2013 et 2014 sont encore valables pour 2015. Mais j’ai pris la résolution d’arrêter d’être fainéant cette année, et voici donc un autre article, spécialement consacré à 2015.

Bob

Vous connaissez le rapport entre le groupe ABBA et le XANAX ? Non, la réponse n’est pas qu’il faut être drogué pour pouvoir apprécier un groupe de musique suédois (quoi que…). Le lien entre les deux est que ces deux termes sont ce qu’on appelle des palindromes, c’est-à-dire des mots qui se lisent de droite à gauche ou de gauche à droite de la même façon.

En mathématiques, la notion de nombre palindrome est similaire: ce sont les nombres qui, quand ils sont lus dans un sens ou dans l’autre, ne changent pas. Par exemple, 121 et 9009 sont des palindromes.

Quel est le lien avec 2015 dans tout ça ? Car il est clair que ce n’est pas un palindrome. Mais quelque part dans l’horloge de votre ordinateur, le nombre 2015 est stocké sous forme d’un nombre binaire (avec des 0 et des 1). Et l’écriture de 2015 en binaire est:

11111011111

qui lui est un palindrome ! Je vous propose dans cet article de voir s’il y a eu (et s’il y aura) beaucoup d’années qui sont des palindromes en binaire, ce qui sera un prétexte pour faire un peu (beaucoup) de dénombrement.

Compter les palindromes à 11 et 12 chiffres

Pour savoir s’il y eu beaucoup d’années palindromes en binaire avant 2015 (et plus généralement, la proportion de nombres qui sont des palindromes en binaire), nous allons commencer par dénombrer tous les palindromes binaires à n chiffres, où n est un entier quelconque. Par exemple, 2015 possède 11 chiffres en binaire; commençons donc par trouver combien il y a de palindromes en binaire à 11 chiffres.

Si un nombre possède 11 chiffres exactement, le 1er chiffre est forcément 1 (il ne peut valoir 0, sinon il serait considéré comme un nombre à 10 chiffres !). Et puisque c’est un palindrome, le dernier chiffre sera aussi un 1. Un palindrome à 11 chiffres est donc de la forme:palindrome_a_11_chiffresVous voyez qu’on peut choisir librement les 2ème, 3ème, 4ème et 5ème chiffres (représentés par les lettres a, b, c et d). Puisque il y a 2 possibilités pour chacun de ces chiffres (0 ou 1 !), cela donne 2^4 possibilités. Une fois choisis, on n’aura pas le choix pour les 10ème, 9ème, 8ème et 7ème chiffres puisqu’il faut qu’il y ait symétrie ! Il reste le chiffre du milieu, qu’on peut choisir librement, ce qui donne deux possibilités supplémentaires.palindrome_a_11_chiffres_dénombrementAinsi, il y a 2^4 \times 2 = 32 nombres de 11 chiffres en binaire qui sont des palindromes.

Et pour les nombres à 12 chiffres ? Comme 12 est pair, il n’y aura pas de chiffre isolé au milieu; comment fait-on alors ? En fait, pour un nombre à 12 chiffres en binaire, le raisonnement est quasiment le même. Un palindrome à 12 chiffres est de la forme:palindrome_a_12_chiffresOn peut choisir librement les 2ème, 3ème, 4ème, 5ème et 6ème chiffres, ce qui donne 2^5=32 possibilités. A partir de là, il n’y a plus guère de choix possible pour les 7ème, 8ème, 9ème, 10ème, 11ème chiffres car ils doivent être respectivement les mêmes que les 6ème, 5ème, 4ème, 3ème et 2ème chiffres.palindrome_a_12_chiffres_dénombrementAu final, cela fait 32 nombres à 12 chiffres en binaire qui sont des palindromes.

On voit au passage qu’il y a autant de palindromes à 11 chiffres que de palindromes à 12 chiffres en binaire !

Compter les palindromes dans le cas général

On va compter le nombre d’entiers à n>0 chiffres en binaire qui sont des palindromes. Comme dans l’exemple précédent, on distingue deux cas:

1) n est un nombre pair: Dans ce cas, un nombre en binaire à n chiffres se compose de \frac{n}{2} premiers chiffres et de \frac{n}{2} derniers chiffres. Ces derniers étant entièrement déterminés par les \frac{n}{2} premiers. On sait que le premier chiffre est un 1. Il reste donc à choisir \frac{n}{2} - 1 chiffres ce qui donne 2^{\frac{n}{2} - 1} possibilités.

palindrome_n_chiffres_pair2) n est un nombre impair: Dans ce cas, il y a \frac{n-1}{2} premiers chiffres, puis un chiffre du milieu puis \frac{n-1}{2} derniers chiffres. Comme toujours, le premier chiffre est un 1. Ensuite, on peut choisir librement les \frac{n-1}{2} - 1 chiffres suivants, ainsi que le chiffre du milieu.

palindrome_n_chiffres_impairCela donne 2^{ \frac{n-1}{2} - 1} \times 2 = 2^{\frac{n-1}{2}} possibilités.

Résumons: si on note P(n) le nombre d’entiers à n chiffres en binaire qui sont des palindromes (en binaire) alors:

P(n) = \begin{cases} 2^{\frac{n}{2}} & \text{si n pair} \\ 2^{\frac{n-1}{2}} & \text{si n impair} \end{cases}

Nombre de palindromes

En incluant 2015, il y a eu 93 années depuis l’an 1 qui sont des palindromes en binaire. Les voici:

1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 85, 93, 99, 107, 119, 127, 129, 153, 165, 189, 195, 219, 231, 255, 257, 273, 297, 313, 325, 341, 365, 381, 387, 403, 427, 443, 455, 471, 495, 511, 513, 561, 585, 633, 645, 693, 717, 765, 771, 819, 843, 891, 903, 951, 975, 1023, 1025, 1057, 1105, 1137, 1161, 1193, 1241, 1273, 1285, 1317, 1365, 1397, 1421, 1453, 1501, 1533, 1539, 1571, 1619, 1651, 1675, 1707, 1755, 1787, 1799, 1831, 1879, 1911, 1935, 1967, 2015

Pour les trouver, j’ai écrit un petit programme mais il serait plus intéressant d’avoir une formule qui donne le nombre de palindromes qu’il y a eu avant telle ou telle année…. malheureusement, une telle formule n’est pas forcément facile à déterminer.  On va donc s’en passer et nous allons plutôt essayer de trouver une estimation du nombre de palindrome inférieurs à un nombre donné.

Si x un entier (qui représente donc une année), on note N(x) le nombre d’entiers positifs non nuls qui sont inférieurs ou égaux à x et qui sont des palindromes en binaire. Par exemple, on vient de voir que N(2015)=93 car il y eu 93 années avant 2015 qui étaient des palindromes en binaire. Voici le graphe de la fonction N(x) pour x compris entre 1 et 2015:

Fonction_N(x)_2015

Vu la gueule du graphe, vous comprenez mieux pourquoi on ne va pas chercher une formule exacte pour N(x) !

 

Comme j’ai dit, notre but sera d’essayer d’estimer N(x) pour voir si, à l’avenir, il y aura beaucoup d’années qui sont des palindromes en binaires.

Certes, trouver une formule pour N(x) n’est pas chose aisée, mais il y a quand même des cas simples où il existe une formule exacte: par exemple dans le cas où x est de la forme 2^{n}. En effet, 2^{n} est le plus petit nombre à n chiffres en binaire et n’est pas un palindrome donc, pour trouver N(2^n), il suffit d’additionner le nombre de palindromes à n-1 chiffres avec le nombre de palindromes à n-2 chiffres avec le nombres de palindromes à n-3 chiffres, etc. Mais nous avons déjà vu combien il y a de palindromes à k chiffres ! Je ne mets pas les calculs, mais voici la formule (vous pourrez trouver la démonstration de cela à la fin de l’article):

N(2^n) = \begin{cases} 2 (2^{\frac{n}{2}} - 1) & \text{si } n \text{ est pair} \\ 3 \times 2^{\frac{n-1}{2}} - 2 & \text{si } n \text{ est impair} \end{cases}

 

Passons à l’estimation de N(x) pour x un entier quelconque. Puisque tout entier peut être encadré par deux puissances de 2 successives, il existe un entier n tel que

2^n \leq x < 2^{n+1}

Et comme la fonction N est croissante (le nombre de palindromes ne peut diminuer au fur et à mesure des années !), on a

N(2^n) \leq N(x) \leq N(2^{n+1})

Selon que n est pair ou impair, on a donc soit:

2(2^{\frac{n}{2}}-1) \leq N(x) \leq 3 \times 2^{\frac{n}{2}} - 2

soit

3 \times 2^{\frac{n-1}{2}} - 2 \leq N(x) \leq 2(2^{\frac{n+1}{2}}-1)

Ainsi la proportion d’années qui sont des palindromes en base 2, à savoir \frac{N(x)}{x} est encadrée par

\dfrac{2(2^{\frac{n}{2}}-1)}{2^{n+1}} \leq \dfrac{N(x)}{x} \leq \dfrac{3 \times 2^{\frac{n}{2}} - 2}{2^n}

ou par

\dfrac{3 \times 2^{\frac{n-1}{2}} - 2}{2^{n+1}} \leq \dfrac{N(x)}{x} \leq \dfrac{2(2^{\frac{n+1}{2}}-1)}{2^n}

Conclusion

A partir  de là, on voit que les suites qui encadrent \frac{N(x)}{x} tendent vers 0 quand n tend vers l’infini (plus précisément, si x possède n chiffres en binaire alors N(x)/x est de l’ordre de 2^{-\frac{n}{2}}), ce qui signifie que plus x est grand, et plus le nombre de palindromes en binaire tend à se raréfier ! Cela se voit très bien sur le graphique suivant:

Fonction_N(x)Donc, même si vous n’avez pas compris tous les calculs, ce qu’il faut retenir est qu’il y a peu d’années qui sont des palindromes en binaire et donc 2015 est une année remarquable !

Mais ce n’est pas tout ! Il y a mieux !

Nous avons vu que 2015 est un palindrome en base 2. C’est aussi un palindrome en base 38, 64, 154, 402 et 2014. Une curiosité supplémentaire est la suivante: la décomposition en produits de facteurs premiers de 2015 est

2015 = 13 x 5 x 31

Et vous reconnaissez une sorte de palindrome ! Amusant, non ? Cela vient du fait que 13 et 31 sont ce qu’on appelle des Reimerp c’est-à-dire que ce sont des nombres premiers qui sont encore premiers quand on les « renverse ». D’autres exemples sont 37 et 73 ou bien 113 et 311.

Bref, ça fait beaucoup de belles choses pour un simple nombre. Bonne année 2015 à tous !

Note:

Voici la démonstration pour la formule de N(2^n):

Calcul de N(2^n)

Publié dans Dénombrement, Nombres | Marqué avec , , , , , , | 4 commentaires