Quelqu’un a-t-il généralisé le problème des douze pièces?

Question

(En ayant doit à N pesées, parmi combien de pièces pourrait-on trouver la fausse)

JVR, en plus de trouver l'intruse, il faut préciser si elle est plus lourde ou plus légère; sinon ce serait le problème des 27 pièces en trois pesées.

Answer 1

Bonjour,

Je l'ai généralisé il y a quelques années. Sauf erreur de ma part :

Nombre de pesées = INT ( log3 ( 6n + 6 ) )

(où INT = partie entière, et "log3" = log en base 3)

Il faut d'abord constater que le nombre maximum de boules pour p pesées est donné par

n = ( 3^p - 3 ) / 2

Answer 2

En une pesée on peut déterminer au maximum l'intruse parmi 3 pièces

( on en pèse 2, si inégalité on a la réponse, si égalité, c'est que c'était la 3° pièce non pesée)

Hypothèse de récurrence: En N pesées on peut avoir jusqu'à 3 puissance N pièces.

Supposons qu'on ait le droit à N+1 pesées.

Si on a 3 puissances N+1 pièces, on sépare en 3 groupes de 3 puissances N pièces.
On fait une première pesée. On sait alors dans quel groupe de 3 puissance N pièces se trouve la fausse.

On choisit ce groupe de pièces, et on utilise l'hypothèse de récurence : on pourra bien déterminer la fausse pièce en N autres pesées, total N+1 pesées.

Edit : Il va falloir que je réfléchisse davantage alors !

Answer 3

le pb des 12 pieces (moi CT des boules...) m'a assez fait tourner la tête pour arriver à 3coups.. de la a le généraliser à n pesées....