Les 12 boules.

[Patastronch]

On dispose de douze boules :
Une boule est différente des autres.
Elle est soit plus lourde soit plus légère.

Quel est le nombre minimum de pesées necessaire sur une balance ( à plateau ), sans poids, pour retrouver cette boule et dire si elle est plus lourde ou plus légère.

[Alpha]

Salut, Patast...,

Voilà comment je procéderai : 6 boules de chaque côté d'abord, ensuite, une fois que j'ai déterminé quel était le groupe de 6 le plus lourd, j'en déduis que soit le groupe le plus léger contient une boule plus légère que les autres, soit c'est l'autre groupe qui contient une boule plus lourde que les autres.

Il faut alors que dans chaque groupe, je compare les boules entre elles : pour le premier groupe de 6, je sépare en 3 et 3, et pour le 2ème, je fais pareil, et après ces 2 pesées, je sais dans quel groupe se trouve la boule anormale, et si elle est plus lourde ou plus légère que les autres.

De plus, dans l'une de mes deux dernières pesées, j'ai donc eu un des deux groupes de 3 plus lourd ou plus léger que l'autre, je prends 2 de ces 3 boules, je les compare, si elles pèsent autant, je sais que c'est l'autre qui est anormale, si elles ne pèsent pas autant, je sais laquelle est anormale.

Par conséquent, j'ai éffectué 1+2+1 = 4 pesées.

Mais je ne suis pas sûr d'avoir prouvé que c'était le plus petit nombre de pesées que l'on peut effectuer.

Cordialement.

[Galt]

Il y a un algorithme à 3 pesées.
Question supplémentaire :quel est le nombre maximal de billes nécessitant 4 pesées ?

[Alpha]

Salut Galt!

Peut-on connaître cet algorithme à 3 pesées?

Merci

[Patastronch]

Je préfererais que Galt ne donne pas la réponse comme ca. Vous l'aurez compris 3 est la réponse, Comment fait-t-on ? là est toute la partie intéressante du probleme.

[Patastronch]

(.../...)

Il ya beaucoup plus simple en 4 pesées. Et surtout il faut pouvoir déterminer si elle est plus lourde ou plus légère et pas seulement déterminer la boule anormale.

[Patastronch]

Il y a un algorithme à 3 pesées.
Question supplémentaire :quel est le nombre maximal de billes nécessitant 4 pesées ?

Sans raisonement je dirais qu'en utilisant le principe de l'algorithme en trois pesées pour les 12 boules, 24.

Apres je n'ai pas réfléchis encore si 12 était un vrai maximal pour 3 pesées, ou si en 4 pesées on ne peut pas faire plus malin que cet algorithme.

Mais je peux affirmer que c'est au moins 24 le maximum :lol4:

[Patastronch]

Bon j'ai trouvé pour 26 boules en 4 pesées, je cherche pour 28 !

[Patastronch]

Bon j'en suis a 28, mais mon intuition me dit que c'est le maximum.

Si la solution interesse quelqu'un je la donnerai lorsque l'algorithme en trois pesées pour 12 boules sera trouvé puisque je m'en sert.

[Galt]

On peut aller jusqu'à 36 en 4 pesées. Bien évidemment, il faut utiliser l'algorithme en 3 pesées.

[Zebulon]

Bonjour à tous,
je suis nouvelle sur le forum.
J'ai cherché le problème des 12 boules en 3 pesées. Je pense avoir trouvé un moyen d'y arriver. Peut-être est-ce "l"'algorithme des 3 pesées dont vous parlez, ou un autre, enfin voilà:
Je sépare les 12 boules en 3 paquets de 4.
Je prends les deux premiers paquets et je les compare.

A). Si ça ne balance pas, ça va:on sait que la boule recherchée est parmi les quatre restantes et il reste 2 pesées. Je prends trois boules de ce paquet et je les compare à trois autres "neutres".
Si ça ne balance pas, c'est la boule restante que l'on compare avec n'importe quelle autre boule pour savoir si elle est plus ou moins lourde que les autres.
Si ça balance, on sait que c'est une de ces trois boules, elle est plus (resp moins, selon le résultat de la pesée) lourde, et il reste une pesée. Je compare deux de ces trois boules entre elles. Si ça ne balance pas, c'est l'autre et elle est plus (resp moins) lourde; si ça balance, c'est celle qui est la plus (resp moins) lourde.

