Trois pesées suffisent !

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

Avec 12 boules dont une intruse, trois pesées suffisent-elles pour identifier l’intruse et déterminer si elle est plus lourde ou plus légère ?

Combien de pesées sont nécessaires si on dispose de n boules ?

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

1/A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

2/Avec 12 boules dont une intruse, trois pesées suffisent-elles pour identifier l’intruse et déterminer si elle est plus lourde ou plus légère ?

3/Combien de pesées sont nécessaires si on dispose de n boules ?

1/on tire une boule et on pese 8 si le balance et equilibrés alors c la boule qu'on a tiré si non on prend les 4boule qui ont plus lourd alors on les péses autre fois ,les 2boule plus lourd on les prend et on les pése la 3éme fois alors la plus lourde on la prend c la boule cherché .

2/oui il suffit: en pése les 12 boule et on les repartie en ensemble de 4 - 4 - 4 en pese la 1er fois les deux 4boule si il sont equilibrés alors on prend les 4restantes et on continue a pésé 2 a 2 puis 1 et1 pour trouvez la boule cherche. si non la balance n'est pas equilibré alors on prend les 4plus lourde et on continue les meme etapes que les autre qu'on a laissé. et on trouve la boule cherché .
3/ pour demai1:)

BeStFrIeNd a écrit:

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

1/A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

2/Avec 12 boules dont une intruse, trois pesées suffisent-elles pour identifier l’intruse et déterminer si elle est plus lourde ou plus légère ?

3/Combien de pesées sont nécessaires si on dispose de n boules ?

1/on tire une boule et on pese 8 si le balance et equilibrés alors c la boule qu'on a tiré si non on prend les 4boule qui ont plus lourd alors on les péses autre fois ,les 2boule plus lourd on les prend et on les pése la 3éme fois alors la plus lourde on la prend c la boule cherché .

2/oui il suffit: en pése les 12 boule et on les repartie en ensemble de 4 - 4 - 4 en pese la 1er fois les deux 4boule si il sont equilibrés alors on prend les 4restantes et on continue a pésé 2 a 2 puis 1 et1 pour trouvez la boule cherche. si non la balance n'est pas equilibré alors on prend les 4plus lourde et on continue les meme etapes que les autre qu'on a laissé. et on trouve la boule cherché .
3/ pour demai1:)

nn on sait pas si la boule cherchée est lourde ou legere

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.
A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

Combien de pesées sont nécessaires si on dispose de n boules ?

je crois que 2 pesée sont amplement suffisantes:
on divise à 3-3-3, on pèse 6 boules, si il y a un équilibre ce sont les 3 boules non pesées, puis on reprend avec 1-1-1

Salut Codex00

codex00 a écrit:

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

je crois que 2 pesée sont amplement suffisantes:
on divise à 3-3-3, on pèse 6 boules, si il y a un équilibre ce sont les 3 boules non pesées, puis on reprend avec 1-1-1

Non, tu supposes connaître si la boule anormale est plus lourde ou plus légère, ce qui est contradictoire avec l'énoncé.
Il faut de toutes façons au moins 3 pesées puisque on a 18 cas (1+lourde, 1+légère, 2+lourde, 2+légère, ..., 9+lourde, 9+légère) et que chaque pesée ne donne que 3 cas différents (<,=,>). Deux pesées donnent donc 9 cas différents qui ne peuvent discriminer 18 possibilités.

--
Patrick

Conan a écrit:

nn on sait pas si la boule cherchée est lourde ou legere

Mais j'(ai demontrer coment fesant pour la connaitre tu vois PAs? ..

Salut Bestfriend,

BeStFrIeNd a écrit:

Mais j'(ai demontrer coment fesant pour la connaitre tu vois PAs? ..

Non, ta démonstration suppose que la boule anormale est plus lourde (tu prends à chaque fois la pesée la plus lourde) mais on ne sait pas si la boule anormale est plus lourde ou plus légère (on demande même de le déterminer) donc ta méthode ne fonctionne pas.

Désolé.

--
Patrick

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

