par GUNDAG Rakibe, RIVALLAN Estelle, SANTHIRALINGAM Samantika,lves des lyces R.Rolland dArgenteuil et P. Eluard de Saint-Denis
Professeurs : BRUN Olivier ; DESESPRINGALLE Franck ; GUY Dominique ; HUET Alain
Chercheur : ALLYS Loc
I PRESENTATION DU SUJET
Un professeur de mathmatiques qui sappelle Franois va en Turquie et change mille francs contre un tas de pices. Un jour de pluie, Franois ne peut pas sortir et reste donc dans sa chambre avec son amie Olive. Ils sennuient tellement quils dcident dessayer de trouver un sujet de contrle pour leurs lves de premire scientifique qui tudient les probabilits. Pour cela, Olive a eu une ide lorsquelle a vu toutes ces pices turques. Elle a pens quil y avait peut-tre (et au maximum) une fausse pice qui pouvait tre soit plus lourde, soit plus lgre que les autres. Franois et Olive disposent dune pice talon (cest--dire une vraie pice) et dune balance plateaux pour trouver en un minimum de peses cette ventuelle fausse pice.
II CONVENTIONS UTILISEES
n : nombre de pices
k : nombre de peses
E : pice talon
1,2,3 : le numro de la pice
( ) ( ) : la balance plateaux
= : quilibre de la balance
: dsquilibre de la balance
III SANS ETALON
Olive : Si on essayait dabord de trouver cette fausse pice (sil y en a une) sans utiliser la pice talon ?
Franois : Je veux bien partir de 3 pices mais pour 1 et 2 pices, ce nest pas possible : nous devons utiliser la pice talon. Regarde !
Avec 1 pice : 2 cas
1er cas : ( 1 ) = ( E ) il ny a pas de fausse pice
2e cas : ( 1 ) ( E ) la "1" est fausse
Avec 2 pices : 2 cas
:
Franois : Tu vois, on est oblig dutiliser la pice talon lors de la deuxime pese.
Olive : Essaye avec 3 pices.
Franois : Daccord. Regarde ce que lon trouve sans la pice talon.
Au bout dune demi-heure, Franois et Olive avaient dj trouv le nombre de peses quil fallait pour 3 pices, 4 pices 9 pices. Voici le tableau des rsultats :
Nombre de pices |
Nombre de peses |
3 4 5 6 7 8 9 |
2 3 3 4 4 5 5 |
Franois : Jai fait une conjecture ! (Cest--dire, jai devin une loi)
Quand n 3 et n pair,(cela marche aussi pour n = 2 mais il faut utiliser la pice talon donc on ne prend pas ce cas en compte)on a :
|
Quand n 3 et n impair, (cela marche aussi pour n = 1 mais on ne prend pas ce cas en compte pour la mme raison que prcdemment) on a :
k tant le nombre de peses suffisant
Olive : Nous pouvons utiliser une autre mthode : la dichotomie. Pour ce faire, prenons pour nombre de pices dans chaque plateau une puissance de 2. Regarde avec 4 et 9 pices ce que lon trouve !
Franois : pour 9, on laisse une pice de ct et on met 4 pices sur chaque plateau. Si la pice laisse est fausse, la balance sera quilibre.
Avec 4 pices : il faut 3 peses :
Avec 4 pices : il faut 3 peses ( 1,2 ) = ( 3,4 ) il ny a pas de fausse pice
![]()
De faon analogue, Franois et Olive ont obtenu les rsultats suivants :
Nombre de pices | 3 |
4.5.6.7 |
8.9.10...15 | 16 ..31 |
32 ..63 |
64 .etc |
Puissance de 2 |
2 |
|
|
|
||
Nombre de peses |
2 |
3 |
4 |
5 |
6 |
Olive : Moi aussi jai une conjecture
Si n est le nombre de pices et k l'exposant de 2, alors et le nombre suffisant de peses est alors k.
Franois : Regarde Olive ! Pour 12 pices, on peut trouver la fausse pice, avec la pice talon, en 3 peses alors quil ten a fallu 4
.
![]()
Olive : Cest vrai, nous navions pas tenu compte dune information ! Nous ne savions pas si la fausse pice tait plus lourde ou plus lgre que les autres. De plus, nous navons pas utilis la pice talon et lexemple de 12 pices nous laisse supposer quelle permet de trouver la fausse pice plus rapidement.
IV AVEC UNE PIECE ETALON
Olive : Si nous avons n pices, il y a 3 possibilits :
soit toutes les pices sont bonnes : 1 cas
soit une pice est plus lourde que les autres : n cas
soit une pice est plus lgre que les autres : n cas
Nous avons donc 2n + 1 cas diffrents.
Franois : De plus : pour la 1re pese, on a 3 rsultats possibles
pour la 2e pese, on a 32 rsultats possibles
pour la pese numro k, il y a 3k rsultats possibles
voir le schma suivant
(1)
(2)
(3)
![]()
(1)
![]()
(2) (3)
cest le maximum de rsultats possibles (car dans le schma prcdent, on compte des cas impossibles)
donc 2n + 1 3k
Olive : Si on sintressait au cas o 2n + 1 =
![]()
2n + 1 =
![]()
Grce cette galit, jai tabli le tableau suivant :
k : nombre de peses |
n = Nk : nombre de pices |
0 1 2 3 4 5 |
0 1 4 13 40 121 |
Franois : Avec k peses, on peut connatre au plus
pices, avec :
Nk =
2Nk + 1 =
Dmontrons, par rcurrence seule, que Nk+1 = 3Nk + 1, on note cette proprit (Pk)
pour k = 0, N0 = 0 et N1 = 1
donc on a bien N1 = 3N0 + 1 (P0) est vraie
supposons, pour un k donn, que Nk+1 = 3Nk + 1
Nk+1 =
donc 3Nk+1 + 1 = 3*
+ 1
donc 3Nk+1 + 1 =
+ 1
or, 3k+2 = 2Nk+2 +1
do 3Nk+1 + 1 =
![]()
3Nk+1 + 1= Nk+2 1 + 1
3Nk+1 + 1= Nk+2
donc si (Pk) est vraie, alors (Pk+1) est vraie.
Conclusion : La proprit (P0) est vraie. Si elle est vraie pour k, alors elle vraie pour k+1. Donc elle est vraie pour tout k IN. Donc, si avec k peses on connat le nombre de pices maximum que lon peut dterminer, alors on peut connatre le nombre de pices maximum que lon peut dterminer avec une pese supplmentaire.
Olive : Je pense que tes lves voudront une exercice beaucoup plus facile et quils pourront faire en une heure, non pas en trois jours.