B). Si ça balance, ça se corse. On a alors toujours trois paquets de 4 boules:un de "susceptibles d'être plus lourdes" (que je qualifie de S+), un de "susceptibles d'être moins lourdes" (que je qualifie de S-), et un de "neutres" (que je qualifie de N). Je forme 4 nouveaux paquets:
paquet G:{2 S- et 1 S+}
paquet D:{1 S-, 1 N et 1 S+}
paquet N:les 3 boules N restantes
paquet R:les boules restantes, ie {1 S- et 2 S+}
Je compare sur la balance les paquets G et D ( :id: je mets G à gauche et D à droite). Après ça, il reste une pesée.
1) Si la balance penche à gauche, ie G est plus lourd alors c'est la S+ de G qui est plus lourde ou la S- de D qui est moins lourde. J'en compare une des deux avec une N et ok...;
2) Si la balance penche à droite, ie D est plus lourd, alors c'est une des deux S- (que j'appelle S-1 et S-2) de G qui est moins lourde ou la S+ de D qui est plus lourde. Je compare: {S-1 et S+} avec 2N. Si ça ne balance pas, alors c'est S-2 qui est moins lourde. Si {S-1 et S+} est plus (resp moins) lourd que 2N, alors c'est S+ (resp S-1) qui est plus (resp moins) lourde;
3) Si G et D ont le même poids, alors la boule recherchée est dans le paquet R. Je suis alors ramenée au cas 2) en inversant les plus et les moins...flemme...

Voilà ma solution. Est-ce que c'est bon?

[Patastronch]

Bravo c'est ca !!!

[Zebulon]

Monsieur Galt, j'ai réussi à prouver le résultat pour les 36 boules en 4 pesées. Ne peut-on pas étendre le résultat à (3^k)*12 en k+3 pesées? Je cherche, je récurre tant que je peux...

[Anonyme]

Bien vu, Zebulon.
J'ai trouvé aussi le résultat pour les 36 boules en 4 pesées.

Pour la généralisation, c'est possible par récurrence: il suffit de montrer par récurrence que si l'on a une boule différente et qu'on sait qu'elle est plus légère ou plus lourde parmi 3^k boules, on sait faire en k pesées, puis d'en déduire que s'il y a une boule différente et qu'on sait qu'elle est plus légère ou plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées, et que si on sait qu'il y a une boule plus légère parmi 3^k boules ou une boule plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées.

C'est bien ça ?

[Patastronch]

si l'on a une boule différente et qu'on sait qu'elle est plus légère ou plus lourde parmi 3^k boules, on sait faire en k pesées.