on divise les 9 boules en 3 groupe de A,B,C tel que card(A)=card(B)=card(C)=3.
1er operation: comparer les poids de A et B.
2eme operation: comparer les poids de A et C.

on va trouver deux groupe qui ont le meme poid et un qui est plus lourde (ou bien plus legere)

3eme operation: on prend les 3 boules du groupe qui est plus lourde (ou bien plus legere).
on compare 2 boules, s'ils ont le meme poid alors la 3eme est la boule cherche et il est la plus lourd (resp. plus legere)
sinon la plus lourde est la boule cherche et il est la plus lourd bien sure parmi tous les boules (resp. la plus legere est la boule cherche et il est la plus legere parmi tous les boules)

encore un petit effore !!!

.

BeStFrIeNd a écrit:

pilot_aziz a écrit:

Conan a écrit:

On dispose de 9 boules d’aspect identique et l’un d’entre elles est d’un poids différent mais on ne sait pas si elle est plus lourde ou plus légère.

A l’aide de trois pesées d’une balance Roberval, comment identifier la boule intruse et déterminer si elle est plus lourde ou plus légère.

on divise les 9 boules en 3 groupe de A,B,C tel que card(A)=card(B)=card(C)=3.
1er operation: comparer les poids de A et B.
2eme operation: comparer les poids de A et C.

on va trouver deux groupe qui ont le meme poid et un qui est plus lourde (ou bien plus legere)

3eme operation: on prend les 3 boules du groupe qui est plus lourde (ou bien plus legere).
on compare 2 boules, s'ils ont le meme poid alors la 3eme est la boule cherche et il est la plus lourd (resp. plus legere)
sinon la plus lourde est la boule cherche et il est la plus lourd bien sure parmi tous les boules (resp. la plus legere est la boule cherche et il est la plus legere parmi tous les boules)

Et Si la plus lourde ou l aplus légere se trouve dans le groupe A !! alors l'equilibrage du balance n'arrive pas dans les 2 operation!!! alors il mank klk chose DAns Votre demonstration:bounce:

nn c tout a fait juste ! car avec ces deux premiers pesés , il va savoir ou se trouve le plus lourde ou la plus legere dans trois boule , ensuite il va peser deux de cest trois (car maintenant il sais s'elle est lourde ou legere)
et il deduit

alors passons aux cas plus defficile avec 12 boules !!!

Bonjour à ous,

Voici une démonstration générale.

Proposition P1(n) : Si j'ai 3^n boules identiques sauf une, inconnue, plus lourde ou plus légère (sans que je sache si c'est lourde ou légère), je peux déterminer la boule anormale parmi les 3^n et son type (plus lourde ou plus légère) en au plus n+1 pesées de Roberval.

Proposition P2(n) : Si j'ai un premier groupe de 3^n boules et un deuxième groupe de 3^n, ces deux groupes étant constitués de boules identiques sauf une, inconnue, plus lourde ou plus légère (sans que je sache si c'est lourde ou légère), ET que je sais que le premier groupe est plus lourd que le second, je peux déterminer la boule anormale parmi les 2*3^n et son type (plus lourde ou plus légère) en au plus n+1 pesées de Roberval.

On peut démontrer ces deux propositions par récurrence sur n.
P1(1) : 3 boules A, B et C
Peser A contre B.
En cas d'égalité, A et B sont normales et C est anormale. La pesée A contre C permet de déterminer le type de l'anomalie de C.
En cas d'inégalité, mettons A > B, on a soit A_Lourd, soit B_Légère et C normale. On pèse alors A contre C. L'égalité permet de conclure B_Légère, l'inégalité (nécessairement A plus lourd) permet de conclure A_Lourd.
Donc P(1) est résoluble en 2 pesées.

P2(1) : 3 boules ABC plus lourdes que 3 autre boules DEF
Peser AD contre BE
En cas d'égalité, l'anomalie est entre C et F et on a nécessairement ABDE normales et soit C_Lourd, soit F_Légère. Une deuxième pesée entre A et C permet de déterminer entre C_Lourd et F_Légère.
Si AD > BE, on a nécessairement A_Lourd ou E_Légère. Une deuxième pesée entre A et B permet de discriminer.
Si AD < BE, on a nécessairement D_Légère ou B_Lourd. Une deuxième pesée entre A et B permet de discriminer.
Donc P2(1) est résoluble en 2 pesées.

