Les 12 boules.

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: 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.


Posted by: 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.


Posted by: Galt

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


Posted by: Alpha

Salut Galt!

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

Merci


Posted by: 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.


Posted by: Patastronch

Citation:
Posté par Galt
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


Posted by: Patastronch

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


Posted by: 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.


Posted by: Galt

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


Posted by: 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 ( 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?


Posted by: Patastronch

Bravo c'est ca !!!


Posted by: 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...


Posted by: Bouchra

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 ?


Posted by: Patastronch

Citation:
Posté par Bouchra
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 ?


Posted by: Bouchra

>>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...


Posted by: 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


Posted by: Bouchra

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...


Posted by: 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.


Posted by: Bouchra

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 ?


Posted by: Patastronch

oui oui c es bon. Dailleur je suis bete j ai bien l algo pour 39 boules puisque (3^4-3)/2 vaut 39 et non 36. J'avais meme pas réalisé que j'avais trouvé plus que le 36 boules de Galt.

Je te metrais la maniere de faire demain ou directement la construction de l algo si ca t interesse.


Posted by: Patastronch

Bon jai un peu de temps finallement je te met l algo pour 39 boules :

3 paquets de 13 boules :

on pese : 13 boules avec 13 autres, si ca penche on sait faire (voir ton cas)

Si ca penche pas , on a 13 inconnu et 26 normales determinées :

On pese 13 N avec 9 boules inconnu + 4 N

On a 3 cas :

Si ca penche a gauche : La boule est plus legere et est parmis les 9 inconnu pesées. On sait faire en 2 pesées.

Si ca penche a droite : La boule estplus lourde et est parmis les 9 boules inconnu pesées. On sait faire en 2 pesées.

Si ca penche pas : La boule est parmis les 4 inconnues restantes,on sait faire en 2 pesées. (on pese 3 inconnu avec 3 normales, si ca penche pas on pese la derniere avec une normale, si ca penche on se retrouve avec soit 3 legere soit 3 lourdes et on sait faire en une pesée.)

Sauf erreur ca marche.

Me méthode fonctionne sur le principe suivant en gros :

On divise en 3 paquets. Chaque paquet comporte N boules exactement, ou N vaut le nombre de boules maximum pesable en (P-1) pesées.

Pour une pesée : 3 tas de 0 soit 0 boules en tout
Pour 2 pesées : 3 tas de 1 soit 3 boules en tout
Pour 3 pesées : 3 tas de 4 soit 12 boules en tout
Pour 4 pesées : 3 tas de 13 soit 39 boules en tout

pour 5 pesées on aurait donc : 3 tas de 40 boules, soit 120 boules en tout.

C est omme ca que j ai conjecturé la formule (3^P-3)/2. Mon algo fonctionne sur des séparation de cette maniere. Mais rien ne justifie qu'on ne puisse pas faire mieu je le repete.

Donc le tout est de savoir si 40 boules c est trouvable en 4 pesées :)


Posted by: Bouchra

Merci beaucoup.
Pour 39 boules, moi j'avais partagé en 11, 14 et 14 boules et ça marchait pas. Avec ta méthode ça marche très bien.
je vois un peu la construction.

Pour 40 boules en 4 pesées, j'ai des doutes que ce soit possible mais on sait jamais, vais chercher...

Merci encore pour le temps consacré.


Posted by: Patastronch

