par GUNDAG Rakibe, RIVALLAN Estelle, SANTHIRALINGAM Samantika,Žl�ves des lycŽes R.Rolland d’Argenteuil et P. Eluard de Saint-Denis

Professeurs : BRUN Olivier ; DESESPRINGALLE Franck ; GUY Dominique ; HUET Alain

Chercheur : ALLYS Lo•c

Un professeur de mathŽmatiques qui s’appelle Fran�ois va en Turquie et Žchange mille francs contre un tas de pi�ces. Un jour de pluie, Fran�ois ne peut pas sortir et reste donc dans sa chambre avec son amie Olive. Ils s’ennuient tellement qu’ils dŽcident d’essayer de trouver un sujet de contr™le pour leurs Žl�ves de premi�re scientifique qui Žtudient les probabilitŽs. Pour cela, Olive a eu une idŽe lorsqu’elle a vu toutes ces pi�ces turques. Elle a pensŽ qu’il y avait peut-�tre (et au maximum) une fausse pi�ce qui pouvait �tre soit plus lourde, soit plus lŽg�re que les autres. Fran�ois et Olive disposent d’une pi�ce Žtalon (c’est-ˆ-dire une vraie pi�ce) et d’une balance ˆ plateaux pour trouver en un minimum de pesŽes cette Žventuelle fausse pi�ce.

n : nombre de pi�ces

k : nombre de pesŽes

E : pi�ce Žtalon

1,2,3… : le numŽro de la pi�ce

(…) Ð (…) : la balance ˆ plateaux

= : Žquilibre de la balance

Õ : dŽsŽquilibre de la balance

Olive : Si on essayait d’abord de trouver cette fausse pi�ce (s’il y en a une) sans utiliser la pi�ce Žtalon ?

Fran�ois : Je veux bien ˆ partir de 3 pi�ces mais pour 1 et 2 pi�ces, ce n’est pas possible : nous devons utiliser la pi�ce Žtalon. Regarde !

Avec 1 pi�ce : 2 cas

1^er cas : ( 1 ) = ( E ) Þ il n’y a pas de fausse pi�ce

2^e cas : ( 1 ) Õ ( E ) Þ la "1" est fausse

Avec 2 pi�ces : 2 cas

:

Fran�ois : Tu vois, on est obligŽ d’utiliser la pi�ce Žtalon lors de la deuxi�me pesŽe.

Olive : Essaye avec 3 pi�ces.

Fran�ois : D’accord. Regarde ce que l’on trouve sans la pi�ce Žtalon.

Au bout d’une demi-heure, Fran�ois et Olive avaient dŽjˆ trouvŽ le nombre de pesŽes qu’il fallait pour 3 pi�ces, 4 pi�ces…9 pi�ces. Voici le tableau des rŽsultats :

Fran�ois : J’ai fait une conjecture ! (C’est-ˆ-dire, j’ai devinŽ une loi)

 

Quand n Ò 3 et n pair,(cela marche aussi pour n = 2 mais il faut utiliser la pi�ce Žtalon donc on ne prend pas ce cas en compte)on a :

      k Žtant le nombre de pesŽes suffisant

Quand n Ò 3 et n impair, (cela marche aussi pour n = 1 mais on ne prend pas ce cas en compte pour la m�me raison que prŽcŽdemment) on a :

k Žtant le nombre de pesŽes suffisant

 

 

Olive : Nous pouvons utiliser une autre mŽthode : la dichotomie. Pour ce faire, prenons pour nombre de pi�ces dans chaque plateau une puissance de 2. Regarde avec 4 et 9 pi�ces ce que l’on trouve !

Fran�ois : pour 9, on laisse une pi�ce de c™tŽ et on met 4 pi�ces sur chaque plateau. Si la pi�ce laissŽe est fausse, la balance sera ŽquilibrŽe.

Avec 4 pi�ces : il faut 3 pesŽes :

Avec 4 pi�ces : il faut 3 pesŽes ( 1,2 ) = ( 3,4 ) Þ il n’y a pas de fausse pi�ce

 

De fa�on analogue, Fran�ois et Olive ont obtenu les rŽsultats suivants :

4.5.6.7

Olive : Moi aussi j’ai une conjecture

Si n est le nombre de pi�ces et k l'exposant de 2, alors et le nombre suffisant de pesŽes est alors k.

 

Fran�ois : Regarde Olive ! Pour 12 pi�ces, on peut trouver la fausse pi�ce, avec la pi�ce Žtalon, en 3 pesŽes alors qu’il t’en a fallu 4

.

 

Olive : C’est vrai, nous n’avions pas tenu compte d’une information ! Nous ne savions pas si la fausse pi�ce Žtait plus lourde ou plus lŽg�re que les autres. De plus, nous n’avons pas utilisŽ la pi�ce Žtalon et l’exemple de 12 pi�ces nous laisse supposer qu’elle permet de trouver la fausse pi�ce plus rapidement.

 

 

IV AVEC UNE PIECE ETALON

Olive : Si nous avons n pi�ces, il y a 3 possibilitŽs :

• soit toutes les pi�ces sont bonnes : 1 cas

• soit une pi�ce est plus lourde que les autres : n cas

• soit une pi�ce est plus lŽg�re que les autres : n cas

Nous avons donc 2n + 1 cas diffŽrents.

Fran�ois : De plus : pour la 1^�re pesŽe, on a 3 rŽsultats possibles

pour la 2^e pesŽe, on a 3² rŽsultats possibles

pour la pesŽe numŽro k, il y a 3^k rŽsultats possibles

---

voir le schŽma suivant

(1) (2) (3)

(1)

(2)

(3)

 

c’est le maximum de rŽsultats possibles (car dans le schŽma prŽcŽdent, on compte des cas impossibles)

donc 2n + 1 £ 3^k

Olive : Si on s’intŽressait au cas o� 2n + 1 =

2n + 1 = ó

Gr‰ce ˆ cette ŽgalitŽ, j’ai Žtabli le tableau suivant :

Fran�ois : Avec k pesŽes, on peut conna”tre au plus pi�ces, avec :

N_k = ó 2N_k + 1 =

 

DŽmontrons, par rŽcurrence seule, que N_k+1 = 3N_k + 1, on note cette propriŽtŽ (P_k)

• pour k = 0, N₀ = 0 et N₁ = 1

donc on a bien N₁ = 3N₀ + 1 Þ (P₀) est vraie

 

• supposons, pour un k donnŽ, que N_k+1 = 3N_k + 1

N_k+1 = donc 3N_k+1 + 1 = 3* + 1

donc 3N_k+1 + 1 = + 1

or, 3^k+2 = 2N_k+2 +1

d’o� 3N_k+1 + 1 =

3N_k+1 + 1= N_k+2 – 1 + 1

3N_k+1 + 1= N_k+2

 

donc si (P_k) est vraie, alors (P_k+1) est vraie.

 

Conclusion : La propriŽtŽ (P₀) 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 pesŽes on conna”t le nombre de pi�ces maximum que l’on peut dŽterminer, alors on peut conna”tre le nombre de pi�ces maximum que l’on peut dŽterminer avec une pesŽe supplŽmentaire.

 

Olive : Je pense que tes Žl�ves voudront une exercice beaucoup plus facile et qu’ils pourront faire en une heure, non pas en trois jours.