Soit maintenant n >= 2 tel que P1(n) et P2(n) soit bien résolubles en au plus n+1 pesées

P1(n+1) : Je découpe mes 3^(n+1) boules en 3 groupes G1, G2, G3 de 3^n boules chacun. Je pèse G1 contre G2.
Si G1 = G2 je suis ramené à P1(n) avec le groupe G3 ==> n+2 pesées au total
Si G1 > G2 je suis ramené à P2(n) avec G1,G2 ==> n+2 pesées
Si G1 < G2 je suis ramené à P2(n) avec G2,G1 ==> n+2 pesées
CQFD

P2(n+1) : J'ai G1 > G2. Je découpe G1 en 3 groupes de 3^n boules G11, G12, G13. Je pécoupe G2 en 3 groupes de 3^n boules G21, G22 et G23.
Je pèse G11+G21 contre G12+G22
Si égalité, l'anomalie est dans G13 ou G23 et j'ai bien sûr G13 > G23. Je suis donc ramené à P2(n) avec G13,G23 ==> n+2 pesées
Si G11+G21 > G12+G22, j'ai nécessairement G11 > G22. Je suis donc ramené à P2(n) avec G11,G22 ==> n+2 pesées
Si G11+G21 < G12+G22, j'ai nécessairement G12 > G21. Je suis donc ramené à P2(n) avec G12,G21 ==> n+2 pesées
CQFD

=======================
Par ailleurs, le problème de 3^n boules ne peut se résoudre en moins de n+1 pesées.
En effet, chaque pesée donne 3 cas (< = >) et p pesées permettent au mieux de discriminer 3^p cas.
Or, 3^n boules donnent 2*3^n cas (1_Lourd, 1_Légère, 2_Lourd, 2_Légère, ... 3^n_Lourd, 3^n_Légère). Il faut donc p tel que 3^p >= 2*3^n, soit p >= n + log3(2), soit p >= n+1
CQFD.

Comme on a déterminé (P1(n)) que la détermination pouvait se faire en n+1 pesées et comme il en faut au moins n+1, on peut conclure :
La détermination de la boule anormale ET de son type (plus lourde, plus légère) parmi 3^n boules peut se faire en n+1 pesées et ne peu se faire en moins.

Il reste ensuite le cas de p boules, avec 3^n> p > 3^(n-1).
Il est clair que l'on peut déterminer en n+1 pesées.
Il est clair qu'il doit être possible de déterminer en n pesées dans certains cas (en tous cas pas si log3(p) + log3(2) > n)

La question de savoir s'il est nécesssairement possible de déterminer en n pesées si log3(p) + log3(2) <= n reste - en ce qui me concerne - à creuser.

=====================

Les questions posées :
Avec 9 boules, on est exactement dans le cas P1(2) ==> 3 pesées et pas moins
Avec 12 boules, on est dans le cas où log3(12) + log3(2) < 3 et il ne me semble pas que l'on puisse traiter le cas en 3 pesées (on le peut évidemment en 4).


--
Patrick

pco a écrit:

Bonjour à ous,

Voici une démonstration générale.

Proposition P1(n) : Si j'ai 3^n boules identiques sauf une, inconnue, plus lourde ou plus légère (sans que je sache si c'est lourde ou légère), je peux déterminer la boule anormale parmi les 3^n et son type (plus lourde ou plus légère) en au plus n+1 pesées de Roberval.

Proposition P2(n) : Si j'ai un premier groupe de 3^n boules et un deuxième groupe de 3^n, ces deux groupes étant constitués de boules identiques sauf une, inconnue, plus lourde ou plus légère (sans que je sache si c'est lourde ou légère), ET que je sais que le premier groupe est plus lourd que le second, je peux déterminer la boule anormale parmi les 2*3^n et son type (plus lourde ou plus légère) en au plus n+1 pesées de Roberval.