De rien, ca me fait meme plaisir de savoir que je suis pas le seul a me prendre la tete la dessus (bien que j'ai arreté de le faire depuis quelques semaines deja :p )


Posted by: sengirs

bijour, il y a u ne chose qui m'echape, comment faire pour connaitre la boule la plus legere lorsque l'on a 9 boules????
(boushra a ecrit "Par exemple: en 2 pesées, on peut trouver la boule la plus légère parmi 9 boules.")
j'ai beau chercher je ne trouve pas la solution...
merci


Posted by: Patastronch

3 tas de 3 boules.

premiere pesée 3 boules avec 3.

Si ca ne penche pas : la boule légère se trouve dans les trois dernieres, trivial en une pesée pour déterminer la boule exacte.

Si ca penche : la boule légère se trouve dans les trois boules du coté où ca ne penche pas,trivial également en une pesée.


Posted by: sengirs

reslt
je croyais qu'on ne savait pas si la boule etait plus ou moins lourde?
Car dans ce cas,Pour 9 boules, il faut 3 pesées minimum pour connaitre la boule differente.
Cordialement.


Posted by: Alpha

Effectivement,

je confirme ce que dit sengirs : dans l'énoncé, il n'est nulle part dit que la boule est plus légère, au contraire, il est précisé qu'elle est soit plus lourde, soit plus légère. Donc, dans le 2ème cas, si ça penche, on ne peut pas savoir de quel côté se trouve la boule anormale : disons par exemple que ça penche à gauche, alors :

-soit la boule anormale est plus lourde que les autres et elle se trouve à gauche
-soit elle est plus légère que les autres, et elle se trouve à droite.

Cordialement,

Alpha


Posted by: Patastronch

Oui mais faudrait lire et comprendre ce que l on dit avant de crier au loup.
Dans l etape ou on dit ca on en déduit qu'elle est legere et qu elle est parmis 9 boules :

on a pesé : 4(L)+9(N) d'un coté et 9(L)+4(l)

Donc si ca penche a droite : c'est que la boule est plus lourde et est parmis 9 boules (cas identique a celui sur lequel vous vous posiez la question). On sait donc a partir de maintenant que la boule est plus lourde si on arrive dans un cas comme ca et que ca penche a droite.

Je vous met au défi de dire qu on a dit qu'il etait possible de trouver en 2 pesées pour 9 boules sans savoir si la boule est plus lourde ou plus legere.
Si c'est pas le cas faudra m'expliquer la question de Sengir.

Cordialement.


Posted by: Patastronch

Citation:
Posté par sengirs
bijour, il y a u ne chose qui m'echape, comment faire pour connaitre la boule la plus legere lorsque l'on a 9 boules????
(boushra a ecrit "Par exemple: en 2 pesées, on peut trouver la boule la plus légère parmi 9 boules.")
j'ai beau chercher je ne trouve pas la solution...
merci



D'ailleur relis toi meme ta question.


Posted by: sengirs

Ok patastronch , le nombre de pesées necessaires a trouver une boule DIFFERENTE des 12 autres est 4 n'est ce pas???
cordialement.


Posted by: Bouchra

Non, c'est 3 .


Posted by: sengirs

c'est bon ok .....merci


Posted by: Patastronch

Edit :

Oups rien dit.

On t as deja répondu j avais pas vu.


Posted by: ffpower

Désolé de remonter un si vieux topic,mais ca m a interpellé car tout le monde semble d accord pour dire qu on ne peut pas resoudre le probleme en 3 pesées si on a 13 boules,alors que moi,je crois avoir réussi(et si je fais un nouvau topic,on va me dire qu il y a déja des topics la dessus..)

Voila comment je procede(ya p-e une erreur mais je la vois pas..)
Je prend les memes notations que Zebulon:
N:piece neutre(cad qui n est pas celle ayant un poids different)
S+:piece succeptible d etre plus lourde
S-:piece succeptible d etre plus legere

Je commence comme avec le probleme des 12 boules,j en met 4 de chaque coté.

-Si la balance n est alors pas équilibrée,on peut alors poursuivre comme dans le probleme des 12 boules.

-Si elle est équilibrée:la boule cherchée est donc parmi les 5 qui restent.J en prend 3 et j en prend une neutre dans les 7 autres.J en met 2 de chaque coté
de la balance

--Si la balance est équilibrée,la boule chechée est dans les 2 qui restent,et on la trouve en une pesée

--Si la balance n est pas équilibrée,on vire la boule neutre dans les 4 boules pesées,la boule cherchée est dans les 3 qui restent.De plus on a soit une S+ et 2 S-,soit 1 S- et 2 S+...De toute facon,on prend une S+ et une S- que l on met sur un plateau et 2 N que l on met sur l autre plateau

---Si c est pas équilibré,on sait que la boule cherchee est la S+ ou la S- selon comment le plateau penche

---Si c est équilibré,c est la boule qui reste

Voila,dites moi ce que vous en pensez


Posted by: Patastronch

Citation:
Posté par ffpower
--Si la balance est équilibrée,la boule chechée est dans les 2 qui restent,et on la trouve en une pesée


Ah et comment tu fait ?

J'avais trouvé (voir plus haut) qu'on pouvait toujours peser \frac{3^P-3}{2} boules en P pesées et y arriver. Soit 0 boules pour 1 pesée (ca veut pas dire que plus est impossible, j'ai pas trouvée de démo pour prouver que c'est max). Dans tous les cas ca demande une explication ton truc vu que ca pas été prouvé, si t'arrives a faire plus de boules en une pesée dit comment tu fait mais ca me parait juste impossible. Tu me diras que t es pas dans une situation de départ car tu dispose de boules dont on sait qu'elles sont normales. Dans ce cas pas de probleme dit moi comment tu fait en une seule pesée pour déterminer laquelle des 2 est différente et dire si elle est plus lourde/legere.

La question est toujours pas résolu : combien de boules peut on peser au maximum pour P pesées. On en est a \frac{3^P-3}{2} mais on a pas prouvé que c'était maximum. Donc rien ne dit qu'on ne peut pas faire mieu, et si on ne peut pas reste a le prouver :)