Non pour 3 pesées le max est 12 boules.(on peut prouver que 13 boules n'est pas possible en 3 pesées)

D'apres ce que j'ai pu trouver :

le nombre de boule max pour P pesées est :
(3^P-3)/2.

Par construction d'un algorithme on prouve facilement que le max de boules est superieur a (3^P-3)/2 (encore faut il trouver la construction), apres pour prouver que que le max de boules est inferieur ou egal a (3^P-3)/2 pour P pesées j'ai pas trouvé de méthode maline.Et puis meme, de toute facon ma methode "bourrine" me parait fausse.

Peut etre que Galt pourrait nous aider ? et confirmer que (3^P-3)/2 est bien le maximum de boules pour P pesées ?

[Anonyme]

>>Non pour 3 pesées le max est 12 boules.(on peut prouver que 13 boules n'est pas possible en 3 pesées)

Oui. Je n'étais pas claire : je voulais dire que si on a une boule plus légère (on sait déjà qu'elle est plus légère) parmi 3^k boules, on peut la trouver en k pesées.
Par exemple: en 2 pesées, on peut trouver la boule la plus légère parmi 9 boules.

Sinon, pour le nombre max de boules, je n'ai aucune idée, j'ai juste montré par récurrence que si on a une boule différente parmi 12.3^k boules, on peut la trouver et dire si elle est plus lourde ou plus légère en k+3 pesées.

Pour k=0: on a vu que c'est vrai.
Supposons que c'est vrai pour un entier k quelconque, et montrons que c'est vrai pour k+1.

.Première pesée: On partage les 12.3^(k+1) boules en 12.3^(k+1) / 3 boules et on fait : 12.3^k boules d'un coté et 12.3^k boules de l'autre coté de la balance.
1er cas: si ça balance pas, la boule cherchée fait partie de 12.3^k boules restantes: on sait faire d'après l'hypothèse en k+3 pesées.
on a donc fait k+4 pesées.

2e cas: Si ça balance, on a alors 12.3^k boules susceptibles d'être plus légères (l) et 12.3^k boules susceptibles d'être plus lourdes (L) et 12.3^k boules normales (L).
.2ème pesée: on fait 12.3^k/2 boules (L) avec 12.3^k/4 boules (N) d'un coté, et 12.3^k/ boules(L) avec 3.3^k boules (l) de l'autre coté.
On a alors 3 cas a, b et c :
(6.3^k(L)+3.3^k(l)) a
(6.3^k(L)+3.3^k(N))-- (6.3^k(L)+3.3^k(l)) b
(6.3^k(L)+3.3^k(l)) c

b => la boule cherchée fait partioe des (l) restantes, y en a 3^(k+2) . On sait donc qu'elle est légère et on sait faire en k+2 pesées. (*)
c=> la boule cherchée fait partie des 6.3^k=2.3^(k+1) (L) (à droite), on sait qu'elle est lourde et on sait faire en k+2 pesées. (*)
a => la boule chechée est soit plus légère et fait partie de 3^(k+1) (l), soit plus lourde et fait partie de 2.3^(k+1) (L) (à droite)
, on sait faire en k+2 pesées. (*)

dans les 3 cas, on a 2+k+2 = k+4 pesées.

-
(*) On montre par récurrence que si l'on a une boule différente et qu'on sait d'avance si elle est plus légère ou plus lourde parmi 3^k boules, on sait faire en k pesées, on en déduit que s'il y a une boule différente et qu'on sait qu'elle est plus légère ou plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées, et que si on sait qu'il y a une boule plus légère parmi 3^k boules ou une boule plus lourde parmi 2.3^k boules, on sait faire en k+1 pesées.

Voilà, en éspérant que je me suis pas trompée.

Sinon, je veux bien savoir le nombre max de boules pour p pesées...

[Patastronch]

ok je vois ce que tu voulais dire.

De toute facon comme je l ai dit avant j arrive a démontrer que le max de boules vaut au moins (3^P-3)/2, et ca majore 12*3^(P-3).

Si quelqu'un trouve mieu que (3^P-3)/2 qu'il le fasse savoir ! A force on finira bien par le trouver ce maximum :p

[Anonyme]

Bon, j'ai trouvé pour 37 et 38 boules en 4 pesées, euh tu fais comment pour 39 boules en 4 pesées ?

C'est vrai que (3^P-3)/2 >= 12.3^(P-3), mais on peut affirmer que que P est le nombre min de pesées pour 12.3^(P-3) boules, vu que 12.3^(P-3) > (3^(P-1)-3)/2 . (je suppose que le nombre max de boules pour P pesées est (3^P-3)/ puisque tu le crois). C'est moins intéressant mais bon...

[Patastronch]

t as trouvé 37, 38 boules en 4 pesées maximum ? Moi j ai pas cherché pour plus que 36 boules.

Ca m interesse envoit ! Surtout que si Galt dit que 36 est le maximum je trouve ca etonnant.

Et ma formule n'a rien de véridique. Je l'ai juste estimé a partir de :

2 pesées : max 3 boules. (max sur, en traitant toutes les possibilités on s'en convain facilement)
3 pesées : max 12 boules. (max sur, on peut prouver que 13 c est pas possible)
4 pesées : max 36 boules. (max que je croyais etre sur selon les dires de Galt mais apparement t as trouvé mieu)

Apres j'ai juste démontré que l'algo existait pour ce nombre de boule donné par la formule.
Mais rien ne certifis que c est la bonne formule qui donne le nombre max de boules.

J'affirme juste que (3^P-3)/2 est le minimum de boules que l'on peut traiter en P pesées.

[Anonyme]

38 boules en 4 pesées:

On partage les 38 boules en 12, 13 et 13 boules.
1ère pesée : On fait 13 boules d'un coté et 13 de l'autre coté.
1er cas : si ça balance pas, la boule qu'on cherche fait partie des 12 boules restantes, on sait faire en 3 pesées.
(4 pesées en tout)

2e cas : si ça balance, on a alors 13(L), 13(l) et 12(N).
.2e pesée: On fait 4(L)+9(N) d'un coté et 9(L)+4(l) de l'autre, on a alors 3 cas :

a) 9(L)+4(l)
b) 9(L)+4(l)---4(L)+9(N)
c) 9(L)+4(l)

b=> La boule cherchée est plus légère et elle est parmi 9(l) restantes : on sait faire en 2 pesées.

c=> La boule cherchée est plue lourde et elle est parmi 9(L): on sait faire en 2 pesées.

a=> la boule cherchée est soit plus lourde parmi 4(L), soit plus légère parmi 4(l)
3e pesée: On fait 2(L)+1(N) d'un coté et 2(L)+1(l) de l'autre, on a alors 3 cas:
a') 2(L)+1(l)
b') 2(L)+1(l)--2(L)+1(N)
c') 2(L)+1(l)

a' => la boule cherchée est soit plus lourde parmi 2(L) (à droite), soit plus légère parmi 1(l): on sait faire en 1 pesée, on compare les 2(L) et c'est fini.

b'=> La boule cherchée est plus légère parmi 3(l) restantes : on sait faire en 1 pesée.

c'=> La boule cherchée est plus lourde parmi 2(L): on sait faire en 1 pesée.

On a donc fait 4 pesées.

(sauf erreur)
--
J'ai cheché pour 37 et 38 boules car tu as dit que le nombre max de boules pour 4 pesées est (3^4-3)/2 = 39, non ?