On peut démontrer ces deux propositions par récurrence sur n.
P1(1) : 3 boules A, B et C
Peser A contre B.
En cas d'égalité, A et B sont normales et C est anormale. La pesée A contre C permet de déterminer le type de l'anomalie de C.
En cas d'inégalité, mettons A > B, on a soit A_Lourd, soit B_Légère et C normale. On pèse alors A contre C. L'égalité permet de conclure B_Légère, l'inégalité (nécessairement A plus lourd) permet de conclure A_Lourd.
Donc P(1) est résoluble en 2 pesées.

P2(1) : 3 boules ABC plus lourdes que 3 autre boules DEF
Peser AD contre BE
En cas d'égalité, l'anomalie est entre C et F et on a nécessairement ABDE normales et soit C_Lourd, soit F_Légère. Une deuxième pesée entre A et C permet de déterminer entre C_Lourd et F_Légère.
Si AD > BE, on a nécessairement A_Lourd ou E_Légère. Une deuxième pesée entre A et B permet de discriminer.
Si AD < BE, on a nécessairement D_Légère ou B_Lourd. Une deuxième pesée entre A et B permet de discriminer.
Donc P2(1) est résoluble en 2 pesées.

Soit maintenant n >= 2 tel que P1(n) et P2(n) soit bien résolubles en au plus n+1 pesées

P1(n+1) : Je découpe mes 3^(n+1) boules en 3 groupes G1, G2, G3 de 3^n boules chacun. Je pèse G1 contre G2.
Si G1 = G2 je suis ramené à P1(n) avec le groupe G3 ==> n+2 pesées au total
Si G1 > G2 je suis ramené à P2(n) avec G1,G2 ==> n+2 pesées
Si G1 < G2 je suis ramené à P2(n) avec G2,G1 ==> n+2 pesées
CQFD

P2(n+1) : J'ai G1 > G2. Je découpe G1 en 3 groupes de 3^n boules G11, G12, G13. Je pécoupe G2 en 3 groupes de 3^n boules G21, G22 et G23.
Je pèse G11+G21 contre G12+G22
Si égalité, l'anomalie est dans G13 ou G23 et j'ai bien sûr G13 > G23. Je suis donc ramené à P2(n) avec G13,G23 ==> n+2 pesées
Si G11+G21 > G12+G22, j'ai nécessairement G11 > G22. Je suis donc ramené à P2(n) avec G11,G22 ==> n+2 pesées
Si G11+G21 < G12+G22, j'ai nécessairement G12 > G21. Je suis donc ramené à P2(n) avec G12,G21 ==> n+2 pesées
CQFD

=======================
Par ailleurs, le problème de 3^n boules ne peut se résoudre en moins de n+1 pesées.
En effet, chaque pesée donne 3 cas (< = >) et p pesées permettent au mieux de discriminer 3^p cas.
Or, 3^n boules donnent 2*3^n cas (1_Lourd, 1_Légère, 2_Lourd, 2_Légère, ... 3^n_Lourd, 3^n_Légère). Il faut donc p tel que 3^p >= 2*3^n, soit p >= n + log3(2), soit p >= n+1
CQFD.

Comme on a déterminé (P1(n)) que la détermination pouvait se faire en n+1 pesées et comme il en faut au moins n+1, on peut conclure :
La détermination de la boule anormale ET de son type (plus lourde, plus légère) parmi 3^n boules peut se faire en n+1 pesées et ne peu se faire en moins.

Il reste ensuite le cas de p boules, avec 3^n> p > 3^(n-1).
Il est clair que l'on peut déterminer en n+1 pesées.
Il est clair qu'il doit être possible de déterminer en n pesées dans certains cas (en tous cas pas si log3(p) + log3(2) > n)

La question de savoir s'il est nécesssairement possible de déterminer en n pesées si log3(p) + log3(2) <= n reste - en ce qui me concerne - à creuser.

=====================