P.S: ca c'est un beau détérage de topic ! 2 ans!


Posted by: ffpower

Je suis tombé sur ce topic en les classant par notes^^.

Quand tu sais que la boule cherchée est parmi 2,c est evidemment impossible sauf si il y a des boules neutres a coté,ce qui est le cas ici:donc tu en prend une parmi les 2 que tu compares avec une neutre.Si la balance s equilibre,c est que la boule chechee est celle que tu n as pas pesee,sinon,c est que c est l autre(celle que tu viens de comparer a la neutre..)

Je reflechirai voir si je peux ameliorer la formule generale^^


Posted by: Patastronch

Non car dans le cas ou ca s'equilibre tu peux pas dire si la boule est plus lourde ou plus legere, donc ca marche pas.


Posted by: ffpower

Ah pardon,j avais mal lu l enoncé..Bon ben tu dois avoir raison alors,j ai uppé un topic de 2 ans pour rien


Posted by: Patastronch

Ben ca veut pas dire que c'est pas possible, tant qu'on a pas la démonstration que \frac{3^P-3}{2} est le nombre maximale de boules pesable en P pesées, tout est envisageable à priori.


Posted by: ffpower

P-e qu il y a une formule plus optimale que la tienne(j y reflechirai,comme ca le up sera p-e pas inutile^^),mais dans le cas des 13 boules,on a vite fait le tour de ttes les possibilités..


Posted by: Patastronch

Citation:
Posté par ffpower
P-e qu il y a une formule plus optimale que la tienne(j y reflechirai,comme ca le up sera p-e pas inutile^^),mais dans le cas des 13 boules,on a vite fait le tour de ttes les possibilités..

a l'époque j'etais tombé sur un site qui prouvait qu'on pouvait pas faire 13 boules en 3 pesées. Mais ca ne prouve pas pour autant l'optimalité de la formule citée au dessus.


Posted by: ffpower

Apres avoir réfléchi un ptit moment,je suis effectivement moi aussi sur la meme formule que toi,et je crois en avoir prouvé l optimalité:

Pour les notations,je garde toujours les memes(histoire de pas embrouiller^^):
Une boule est S+ si on sait que si c est la boule de poids different,alors elle est plus lourde
Une boule est S- si on sait que si c est la boule de poids different,alors elle est plus legere
Une boule est neutre ou N si on sait que ce n est pas la boule de poids différent
(Remarque:si une boule est a la fois S+ et S-,alors elle est en fait neutre..)

Je procede en plusieurs étapes:

