par GUNDAG Rakibe, RIVALLAN Estelle, SANTHIRALINGAM Samantika,lves des lyces R.Rolland d’Argenteuil 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 s’appelle 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 s’ennuient tellement qu’ils dcident d’essayer de trouver un sujet de contrle pour leurs lves de premire scientifique qui tudient les probabilits. Pour cela, Olive a eu une ide lorsqu’elle a vu toutes ces pices turques. Elle a pens qu’il 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 d’une pice talon (c’est--dire une vraie pice) et d’une 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 d’abord de trouver cette fausse pice (s’il y en a une) sans utiliser la pice talon ?

Franois : Je veux bien partir de 3 pices mais pour 1 et 2 pices, ce n’est pas possible : nous devons utiliser la pice talon. Regarde !

Avec 1 pice : 2 cas

1er cas : ( 1 ) = ( E ) il n’y a pas de fausse pice

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

Avec 2 pices : 2 cas

:

Franois : Tu vois, on est oblig d’utiliser la pice talon lors de la deuxime pese.

Olive : Essaye avec 3 pices.

Franois : D’accord. Regarde ce que l’on trouve sans la pice talon.

 

Au bout d’une demi-heure, Franois et Olive avaient dj trouv le nombre de peses qu’il 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 : 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 pice talon donc on ne prend pas ce cas en compte)on a :

      k tant le nombre de peses suffisant


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 l’on 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 n’y 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 j’ai 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 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 pice tait plus lourde ou plus lgre que les autres. De plus, nous n’avons pas utilis la pice talon et l’exemple de 12 pices nous laisse supposer qu’elle 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)

 

c’est le maximum de rsultats possibles (car dans le schma prcdent, on compte des cas impossibles)

donc 2n + 1 3k

Olive : Si on s’intressait au cas o 2n + 1 =

2n + 1 =

Grce cette galit, j’ai 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

d’o 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 l’on peut dterminer, alors on peut connatre le nombre de pices maximum que l’on peut dterminer avec une pese supplmentaire.

 

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