Les questions posées :
Avec 9 boules, on est exactement dans le cas P1(2) ==> 3 pesées et pas moins
Avec 12 boules, on est dans le cas où log3(12) + log3(2) < 3 et il ne me semble pas que l'on puisse traiter le cas en 3 pesées (on le peut évidemment en 4).


--
Patrick

nn pco : on peut traiter le cas 12 avec seulement trois pesés, à toi de jouer

Conan a écrit:

nn pco : on peut traiter le cas 12 avec seulement trois pesés, à toi de jouer

on regroupe les 12 boules en groupe de (G1) 9-(G2) 3
1erment en repartie aussi les 9 au groupe de A *3 -B *3-c *3 alors en pése A et B
et A et C
si la balance reste equilibrés alors la boles cherché et resté avec le Groupe G2 alors en tire une une et en pése les autre si il sont equilibrés la boule cherché c qui est a notre main si non on va prendre un des deux boule (LA plus légé ou la plus lourd)

SI non SI la pésé de A et B et A et C sont pas equilibrés alors on continue avec la meme methode que pilot_aziz a dit..

BeStFrIeNd a écrit:

Conan a écrit:

nn pco : on peut traiter le cas 12 avec seulement trois pesés, à toi de jouer

on regroupe les 12 boules en groupe de (G1) 9-(G2) 3
1erment en repartie aussi les 9 au groupe de A *3 -B *3-c *3 alors en pése A et B
et A et C
si la balance reste equilibrés alors la boles cherché et resté avec le Groupe G2 alors en tire une une et en pése les autre si il sont equilibrés la boule cherché c qui est a notre main si non on va prendre un des deux boule (LA plus légé ou la plus lourd)

SI non SI la pésé de A et B et A et C sont pas equilibrés alors on continue avec la meme methode que pilot_aziz a dit..

mais là, tu as fini les 3 pesés , et tu as deux boule une lourde et l'autre legere !!!!

Hello,

BeStFrIeNd a écrit:

on regroupe les 12 boules en groupe de (G1) 9-(G2) 3
1erment en repartie aussi les 9 au groupe de A *3 -B *3-c *3 alors en pése A et B
et A et C
si la balance reste equilibrés alors la boles cherché et resté avec le Groupe G2 alors en tire une une et en pése les autre si il sont equilibrés la boule cherché c qui est a notre main

Non,

Car tu as fait tes 3 pesées et la boule qui est dans t main est bien anormale mais tu ne sais pas si elle est plus lourde ou plus légère. Tu n'as donc pas résolu le problème.


--
Patrick

Salut,

Solution pour 12 boules en 3 pesées.
Les boules : ABCDEFGHIJKL
Quand je note A+ ou A-, je signifie A_Lourde ou A_Légère

Pesée 1 : ABCD contre EFGH
1) Si ABCD=EFGH, la boule anormale est dans IJKL, effectuer alors la pesée IJ contre AK
1.1) Si IJ = AK, la boule anormale est L+ ou L- et une pesée A L permet de déterminer la solution
1.2) Si IJ > AK, on a I+ ou J+ ou K-. Il suffit de peser I et J pour discriminer (I>J ==> I+, I<J ==> J+, et I=J ==> K-)
1.3) si IJ < AK, on a I- ou J- ou K+. Il suffit là encore de peser I contre J pour trouver la réponse (I>J ==> J-, I<J ==> I-, et I=J ==> K+)

2) Si ABCD > EFGH, on a A+ ou B+ ou C+ ou D+ ou E- ou F- ou G- ou H-
Effectuer alors la pesée ABE contre CDF
2.1) ABE=CDF ==> on a G- ou H-. On discrimine en pesant G H
2.2) ABE>CDF ==> on a A+, B+ ou F-. On discrimine en pesant A contre B (A>B ==> A+, A<B ==> B+, A=B ==> F-)
2.3) ABE < CDF ==> on a E-, C+ ou D+. On discrimine en pesant C contre D (C>D ==> C+, C<D ==> D+, C=D ==> E-)

3) Si ABCD < EFGH : même cas que 2)

--
Patrick