Etape 1
Soit u_n le nombre maximal de boules tel que le probleme ait une solution en n pesée,mais en ayant en plus une information sur un caractere S+ ou S- pour chaque boule(cas plus general que si l on sait que la boule cherchee est plus lourde ou plus legere,qui correspond a "toutes les boules sont S+" ou "toutes les boules sont S-),et en ayant de plus a disposition a coté autant de boules neutres que l on souhaite..

Apres la premiere premiere pesee:
-Soit la balance est équilibrée,et la boule cherchée est dans celles qui restent
-Soit la balance n est pas équilibrée:la boule cherchée est donc dans les boules pesées,et on peut éliminer alors les boules qui deviennent a la fois S+ et S- donc neutres,mais on a pas de nouvelles infos sur les autres

Cette pesée permet donc juste d isoler la boule cherchée parmi 3 tas.L un de ces 3 tas est de cardinal superieur a u_n/3 ,donc on a forcément u_n\leq 3u_{n-1} ,et par récurrence directe,u_n\leq 3^n (u_0=1 )


Etape 2
Soit maintenant v_n le nombre maximal de boules tel que le probleme ait une solution en n pesée,en ayant cette fois aucune info sur ces boules,mais en ayant toujours a disposition a coté autant de boules neutres que l on souhaite

Apres la premiere pesée:
-Si la balance est équilibrée:la boule cherchée est dans les boules non pesées,et on aucune info supplémentaires sur ces boules,donc il faut qu il y en ait moins de v_{n-1}
-Si la balance n est pas équilibrée,on gagne seulement une info sur un caractere S+ ou S- pour chaque boule pesée,il faut donc que le nombre de boules(non neutres) pesées soit inferieur a u_{n-1}

On a donc v_n\leq v_ {n-1}+u_{n-1}\leq v_{n-1}+3^{n-1} ,puis par récurrence(v_0=0,v_1=1),on obtient v_n\leq3^{n-1}+3^{n-2}+...+1=\frac{3^n-1}{2}


Etape 3
Soit enfin w_n le nombre maximal de boules tel que le probleme ait une solution en n pesée,en ayant cette fois aucune info sur ces boules,et en ayant aucune boule neutre disponible

Apres la premiere pesée:
-Si la balance est équilibrée:la boule chechée est parmi les boules restantes,et on a aucune info sur ces boules,seulement des boules neutres maintenant disponibles(celles que l onvient de peser),le nombre de boules restantes doit donc etre inferieur a v_{n-1}=\frac{3^{n-1}-1}{2}
-Si la balance n est pas équilibrée:la boule cherchée est dans les boules pesées,on a maintenant une info S+ ou S- sur ces boules,et les boules restantes disponibles comme boules neutres.Le nombre de boules pesées doit doit etre inferieur a u_{n-1}=3^{n-1}.Comme le nombre de boules pesées doit de plus etre pair,si n\geq 2 ,le nombre de boules pesées doit en fait etre inferieur a 3^{n-1}-1

On a donc finalement u_n\leq \frac{3^{n-1}-1}{2}+3^{n-1}-1=\frac{3^n-3}{2}

Voila,dis moi ce que tu en pense ou si quelque chose ne te semble pas clair.Pour l algo correspondant,j ai la flemme de l ecrire pour l instant,mais je suppose qu on a a peu pres le meme..


Posted by: carlo90

Il me semble avoir prouvé pour 40 boules, en 4 pesées.
J'ai fait un schéma :
P1, P2, P3, et P4 sont les pesées, et quand P3=x, par exemple, c'est qu'on a trouver la boule à chercher à la troisième pesée.

http://nsa01.casimages.com/img/2008...08022787650.jpg

:)

En clair :
D'abord je fais 3 tas : un de 16 boules et deux de 12.
Puis je pèse les 2 de 12.

Si la boule est dans un tas de 12, je le divise en trois, puis je compare deux de ces trois tas de 4 boules. Puis je prends le tas de 3 boules restant, et je compare deux de ces boules... J'obtient la boule recherchée.

Si la boule recherchée est dans le tas de 16, je le divise aussi en trois : deux tas de 5, un tas de 6. Je pèse les deux tas de 5. Si la boule est dans le tas de 6, je le redivise en trois tas de 2, je pèse, et j'obtiens la boule.
Sinon, s'il est dans un tas de 5, je le divise en deux tas de 2 que je pèse, plus une boule. Si les deux boules ont même poids, la boule cherchée est la boule restante. Sinon, il faut peser le tas de 2 boules ayant la boule cherchée, et on obtient celle-ci :)


Posted by: Patastronch

Citation:
Posté par carlo90
Il me semble avoir prouvé pour 40 boules, en 4 pesées.
J'ai fait un schéma :
P1, P2, P3, et P4 sont les pesées, et quand P3=x, par exemple, c'est qu'on a trouver la boule à chercher à la troisième pesée.

http://nsa01.casimages.com/img/2008...08022787650.jpg

:)

En clair :
D'abord je fais 3 tas : un de 16 boules et deux de 12.
Puis je pèse les 2 de 12.

Si la boule est dans un tas de 12, je le divise en trois, puis je compare deux de ces trois tas de 4 boules. Puis je prends le tas de 3 boules restant, et je compare deux de ces boules... J'obtient la boule recherchée.

Si la boule recherchée est dans le tas de 16, je le divise aussi en trois : deux tas de 5, un tas de 6. Je pèse les deux tas de 5. Si la boule est dans le tas de 6, je le redivise en trois tas de 2, je pèse, et j'obtiens la boule.
Sinon, s'il est dans un tas de 5, je le divise en deux tas de 2 que je pèse, plus une boule. Si les deux boules ont même poids, la boule cherchée est la boule restante. Sinon, il faut peser le tas de 2 boules ayant la boule cherchée, et on obtient celle-ci :)


En rouge: Je vois pas comment tu determines la boule en 2 pesées avec 6 boules.

En vert : Je vois pas comment tu determines la boule en 1 pesée avec 2 boules.

Je rappelle qu'on doit egalement pouvoir dire si elle est plus lourde ou plus legere.


Posted by: Patastronch

Citation:
Posté par ffpower
...


J'ai pas tout lu en détail mais l'idée de la démo est la je pense. Je regarderai plus en détail a tête reposée plus tard.


Posted by: ffpower

Lol,tu aura donc finalement vu mon post^^










-