[FAQ] fr.sci.maths - partie 2/3
medtib@alussinan.org (Mehdi Tibouchi)
Archive-Name: fr/maths/maths-faq-2
Last modified: 2006-11-11
Version 2.12
#####################################################
# #
# FAQ fr.sci.maths (partie 2/3) #
# #
#####################################################
fr.sci.maths est un groupe de discussion destiné à recueillir les
discussions en français concernant les mathématiques.
Ce document rassemble les questions qui ont été fréquemment posées dans
ce forum.
Remarque sur la notation : le signe de multiplication utilisé ici est
l'astérisque *, comme souvent en informatique.
La version texte de ce document a été divisée en trois parties, afin de
faciliter sa difusion sur les forums francophones.
On trouvera, dans cette partie, les chapitres III et IV.
Pour les chapitres I à III, se referer au document intitulé :
"[FAQ] fr.sci.maths - partie 1/3".
Pour les chapitre VI à VII, se referer au document intitulé :
"[FAQ] fr.sci.maths - partie 3/3".
Table des matières :
I Contradictions.
1. Est-ce que 0,9999... = 1 ?
2. J'ai réussi à montrer que 2=1.
3. Zéro puissance zéro égal un (0^0 = 1).
II Démonstrations.
1. Le petit théorème de Fermat.
2. ab et a+b premiers entre eux.
3. Irrationalité de la racine carrée de 2.
4. Irrationalité de la racine d'un nombre premier.
5. Irrationalité de e.
6. Transcendance de e.
7. Somme des puissances des premiers entiers.
8. Les nombres et les polynômes de Bernoulli.
9. Par combien de zéros le nombre 1998! se termine-t-il ?
10. Expression par radicaux des racines d'un polynôme de degré n.
III Géométrie.
1. Problème de la chèvre.
2. Problème (dit) de Napoléon.
-+- Début de la deuxième partie -+-
IV Énigmes.
1. Pièces et balance, traduit par Vincent Lefèvre.
2. Les âges du capitaine.
3. Quel est le nombre qui continue cette suite : 2, 12, 1112,...
4. Probabilité que 2 personnes soient nées le même jour.
5. Somme et produit de deux entiers.
6. Les deux échelles.
7. La cuve de vin.
V Questions fondamentales.
1. Les nombres premiers.
2. Pi.
3. Le grand théorème de Fermat.
4. La conjecture de Syracuse.
5. Les cardinaux des ensembles infinis - Partie I.
6. Les cardinaux des ensembles infinis - Partie II.
7. Qu'est-ce que le nombre e ?
-+- Début de la troisième partie -+-
VI Mathématiques et Ordinateur.
1. Comment écrire des formules mathématiques dans les News ?
2. Logiciels de mathématiques.
3. L'algorithme de CORDIC sur les calculatrices.
VII Conclusion.
1. Références.
2. Remerciements.
========================================================================
Changements intervenus depuis la version précédente :
- Mises à jour ou suppression des liens morts.
- Rééquilibrage des trois parties pour tenir dans la limite de 64ko.
- Révision du paragraphe I.3.
- Suppression du paragraphe VI.1 de Frédéric Bastok (double-emploi
avec le document posté chaque quinzaine).
- Réécriture du paragraphe VI.2 (maintenant VI.1), qui était dépassé
et étrangement structuré.
- Autres détails cosmétiques.
Les changements sont précédés du caractère : |
========================================================================
III Problèmes de Géométrie.
=======================
1. Problème de la chèvre.
----------------------
Problème
Une chèvre est attachée par une corde de longueur l à un pieu fixé à
un point A de la circonférence d'un enclos circulaire C de centre O
et de rayon R.
Trouver l en fonction de R pour qu'elle puisse brouter au maximum la
moitié de l'herbe de l'enclos.
Une solution :
On trace le cercle C' de centre A et de rayon l qui coupe le
cercle C en H et K. J est le point diamétralement opposé à A sur le
cercle C, et P est la projection orthogonale de O sur (AH).
Pour obtenir l'aire S commune aux deux cercles, on additionne l'aire
S1 du secteur AHK du cercle C', l'aire S2 du secteur OHK du
cercle C, et on soustrait l'aire S3 du quadrilatère AHOK (qui serait
comptée 2 fois sinon).
On prend comme inconnue l'angle OAH = x en radians.
On a : AK = AJ * cos x (dans le triangle rectangle AKJ)
d'où l = 2*R*cos x
S1 = (1/2)*l^2*(2*x) = x*l^2 = 4*R^2*x*(cos x)^2
Le triangle OAH est isocèle de sommet O, donc AOH = Pi - 2*x et
S2 = (1/2)*R^2*2(Pi-2*x) = R^2 *(Pi-2*x)
S3 est deux fois l'aire du triangle OAH :
S3 = 2*OP*PA = 2* R*sin x * R*cos x = 2*R^2 * cos x * sin x
L'équation à résoudre est S = Pi*R^2/2 ou encore
S1 + S2 - S3 = Pi*R^2/2
4*R^2*x*(cos x)^2 + R^2 *(Pi-2*x) - 2*R^2*cos x * sin x = Pi*R^2/2
qui se simplifie en :
2 * sin x * cos x - 2 *x * (2 * (cos x)^2 -1) = Pi/2
En posant y = 2x :
sin y - y * cos y = Pi/2
y est l'angle HAK et est compris entre 0 et Pi.
La fonction f : y --> sin y - y * cos y est continue et strictement
croissante sur [0 , Pi] et f(0) = 0 et f(Pi) = Pi.
L'équation f(y) = Pi/2 admet donc une seule solution dans [0 , Pi].
Avec un outil de calcul, on trouve : y = 1.905695729...
On en déduit ensuite : l/R = 2 * cos(y/2) = 1.158728473...
2. Problème (dit) de Napoléon.
---------------------------
Problème:
On dit que Napoléon aurait trouvé le moyen de déterminer le centre
d'un cercle en utilisant uniquement le compas.
Quelle est la construction ?
Solution :
Cette construction, en 6 étapes, est celle de Napoléon et Mascheroni.
-> D'un point A du cercle , un arc de cercle de rayon quelconque qui
recoupe le cercle en B et C
-> arc de cercle de centre B et de rayon AB
-> arc de cercle de centre C et de rayon AB. Ces deux arcs se coupent
en D.
-> arc de cercle de centre D et de rayon DA qui recoupe le premier arc
(de l'étape 1.) en E et F.
-> arc de cercle de centre E et de rayon EA
-> arc de cercle de centre F et rayon EA. ces deux arcs se coupent en O
Ce classique vient du " dictionnaire des Mathématiques " de F.
Le Lionnais.
Il ne reste plus qu'à prouver que O est bien le centre du cercle...
ce qui n'est pas très difficile.
Sans nier que Napoléon ait quelques qualités de mathématicien,
on pense qu'il avait surtout des amis ou courtisans chez les savants
de l'époque et que l'auteur de cette belle solution est
Lorenzo Mascheroni, auteur d'une "Géométrie du compas" célèbre en
son temps. C'est Monge qui a transmis le " truc " à Napoléon.
========================================================================
IV Énigmes.
=========
1. Pièces et balance.
------------------
Traduction de logic/weighing/balance des archives de rec.puzzles.
Problème
On vous donne 12 pièces qui paraissent identiques, dont l'une est
contrefaite et a un poids légèrement différent des autres (vous ne
savez pas si la pièce est plus lourde ou plus légère). On vous donne
une balance de Roberval, qui vous permet de mettre le même nombre de
pièces de chaque côté et d'observer quel côté (s'il y en a un) est
plus lourd. Comment identifier la pièce contrefaite et déterminer si
elle est plus lourde ou plus légère, en 3 pesées?
Solution
Martin Gardner a donné une jolie solution à ce problème.
Supposez que vous avez le droit à P pesées. Écrivez les 3^P chaînes
possibles de longueur P ayant pour caractères " 0 ", " 1 " et " 2 ".
Éliminez les 3 chaînes comportant uniquement un caractère répété
P fois.
Pour chaque chaîne, trouvez le premier caractère différent du
caractère le précédant. Considérez ce couple de caractères. Si ce
couple n'est pas 01, 12 ou 20, éliminez cette chaîne. En d'autres
termes, seules les chaînes de la forme 0*01.*, 1*12.* ou 2*20.*
(expressions rationnelles) sont acceptées.
Il doit vous rester (3^P-3)/2 chaînes. C'est le nombre de pièces
que vous pouvez contrôler en P pesées.
Associez donc chaque pièce à une chaîne de P caractères.
Effectuez P pesées comme suit:
Pour la pesée I, mettez d'un côté toutes les pièces ayant un 0
dans la chaîne en position I, et mettez de l'autre côté toutes
les pièces ayant un 2 dans la chaîne en position I.
Si le côté avec les 0 en position I est plus lourd, écrivez un 0.
Si c'est l'autre côté qui est plus lourd, écrivez un 2. Sinon,
écrivez un 1.
Après P pesées, vous avez écrit une chaîne de P caractères. Si votre
chaîne correspond à une des pièces, alors c'est cette pièce qui est
contrefaite, et elle est plus lourde. Sinon, changez chaque 2 en 0
et chaque 0 en 2 dans votre chaîne. Votre chaîne correspondra alors
à l'une des pièces, et cette pièce est plus légère que les autres.
Notez que si vous devez seulement identifier la pièce contrefaite,
mais pas déterminer si elle est plus lourde ou plus légère, vous
pouvez contrôler (3^P-3)/2+1 pièces. Étiquetez la pièce
supplémentaire par la chaîne contenant uniquement des 1, et utilisez
la méthode ci-dessus.
Notez aussi que vous pouvez contrôler (3^P-3)/2+1 pièces si vous
devez déterminer si la pièce contrefaite est plus lourde ou plus
légère, pourvu que vous ayez une pièce de référence, dont vous savez
qu'elle a le poids correct. Vous faites ceci en étiquetant la pièce
supplémentaire par la chaîne contenant uniquement des 2. Cette
pièce est placée toujours du même côté, et ce plateau contient une
pièce de plus que l'autre. Alors, placez la pièce de référence de
l'autre côté, à chaque pesée.
Il est très facile de prouver que ceci marche, une fois que vous
avez remarqué que la méthode de construction des chaînes assure
qu'à chaque position, 1/3 des chaînes ont un 0, 1/3 ont un 1, et 1/3
ont un 2, et que si une chaîne est dans la liste, alors celle
obtenue en remplaçant chaque 0 par un 2 et chaque 2 par un 0 n'y est
pas.
Si vous savez déjà que la pièce contrefaite est plus lourde (ou plus
légère), vous pouvez contrôler 3^P pièces. Avec P pesées, il ne peut
y avoir que 3^P combinaisons d'équilibre, plateau de gauche plus
lourd et plateau de droite plus lourd.
L'algorithme est dans ce cas:
Partagez les pièces en 3 groupes de même taille... A, B et C. Pesez
A avec B. Si un plateau tombe, il contient la pièce lourde, sinon
cette pièce est dans le groupe C. Si la taille de votre groupe est 1
vous avez trouvé la pièce, sinon faites une recurrence sur le groupe
contenant la pièce lourde.
2. Les âges du capitaine.
----------------------
Le capitaine dit à son fils:
" La cabine n°1 abrite M. DUPONT et ses deux filles. Le produit de leurs
trois âges est 2450 et la somme de leurs trois âges est égale à 4 fois
le tien. Peux-tu trouver les âges des trois passagers ? "
Après un instant, le fils répond: " Non, il me manque une donnée. "
Le capitaine ajoute alors: " Je suis plus âgé que M. DUPONT. "
Le fils du capitaine en déduit aussitôt les trois réponses.
Quel est l'âge du capitaine ? de son fils ? de M. DUPONT ? Quels sont
les âges des deux filles ?
Étant donné que le produit des âges vaut 2450, c'est donc que les âges
des voyageurs sont des diviseurs de 2450.
Or 2450 = 1*2*5*5*7*7 (décomposition en nombres premiers)
On a alors comme âges possibles : 1, 2, 5, 7, 10, 14, 25, 35, 49, 50,
70,
98, 175, 245, 350, 490, 1225, ou 2450.
Il semble absurde de supposer que l'âge d'un des passagers puisse
excéder
174 ans (quoi que...). Ainsi, les âges possibles sont réduits
aux
douze premiers diviseurs.
On a donc qu'un nombre fini de triplets possible :
{98,25,1} , {98,5,5} , {70,35,1} , {70,7,5} , {50,49,1} , {50,7,7},
{49,25,2} ,{49,10,5}... (je ne les écrit pas tous)
Il suffit de faire la somme de chacun des triplets. Or le fils du
capitaine dit ne pas avoir assez d'indices pour trouver avec les sommes,
c'est donc qu'il existe deux sommes identiques. En effet, les triplets
{50,7,7} et {49,10,5} ont la même somme (64 ans).
On en déduit l'âge du fils qui est de 64/4 = 16 ans.
De plus comme le capitaine est plus âgé que M. Dupont, on déduit que M.
Dupont n'a que (sic!) 49 ans De là ses filles ont 10 et 5 ans.
On peut également dire que le capitaine a 50 ans.
Donc
M. Dupont a 49 ans
les deux filles ont 5 et 10 ans
Le capitaine a 50 ans et
Le fils a 16 ans
3. Quel est le nombre qui continue cette suite : 2, 12, 1112...
------------------------------------------------------------
La construction de la suite se fait comme suit : il faut lire à haute
voix les chiffres qui la composent.
On part de " 2 ", on lit un " 2 ", on écrit 12. Puis, on lit un " 1 ",
un " 2 " on écrit 1112. On lit trois " 1 ", un " 2 ", on écrit 3112.
On peut montrer par l'absurde que le nombre de signes distincts qui
composent cette suite se limite aux chiffres 1, 2 et 3.
En effet, supposons qu'à une ligne on trouve le chiffre 4, suivi par
exemple du chiffre 1.
Cela signifie qu'à la ligne précédente, on avait la suite ...1111...
C'est à dire à la ligne d'avant ...11..., que l'on aurait dû traduire
par 21 et non 1111 comme cela a été fait. D'où contradiction.
Il ne peut donc pas y avoir de chiffre supérieur strictement à 3.
Dans la suite, on prendra la convention :
u(0)=2
u(1)=12
u(2)=1112
etc.
Nous nommerons u(n) la valeur trouvée à l'étape n
Cette suite ne peut pas se stabiliser, et même elle tend vers l'infini.
nous savons calculer u(n+1) en fonction de u(n) mais aussi, en toute
logique, u(n-1) en fonction de u(n) (cela paraît évident) qui n'a
qu'une seule valeur possible en fonction de u(n).
Ainsi, supposons qu'il existe m>n tels que u(m) = u(n) alors, d'après
l'observation précédente, u(m-1) = u(n-1) et finalement par une
récurrence évidente, u(m-n) = u(0) = 2.
Or m-n>0 donc d'après la méthode de construction de la liste, u(m-n)
a un nombre pair de chiffres d'où une contradiction.
Donc quels que soient m et n, u(m)<>u(n) ; soit v(n) la suite définie
de la façon suivante :
si il existe k tel que u(k)=n alors v(n)=k. Sinon, v(n)=0
Quel que soit A de N, N=max(v(0)...v(N)) => (n>N => u(n)>A).
Donc u(n) tend vers l'infini.
On peut même montrer que le nombre de 1 diverge :
Je nomme groupe une suite de chiffres faisant partie d'une autre
suite: non décalé (gn) si il commence par un chiffre de rang impair
groupe décalé (gd) si il commence par un chiffre de rang pair
(1232 est un gn de 221232 et un gd de 2221232).
Si X et Y sont deux groupes,
je note X -> Y si une partie de X engendre Y en remontant dans les
termes de la suite (engendrer sera toujours employé dans ce sens).
ex : 1112 (gn) -> 12
2322 (gn) -> 3322
2322 (gd) -> 222
(en effet, les chiffres peuvent être groupés par deux lorsque l'on
remonte dans la suite).
On appellera un doublet, une gn de deux chiffres.
Deux doublets consécutifs ne peuvent pas se terminer par le même
chiffre (on appellera cela une incompatibilité de répétition ir)
le groupe 333 ne peut pas exister car il contient forcément un
doublet 33 et donc engendrera forcément 333 ce qui par récurrence
arrive à une contradiction évidente.
le doublet 33 ne peut donc pas exister. Un groupe contenant un
doublet 33 provoquera une incompatibilité 3 (i3).
Cherchons les gn de quatre chiffres ne contenant pas de 1 et ne
provoquant pas d'incompatibilité (ie: pouvant exister dans la suite):
je ne regarde pas les ir et les i3 triviales :
2223 -> 2233 supposé compatible
2322 -> 3322 supposé compatible
2332 -> 33222 i3 si gn et ir si gd incompatible
3223 -> 22233 supposé compatible
tous les autres sont incompatibles.
Cherchons les gn de huit chiffres ne contenant pas de 1 et ne
provoquant pas d'incompatibilité (il sont constitués des gn de quatre
chiffres compatibles):
22232223 -> 22332233 i3 si gn donc gd
-> 3322233 i3 dans tous les cas
22232322 ir
22233223 -> 223322233 i3 dans tous les cas
23222223 ir
23222322 -> 33223322 i3 si gn donc gd
-> 22233222 i3 si gd et ir si gn
23223223 ir
32232223 -> 222332233 i3 si gd donc gn
-> 223322233 i3 dans tous les cas
32232322 ir
32233223 -> 2223322233 i3 dans tous les cas
Donc tout gn de 8 chiffres contient au moins un 1.
Cette suite tendant vers l'infini, le nombre de gn de 8 chiffres
(même sans recouvrement) tend vers l'infini.
Donc le nombre de 1 aussi.
On constate que la fin du code est stabilisée dès la 6ème itération
pour ses signes finaux.
On note D la transformation telle que u(n+1)=D(u(n)).
On note |X| le nombre de chiffres du groupe X.
Lemme 1 : pour n>=6, u(n) se termine par 222112 si n est pair, et par
322112 si n est impair.
par récurrence. C'est vrai pour n = 6. Soit n > 6, supposons la
propriété vérifiée pour n et montrons la pour n+1. Si n est pair,
u(n) se termine par 222112. Le chiffre précédent, s'il existe, n'est
pas un 2 (puisqu'on n'a pas 4 chiffres identiques consécutifs).
Donc u(n) se termine par un bloc de trois 2, puis un bloc de deux 1,
puis un 2, et donc u(n+1) se termine par 322112 ; n+1 étant impair,
c'est précisément ce qu'on attendait.
Si n est impair, u(n) se termine par 322112. Peu importe si le
chiffre précédent est un 3 ou non, seuls les trois derniers blocs
nous intéressent, et u(n+1) se termine donc par 222112 ; n+1 étant
pair, c'est ce qu'on attendait.
Lemme 2 : soit x(n) la suite définie pour n>=6 par
x(6)=222112, x(7)=322112, x(8)=3222112, x(9)=3322112, x(10)=23222112,
et pour n>=10, x(n+1) est égal à D(x(n)) privé de son premier chiffre.
1. Pour tout n>=6, x(n) est un suffixe de u(n).
2. Pour tout n>=6, x(n) est un suffixe de x(n+2).
3. Pour n>=11, |x(n)| est impair et |x(n+2)| >= |x(n)|+2.
4. Pour tout n, |x(n)| >= n-2.
Preuve :
1. Par récurrence sur n, d'après la définition de u(n).
Noter qu'il est important d'enlever le premier chiffre de D(x(n))
pour construire x(n+1), car le chiffre précédant x(n) dans u(n)
peut être identique au premier chiffre de x(n), ce qui modifie
la longueur du premier bloc ; en revanche, le second chiffre
de D(x(n)), qui indique la nature du premier bloc de x(n),
peut être conservé car il apparaît bien à cet endroit dans u(n+1).
Au passage, on peut noter que ce chiffre est toujours un 2.
2. Par récurrence sur n. On le vérifie à la main pour n < 10.
Pour n>=10, si x(n) est un suffixe de x(n+2), alors x(n+1) est un
suffixe strict de D(x(n+2)), donc c'est un suffixe de x(n+3).
3. Pour n>=11, la longueur de x(n) est impaire par construction.
On montre |x(n+2)| >= |x(n)|+2 par récurrence. C'est vrai pour
n=11 (et même n=9 et n=10). Supposons que |x(n+2)| >= |x(n)|+2
pour un certain n>=11. Comme x(n) est un suffixe de x(n+2), on
peut écrire x(n+2) = wx(n), avec |w| >= 2.
L'avant dernier chiffre de w ne peut être égal au premier chiffre
de x(n), car il s'agit de deux chiffres consécutifs en position
impaire qui sont toujours distincts dans une image par D.
Par conséquent D(x(n+2)) contient au moins un bloc de plus que
D(x(n))
et donc |D(x(n+2))| >= |D(x(n))|+2, d'où |x(n+3)| >= |x(n+1)|+2.
4. Se déduit facilement des valeurs initiales et de 3.
Théorème : pour tout l>=0, il existe un entier n0 tel que pour tout
n > n0, le suffixe de longueur l de u(n) coïncide avec le suffixe de
longueur l de u(n+2).
C'est vrai d'après le lemme 1 pour l <= 6, en prenant n0 = 6.
Pour l supérieur à 6, on prend n0 = l+2. Alors pour n > n0,
le suffixe de longueur l de u(n) est un suffixe de x(n), puisque
|x(n)| >= n-2 >= l d'après le 4. du lemme 2.
Il coïncide donc avec le suffixe de longueur l de u(n+2), puisque
x(n) est un suffixe de x(n+2) qui est un suffixe de u(n+2).
( d'après les 2. et 1. du lemme 2. )
On peut formaliser ce résultat en définissant une topologie
convenable sur l'ensemble des mots finis et infinis sur
l'alphabet {1,2,3}. On peut alors montrer que la suite u(n) a deux
valeurs d'adhérence, qui sont deux mots infinis à gauche :
...131221121321131112111322311211132132212312211322212221121123222112
et
...211331123113221321123113121322111213112221133211322112211213322112
Exercice : faire la même chose en regardant cette fois le début des mots
(ce qui est plus habituel que de regarder la fin, d'ailleurs !).
Cette fois, il y a 3 valeurs d'adhérence.
Enfin, on peut montrer que la proportion de 1 a une limite finie,
qui est un nombre algébrique de degré 71.
L'idée de Conway est d'identifier un certain ensemble fini de blocs
(qu'il nomme selon les éléments chimiques), de sorte que si x est l'un
de ces blocs, D(x) s'exprime comme concaténation de plusieurs blocs
élémentaires, et de plus qu'il n'y ait jamais d'interaction entre blocs
consécutifs, de sorte que D(xy) = D(x)D(y).
D agit alors comme une substitution (i.e. un morphisme de monoïde)
sur les mots formés de symboles de blocs élémentaires,
et le nombre d'occurrences de chacun des blocs élémentaires peut être
exprimé à l'aide de puissances de la matrice de la substitution.
D'où finalement une densité qui s'exprime en fonction des valeurs
propres de cette matrice et est donc un nombre algébrique.
Lire à ce sujet:
-- J.H. Conway "The weird and Wonderful Chemistry of Audioactive Decay"
in "Open Problems in Communications and Computation" T.M. Cover and
B. Gopinath eds., Springer 1987
-- Shalosh B. Ekhad and Doron Zeilberger "Proof of Conway's Lost
Cosmological Theorem"
-- Les commentaires d'un mathématicien, de Jean-Paul Delahaye in "Pour
la Science", Janvier 1996, p.100 et suivantes.
Voir, entre autres (Warning, in english) :
http://www.univie.ac.at/EMIS/journals/ERA-AMS/1997-01-011/1997-01-011.html
http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/horton.html
4. Probabilité que 2 personnes soient nées le même jour.
-----------------------------------------------------
On réunit dans une pièce n personnes. On veut determiner, d'une part,
quelle est la probabilité que deux de ces personnes soient nées le même
jour et d'autre part, à partir de combien de personnes il y a plus d'une
chance sur deux que l'événement cherché soit réalisé.
Enfin, on s'intéressera aux différentes méthodes de calcul et à ce qu'il
se passe quand les dates de naissance ne sont pas équiprobables.
a) Toutes les dates de naissance sont équiprobables.
On supposera dans un premier temps que les dates d'anniversaire ont
la même probabilité d'apparition.
La bonne solution, comme souvent en probabilités, consiste à calculer
la probabilité de l'événement complémentaire. C'est à dire qu'on
s'intéresse à la probabilité qu'il n'y ait aucune coïncidence des
dates d'anniversaire dans un groupe de n personnes.
En effet, la probabilité d'un événement additionnée à celle de son
complémentaire est égale à 1. Donc la probabilité de l'événement est
égale à un moins la probabilité de son complémentaire.
Le nombre total de cas possibles est 365 à la puissance n noté 365^n.
Le nombre de cas favorables est le nombre de choix ordonnés de n
dates parmi 365, soit: 365! / (365-n)!
Donc, la probabilité qu'il n'y ait aucune coïncidence de dates
d'anniversaire est :
365! / ((365-n)! * 365^n ) = produit[(365 - i)/365 , pour i=0 à n-1]
= produit[1 - i/365 , pour i=0 à n-1]
La probabilité P(n) qu'il y ait au moins une coïncidence est donc :
P(n) = 1 - produit[1 - i/365 , pour i=0 à n-1]
Il existe d'autres solutions, par exemple, la suivante.
On nomme A, B etc. les personnes de l'assistance. Alors, il y a une
coïncidence si A a le même anniversaire que B, ou que C,... Ou encore
si B a le même anniversaire que C, etc.
Le problème de cette méthode, c'est qu'il faut ensuite calculer la
probabilité d'une union d'événements qui ne sont pas disjoints.
Il faut faire la somme des probabilités des évènements, en enlever
la somme des intersections 2 à 2, ajouter la somme des intersections
3 à 3, etc. (c'est la formule de Poincaré). C'est long et pénible.
b) A partir de quelle valeur de n cette probabilité dépasse-t-elle 1/2 ?
La seule solution est de calculer la probabilité pour différentes
valeurs de n, et de rechercher la première valeur de P(n) dépassant
1/2. Cette valeur est 23. En effet, on trouve par le calcul:
P(22)=0.4756953077
P(23)=0.5072972343
c) Les différentes méthodes de calcul pratique
Si on veut calculer brutalement le nombre : 365! /((365-n)! * 365^n)
avec une machine à calculer, on obtient un dépassement de capacité.
Il faut donc réfléchir un peu pour faire le calcul, en tenant compte
des possibilités informatiques.
-- Si on dispose d'un logiciel de calcul mathématique, tel que Maple ou
Mathématica, le problème de dépassement de capacité disparaît, et on
utilise n'importe laquelle des expressions ci-dessus.
-- Si on dispose d'une calculatrice programmable, il est possible de
programmer, avec une boucle, le calcul de l'expression :
produit[1 - i/365 , pour i=0 à n-1]
Comme cette programmation dépend de la calculatrice et du langage
utilisés, il est difficile d'en dire plus.
-- Si l'on dispose d'un tableur, l'expression :
produit[1 - i/365 , pour i=0 à n-1] est facile à calculer en faisant
un tableau de taille n, avec 3 colonnes :
une colonne pour i,
une colonne pour 1 - i/365,
une colonne pour le produit.
-- Si l'on n'a qu'une calculatrice scientifique, il est nécessaire
d'utiliser une approximation. Il faut remarquer que
produit[1 - i/365 , pour i=0 à n-1]
= exp(somme[log(1 - i/365) , pour(i=0 à n-1)])
Or, si n est beaucoup plus petit que 365, on a :
log(1 - i/365) ~ -i/365
Et comme la somme des n premiers entiers est égal à n*(n+1)/2.
On a donc : produit[1 - i/365 , pour i=0 à n-1] ~ exp( -n*(n-1)/730)
Cette approximation est relativement précise. Elle donne les valeurs
suivantes pour P(22) et P(23), ce qui donne une réponse juste pour
la question (2) malgré la très forte proximité de P(23) avec 1/2 :
P(22) ~ 0.4689381108
P(23) ~ 0.5000017522
d) Probabilités inégales pour les dates de naissance
Nous avons jusque là supposé que toutes les dates de naissance
étaient de même probabilité. Que se passe-t-il si on se passe de
cette hypothèse ?
Les probabilités de coïncidence d'anniversaire sont augmentées. Cela
paraît assez naturel puisque, si ces probabilités sont très
concentrées, par exemple sur une seule date dans l'année, la
probabilité de coïncidence se rapproche de 1.
La difficulté de cette question tient au fait que l'on ne peut pas
faire varier n'importe comment les probabilités des différentes
dates de naissance. En effet, il faut que la somme de toutes ces
probabilités fasse 1.
Notons p_i la probabilité de naissance le jour i et A l'ensemble des
jours de l'année. Alors la probabilité de non-coïncidence est :
______ _____
\ | |
) | | p_i
/ | |
------ i dans S
S inclus
dans A tel que
card(S)=n
On s'intéresse aux jours 1 et 2. Les ensembles de cardinal n inclus
dans A peuvent être classés en 3 catégories:
les ensembles ne contenant ni 1 ni 2,
les ensembles contenant 1 ou 2, mais pas les deux,
les ensembles contenant 1 et 2.
On note A' l'ensemble A, moins les éléments 1 et 2.
La somme ci-dessus peut être réécrite :
_____ _____ _____ _____ _____ _____
\ | | \ | | \ | |
) | | p_i +(p + p )* ) | | p_i + p * p * ) | | p_i
/ | | 1 2 / | | 1 2 / | |
----- i dans S ----- i dans S ----- i dans S
S inclus S inclus S inclus
dans A' tel que dans A' tel que dans A' et que
card(S)=n card(S)=n-1 card(S)=n-2
Supposons que p1 et p2 soient différents, et montrons que l'on peut
augmenter la probabilité de non-coïncidence. On remplace p1 et p2
par (p1 + p2)/2.
Le premier des 3 termes ci-dessus n'est pas modifié, puisque ni p1
ni p2 n'y apparaissent. Le second non plus, car il ne dépend que de
p1+p2. En revanche, le troisième terme est augmenté, car on remplace
p1*p2 par ((p1 + p2)/2)^2 qui est plus grand.
Donc, si les p_i sont différents, la probabilité de non-coïncidence
n'est pas maximale.
Par la suite, on démontre qu'une fonction continue sur un ensemble
fermé borné atteint son maximum. Or, l'ensemble des vecteurs formés
de 365 probabilités, dont la somme fait 1, est un ensemble fermé
borné. Donc le maximum de la probabilité de coïncidence est atteint.
Il ne peut être atteint que si tous les pi sont égaux, qui est donc
le maximum. Donc, la probabilité de non coïncidence est maximale si
les probabilités de jours de naissance sont égales.
Par conséquent, si les probabilités sont égales, la probabilité de
coïncidence d'anniversaire est minimale.
5. Somme et produit de deux entiers.
---------------------------------
a) Enoncé.
Un prof de maths donne un problème à résoudre à ses deux meilleurs
élèves, Pierre et Sophie. Il donne à Pierre le produit de deux nombres
entiers compris (au sens large) entre 2 et 100, et à Sophie la somme
des deux mêmes nombres, puis il leur demande s'ils peuvent déterminer
quels étaient les nombres de départ.
Pierre: Non, je ne peux pas trouver ces deux nombres.
Sophie: Je le savais.
Pierre: Dans ce cas, je connais les deux nombres.
Sophie: Alors moi aussi.
Sachant que les deux élèves sont d'excellents logiciens et que leurs
quatre déclarations étaient rigoureusement exactes, saurez-vous être
aussi futés qu'eux, et trouver les deux nombres choisis par le
professeur ?
b) Commentaires.
L'énoncé tel qu'il est présenté ici est le plus proche de ce qui est en
général posé dans news:fr.sci.maths. Malheureusement, il lui manque des
précisions importantes sur ce que le prof de maths dit effectivement
aux élèves.
D'abord, il n'est pas précisé que Pierre sait que Sophie a la somme, et
que Sophie sait que Pierre a le produit. Bon, d'accord, c'est
« évident ». Mais il y a un autre point qui semble « évident » alors
qu'il est souvent source d'erreurs de raisonnement.
Cet autre point, c'est que l'on ne sait pas si Pierre et Sophie
connaissent la valeur minimum (2) et la valeur maximum (100) des
nombres de départ. Pour ce qui est de la valeur minimum, il faut qu'ils
la connaissent ; sinon, le problème est impossible (par exemple, s'ils
pensent que les nombres commencent à 1 au lieu de 2, alors la seule
solution serait 1 et 4, qui ne rentre pas dans le cadre de l'énoncé).
En ce qui concerne la valeur maximum, les deux cas sont possibles (soit
ils connaissent la limite, soit ils ne la connaissent pas), ce qui
donne deux problèmes différents, intéressants tous les deux.
c) Solutions.
Puisqu'il y a deux interprétations possibles de l'énoncé, il y a aussi
deux solutions distinctes. La première (c.1) suppose que Pierre et
Sophie savent que les nombres sont compris entre 2 et 100, alors que la
seconde (c.2) suppose qu'ils savent seulement que les nombres sont
supérieurs ou égaux à 2. Néanmoins, la méthode utilisée est la même
dans les deux cas, à savoir prendre chacune des 4 affirmations dans
l'ordre, et en déduire des informations précieuses sur les sommes S et
produits P possibles.
c.1) Solution dans le premier cas (valeur maximum connue, égale à 100).
Pierre: Non, je ne peux pas trouver ces deux nombres.
Ceci signifie que le produit P peut se décomposer d'au moins deux
manières différentes en produit de deux nombres compris entre 2 et 100.
Par exemple, on pourrait avoir P = 75, car ce produit se décompose en
3*25 ou 5*15, mais on ne peut pas avoir P = 77 car alors la
décomposition serait unique : 7*11.
Voici une liste de valeurs que nous pouvons d'ores et déjà éliminer:
- toute valeur inférieure à 4 ou supérieure à 10000
- le produit de deux nombres premiers (par exemple 77 = 7*11)
- le cube d'un nombre premier (par exemple 125 = 5*25)
- le double du carré d'un premier plus grand que 10 (par exemple,
242 = 2*11*11 = 11*22 : la décomposition en 2*121 est impossible)
- un multiple strict d'un nombre premier plus grand que 50 (par exemple
318 = 6*53)
- le produit du carré d'un premier plus grand que 10 par un nombre
premier (par exemple 242 = 2*11*11 = 11*22 ; la décomposition en
2*121 est impossible)
- et bien d'autres...
---
Sophie: Je le savais.
Ceci signifie que la somme S ne peut pas s'écrire comme somme de deux
nombres dont le produit aurait été éliminé dans l'étape précédente.
Par exemple, la somme 11 convient car tous les produits possibles sont
"non uniques" :
11 = 2+9 ; 2*9 = 18 = 3*6
11 = 3+8 ; 3*8 = 24 = 2*12 = 4*6
11 = 4+7 ; 4*7 = 28 = 2*14
11 = 5+6 ; 5*6 = 30 = 2*15 = 3*10
En revanche, la somme 13 ne convient pas car :
13 = 2+11 ; 2*11 = 22 (pas d'autre décomposition)
Par conséquent, on peut commencer par éliminer toutes les sommes de
deux nombres premiers. Vous pouvez vérifier que cela élimine déjà
toutes les sommes paires (ceci a été conjecturé par Goldbach dans le
cas général, et vérifié par ordinateur sur beaucoup plus de nombres que
ce dont on a besoin pour résoudre ce problème). Pour ce qui est des
sommes impaires, on élimine celles qui sont égales à un nombre premier
plus 2: 5 (3+2), 7(5+2), 9(7+2), 13 (11+2), etc.
Après ce premier débroussaillage, il nous reste les sommes qui sont
égales à un nombre composé impair plus 2 : 11 (3*3 + 2), 17 (3*5 + 2),
23 (3*7 + 2), 27 (5*5 + 2), 29, 35, 37, 41, 47, 51, 53, 57, 59, etc.
Nous pouvons aussi supprimer toutes les sommes S à partir de 57,
puisque :
si 57 <= S <= 153, on peut écrire S = 53 + n, avec 4 <= n <= 100,
si 155 <= S <= 197, on peut écrire S = 97 + n, avec 58 <= n <= 100,
si S = 199, on peut écrire S = 100 + 99.
Dans chacun de ces trois cas, le produit P correspondant (soit 53*n,
soit 97*n, soit 100*99) a une décomposition unique.
On peut enfin supprimer la somme S = 51 = 17 + 34, car le produit
P = 17*34 n'a pas d'autre décomposition.
Voici donc la liste exhaustive des sommes possibles à cette étape du
raisonnement, avec pour chaque somme la liste des produits possibles.
11 : 18 24 28 30
17 : 30 42 52 60 66 70 72
23 : 42 60 76 90 102 112 120 126 130 132
27 : 50 72 92 110 126 140 152 162 170 176 180 182
29 : 54 78 100 120 138 154 168 180 190 198 204 208 210
35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340
342
41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408
414 418 420
47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510
522 532 540 546 550 552
53 : 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612
630 646 660 672 682 690 696 700 702
---
Pierre: Dans ce cas, je connais les deux nombres.
Pour que Pierre puisse faire cette affirmation, il faut que le produit
P se trouve une fois et une seule dans la liste que nous venons
d'écrire. Cela élimine donc les produits P = 30 (S = 11 ou 17), P = 42
(S = 17 ou 23), etc. Il reste:
11 : 18 24 28
17 : 52
23 : 76 112 130
27 : 50 92 110 140 152 162 170 176 182
29 : 54 100 138 154 168 190 198 204 208
35 : 96 124 174 216 234 250 276 294 304 306
37 : 160 186 232 252 270 336 340
41 : 114 148 238 288 310 348 364 378 390 400 408 414 418
47 : 172 246 280 370 442 480 496 510 522 532 540 550 552
53 : 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696
700 702
---
Sophie: Alors moi aussi.
Pour que Sophie puisse dire cela, il faut qu'il ne reste plus qu'un
seul produit correspondant à la somme qu'elle connaît. Ceci n'est
réalisé que si la somme est 17, auquel cas le produit est 52. Les
nombres de départ sont donc 4 et 13.
c.2) Solution dans le second cas (valeur maximum inconnue).
Pierre: Non, je ne peux pas trouver ces deux nombres.
Ceci signifie que le produit n'est pas le carré ou le cube d'un nombre
premier, ni le produit de deux nombres premiers. Nous ne pouvons rien
en déduire de plus pour le moment.
---
Sophie: Je le savais.
Comme dans le premier cas, nous pouvons éliminer toute somme paire et
toute somme d'un nombre premier avec 2, et il nous reste les sommes
égales à un nombre composé impair plus 2. Contrairement au premier
cas, nous ne pouvons éliminer aucune autre somme. La liste
(incomplète) des sommes et produits possibles est la suivante:
11 : 18 24 28 30
17 : 30 42 52 60 66 70 72
23 : 42 60 76 90 102 112 120 126 130 132
27 : 50 72 92 110 126 140 152 162 170 176 180 182
29 : 54 78 100 120 138 154 168 180 190 198 204 208 210
35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 ...
37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 ...
41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 ...
47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 ...
...
---
Pierre: Dans ce cas, je connais les deux nombres.
Comme tout-à-l'heure, nous éliminons les produits P qui se trouvent
plus d'une fois dans la liste. Il reste (liste exhaustive pour toutes
les sommes inférieures à 200) :
11 : 18 24 28
17 : 52
23 : 76 112
27 : 50 92 140 152 176
29 : 54 100 208
35 : 96 124 216 304
37 : 160 232 336
41 : 148 288 400
47 : 172 280 496
51 : 98 144 188 308 344 608 620 644
53 : 520 592
57 : 212 260 392 656 800
59 : 220 688
65 : 244
67 : 192 472 1116
71 : 268 448 880
77 : 292 832 976
79 : 228 568 1504
83 : 316 1072 1216
87 : 332 632 836 1136 1340 1472 1880
89 : 1168
93 : 356 1040 1856 1952
95 : 1264 1984
97 : 712 1296
101 : 388 1144 2368 2440
107 : 412 2752
113 : 436 1552
117 : 452 872 1616 3392
119 : 1648 2728
121 : 904 2848
123 : 242 476 1712 3440 3776
125 : 484 1744 3904
127 : 1776
131 : 384 508 3784 4288
135 : 266 524 896 1016 1904 2996 3296 3956 4544
137 : 4672
143 : 556 2032 4120 5056
145 : 1096 2176 3616
147 : 290 1112 1496 2096 2432 3680 4280 5312
155 : 604 2224
157 : 1192 3712
161 : 628 2320 6208 6424
163 : 4192
167 : 652 2416 5080 6592
171 : 338 668 1304 2480 2888 3020 3404 3888 4448 5240 5504 6848 6968
7100 7304
173 : 2512 6976
177 : 692 3140 7232
179 : 2608
185 : 724
187 : 1432 7552
189 : 374 1448 2768 2924 5024 5624 7208 7448 7808
191 : 8128
197 : 772 2896
---
Sophie: Alors moi aussi.
Ici encore, il doit rester un seul produit sur la ligne de la somme
correspondant à ce qu'a Sophie. Là encore, les nombres 4 et 13 sont
solution (S=17, P=52), mais ce ne sont plus les seuls. Les autres
solutions sont: 4 et 61 (S=65, P=244), 16 et 73 (S=89, P=1168), 64 et
73 (S=137, P=4672). Bien évidemment, on ne tiendra pas compte des cas
où l'un des nombres est plus grand que 100, par exemple pour S=127 et
P=1776: les nombres seraient 16 et 111.
6. Les deux échelles.
------------------
a) Enoncé.
Deux échelles se croisent dans une cour rectangulaire. Les échelles
mesurent respectivement 10 et 14m. Vues de côté, elles se croisent à 5m
du sol. On suppose les échelles droites et sans épaisseur.
Quelle est la largeur de la cour ?
b) Solution.
On appelle :
- BF l'échelle qui va du haut à gauche au bas à droite (B en haut à
gauche) ;
- EA l'échelle qui va du bas à gauche au haut à droite (E en bas)
- I le point d'intersection des deux échelles,
- H la projection orthogonale de I sur le sol.
| |A
| /|
| / |
| / |
| / |
| / |
B| / |
|\_ I / |
| \_ / |
| \_ |
| /| \_ |
| / | \_ |
| / | \_ |
E+/---|-------\+F
H
On pose :
AF = x ; EF = y ; BE = z ;
AE = a ; BF = b ; IH = c ;
On applique le théorème de Pythagore dans le triangle FAE rectangle en F.
AF^2 + EF^2 = AE^2. C'est à dire : x^2 + y^2 = a^2.
On applique le théorème de Pythagore dans le triangle FEB rectangle en E.
EF^2 + BE^2 = BF^2. C'est à dire : y^2 + z^2 = b^2.
On applique le théorème de Thalès avec les parallèles (BE), (IH) et (AF).
c/x + c/z = EH/EF + HF/EF = (EH + HF)/EF = 1, d'où c/z = (x-c)/x
Il vient donc : x^2 - z^2 = a^2 - b^2 et z = c*x/(x-c)
Et puis : x^2 - (c*x/(x-c))^2 = a^2 - b^2
ce qui conduit à
x^4 - 2 * c * x^3 - (a^2 - b^2) * x^2 +2 * c * (a^2-b^2) * x
- c^2 * (a^2-b^2)=0
Cette équation de degré 4 se résout par radicaux ou de manière approchée
avec tout outil de calcul.
On a ensuite : y = sqrt(a^2 - x^2).
On a ici : a = 14, b = 10, c = 5, d'où l'équation :
x^4 - 10 * x^3 - 96 * x^2 + 960 * x - 2400 = 0
Et donc :
x = 12.78405 avec un outil de calcul
Puis y = sqrt(a^2-x^2) = 5.706842.
7. La cuve de vin.
---------------
Problème :
Du vin est placé dans une cuve cylindre horizontale de longueur L est
de rayon R. On mesure la hauteur h de vin dans la cuve, et on veut en
déduire le volume v de vin.
Une solution :
On peut s'en sortir avec un peu de calcul intégral. Si l'on considère
un axe vertical dont l'origine est placée à la hauteur du centre du
cylindre, alors la section du cylindre à la hauteur z a pour aire
a(z) = 2*sqrt(R^2-z^2)*L.
Par conséquent, on a : v = int(-R..h-R, a(z)dz)
L'intégrale se calcule par le changement de variable z = R*sin t. On a
alors successivement, en notant x = h/R - 1 (x=-1 lorsque la cuve est
vide, x=0 à mi-hauteur et x=1 quand elle est pleine) :
v = int(-pi/2..Arcsin x, 2L*R^2*cos^2 t dt)
v = L*R^2*int(-pi/2..Arcsin x, (1+cos 2t)dt)
v = L*R^2*[Arcsin x + sin(2*Arcsin x) - (-pi/2 + sin(-pi)]
Finalement, si l'on appelle v0 = pi*R^2*L le volume total de la cuve,
on obtient le taux de remplissage :
v/v0 = [Arcsin x + x*sqrt(1-x^2) + pi/2]/pi, ou plus simplement
v/v0 = [x*sqrt(1-x^2) + Arccos(-x)]/pi
Voici quelques valeurs :
x -1.00 -0.75 -0.50 -0.25 0.00 0.25 0.50 0.75 1.00
v/v0 0% 7% 20% 34% 50% 66% 80% 93% 100%
À noter que la formule ne s'inverse pas simplement (i.e. il n'y a pas
d'expression élémentaire de h en fonction de v), donc si c'est le
niveau
de vin que l'on cherche, le plus simple est de résoudre l'équation
numériquement. On trouve par exemple :
v/v0 10% 20% 30% 40% 50% 60% 70% 80% 90%
x -0.69 -0.49 -0.32 -0.16 -0.00 0.16 0.32 0.49 0.69
========================================================================
Les autres parties de cette FAQ se trouve dans les documents intitulés :
[FAQ] fr.sci.maths - partie 1/3
[FAQ] fr.sci.maths - partie 3/3
Ces documents sont disponibles sur fr.sci.maths ou à l'adresse :
http://www.usenet-fr.net/fur/maths/maths-faq.html
http://www.usenet-fr.net/fur/maths/maths-faq-3.html
.
Traduit en HTML par faq2html.pl le Wed Nov 3 05:42:13 2010 pour le site Web Usenet-FR.
