Les 12 boules.

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

[Patastronch]

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.

[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 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 ,donc on a forcément ,et par récurrence directe, ( )


Etape 2
Soit maintenant 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
-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

On a donc ,puis par récurrence(),on obtient


Etape 3
Soit enfin 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
-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 .Comme le nombre de boules pesées doit de plus etre pair,si ,le nombre de boules pesées doit en fait etre inferieur a

On a donc finalement

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

[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/03/30/0803301208022787650.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

[Patastronch]

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/03/30/0803301208022787650.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.

[Patastronch]

...

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.

[ffpower]

Lol,tu aura donc finalement vu mon post^^

[Bouchra]

Bonjour,
Je fais remonter le topic à mon tour !

La conjecture de Patastronch est vraie : Le nombre maximal de boules pesables en n pesées est bien (3^n-3)/2.
Apparemment, la démonstration est dans "Les casse-têtes logiques" de Baillif :
http://www.diophante.fr/A7.-Problemes-de-pesees/A706.-Trois-pesees-suffisent.html
Peut-être que la démonstration est sur le modèle de ffpower ...