Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 23-07-2013 16:10:05

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore un histoire de boules et de pesées

Hello!

http://3.bp.blogspot.com/-_MM1FO-wDhM/UF8xsIUjHaI/AAAAAAAAAZ8/AEyrePB__cQ/s320/compendium_metrique_balance_roberval_dessin_daguin.jpg
Ci dessus l'image qui ne sert à rien mais qui donne toujours plus envie de lire l’énigme.

En revoyant ces variations sur le problème des boules et des pesées j'ai envie de vous proposer quelque chose de plus formel et moins empirique qu'habituellement.
Rappel de la forme générique du problème original:
On dispose d'une balance deux plateaux, et il faut trouver l'unique boule intruse de poids différent (plus lourde ou plus légère on ne sait pas) en un nombre minimum de pesées parmi un certain nombre de boules.

Ce qui est intéressant c'est d'avoir une vision "récursive" du problème et une manière mécanique de l'aborder. Pourquoi récursive? parce qu’on sent bien que pour résoudre le problème avec un certain nombre de boules on peut avoir intérêt à savoir le résoudre pour un nombre plus faible. Pour pouvoir faire une récursion, il faut souvent généraliser le problème, c'est le cas ici, il se ramène à la question suivante:

"Étant donnée les informations dont on dispose, quel est le nombre minimal de pesées nécessaires pour trouver la boule problématique?"

L’énoncé original n'est qu'un cas particulier de cette question ou les informations disponibles sont pour le moment inexistantes, chaque pesée réalisée et leur issue va faire évoluer ces informations.

Une manière "bête" (mais qui marche toujours) de représenter les informations dont on dispose consiste à simplement avoir un historique des pesées déjà réalisées et de leur issue. Mais dans le cadre particulier du problème original il y a bien moins d'information que ceci à stocker!, d’où la premier question:

Question 1:
Toujours dans le cadre du problème original, quels informations au minimum faudrait il choisir de garder en mémoire pour avoir par la suite la possibilité de faire les même déductions que si on connaissait précisément l'historique de chaque pesée réalisée et de leur issue?
(NB: il est possible d'avoir une quantité d'information maximum indépendante du nombre de pesées déjà réalisées)
Voir d'un exemple en bas si après plusieurs lectures cette question n'est toujours pas claire.

Question 2, plus facile:
Lister les axiomes de déduction, ie les règles qui disent comment faire évoluer les informations en fonction d'une pesée supplémentaire et de son issue.
(NB: souvent faire ensemble les questions 1 et 2 permet de trouver plus facilement les deux)

Lorsqu'on sait répondre à ces deux question vous remarquerez qu'on peut programmer la chose sans problème si on le désire et demander à notre copain ordi combien de pesée il faut pour trouver l'intruse parmi 121 boules.

Une question ouverte:
Dans le cadre du problème donné par PRINCELEROI "2 intruses" ici peut on trouver un modèle d'information ou comme ici la taille serait indépendante du nombre de pesée déjà réalisée?

Une question facultative de geek:
Est ce que j'ai dit 121 au pif? tongue

Voila voila bon courage aux matheux!

Exemple vulgarisé utile uniquement si la question 1 n'est pas claire:
Supposons que votre job consiste à dire quand il y a exactement 0 personnes dans un parking. On vous donne le nombre de personnes qu'il y a initialement dedans. Au fur et a mesure du temps on va vous indiquer que tant de personnes y entrent ou en sortent. Vous pourriez parfaitement noter sur une feuille tout ce qu'on vous dit et refaire systématiquement l'addition soustraction depuis le départ mais ce n'est évidemment pas génial. Le mieux est de ne mémoriser que le nombre actuel de personne dans le parking et le mettre a jour. Avoir cette information et uniquement cette information permet de dire lorsqu'il y a 0 personne dedans.
Et bien ce que la question 1 propose de faire c'est le même genre de chose mais avec le problème des pesées. Plutôt que de mémoriser toutes les pesées faites et leur issue depuis le départ il y a quelque chose de plus compact qu'on peut noter et pouvoir en déduire exactement autant.


Solution:

Spoiler : [Afficher le message]
Question 1 et 2:
A chaque boule on peut associer une valeur parmi un ensemble de quatre états:
-Bonne
-Bonne ou plus lourde
-Bonne ou moins lourde
-Pas d'information

Cette information, proportionnelle au nombre de boules, suffit à mener toutes les déductions possibles à l'issue d'une pesée en suivant les axiomes:

A1:
Lors d'une pesée équilibrée le boules sur la balance deviennent toutes bonnes.
A2: Lors d'une pesée déséquilibrée les boules en dehors de la balance deviennent toutes bonnes.
A3.a: Lors d'une pesée déséquilibrée les boules sans information du plateau le plus lourd deviennent bonnes ou plus lourdes.
A3.b: Lors d'une pesée déséquilibrée les boules sans information du plateau le plus léger deviennent bonnes ou moins lourdes.
A4.a: Lors d'une pesée déséquilibrée les boules bonnes ou moins lourdes du plateau le plus lourd deviennent bonnes.
A4.b: Lors d'une pesée déséquilibrée les boules bonnes ou plus lourdes du plateau le plus léger deviennent bonnes.

On commence bien sur au départ avec un ensemble de boules sans information.
On finit avec un ensemble de boules ou toutes sauf une sont bonnes.

Une autre excellente manière de voir le problème suggérée par gwen27 consiste à envisager l'ensemble des cas possibles. Pour notre problème, et avec N boules, il y a 2N cas possibles. (ie, soit la première est plus lourde soit la première est moins lourde soit la seconde...)
Une pesée ne fait que restreindre cette ensemble de cas possible. A l'issue de plusieurs pesées les cas possibles ne sont que l'intersection de l’ensemble des cas possibles à l'issue de chacune d’entre-elles.
D'un point de vu de la quantité d'information c'est exactement similaire à ce que j'ai dit plus haut.
Exemple pour 4 boules on peut noter ceci par un masque binaire 8bits correspondant aux possibilités 1+,2+,3+,4+,1-,2-,3-,4- au départ on commence avec 11111111 ce qui veut dire que tout est encore possible. (ie 10000001 voudrait dire, soit 1 est plus lourde soit 4 est moins lourde)
On remarque que la quantité d'information est proportionnelle au nombre de boules et que pour chaque boule il y a au total 2 bits codant donc 4 états, correspondant exactement aux mêmes cas que ceux énoncés plus haut.

Cette façon de voir les choses a l'avantage d’être extrêmement générique et permet de répondre trivialement à la question ouverte:
Oui c'est possible, mais avec une quantité d'information proportionnelle au nombre de couples de boules.(Donc totalement impossible en donnant des états à chaque boule)

Question facultative de geek:
J'ai dit 121 car c'est le nombre maximal de boules ou 5 pesées suffisent à trouver l’intrus, à partir de 122 6 pesées sont nécessaires.

  • |
  • Répondre

#0 Pub

 #2 - 23-07-2013 16:59:47

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

encore une histiire de boules et de pesées

Pour 1 et 2 boules, c'est impossible.
Pour 3 ou 4 boules, c'est deux pesées.
De 5 à 13 boules, c'est trois pesées.

Hum, difficile d'y voir une suite avec aussi peu d'éléments. Et la récursivité, je ne sais pas ce que c'est.

 #3 - 23-07-2013 17:14:29

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

encore une histoire de boules et de peqées

@Nombrilist (et peut être à d'autres): Le but du post n'est pas de trouver à la main la réponse générique au problème quelque soit le nombre de boules, ni la suite logique du nombre de pesées minimum. La première question du post c'est celle qui se nomme "question 1" tongue. Quant à récursivité ce n'est rien d'autre que ce que j'explique, c'est la mécanique qu'on fait lorsque pour résoudre un problème d'une certaine taille on appelle sa résolution sur une taille plus faible.

J'ai ajouté un "exemple" en bas du post initial pour mieux cerner la question 1 si c'est pas clair.

 #4 - 23-07-2013 18:51:56

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

encire une histoire de boules et de pesées

Bah c'est simple, je donne un rang à chaque possibilité et je code tout ça en binaire.

Mettons qu'il y ait n boules, j'ai 2n possibilités que je note 1 (potentiellement valables.

J'ai donc en tête 2^(2n) -1

Pour n= 4 : 11111111=2^8 -1 = 255
Si une pesée interdit 3 cas , je garde en tête 10100111 =  167

Le jeu finit quand j'obtiens une puissance de 2

 #5 - 23-07-2013 19:01:00

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore une histoire de boulees et de pesées

@Gwen27: Tu peux détailler comment tu obtiens ton codage?/ce qu'il veut dire?
Je ne suis pas sur de te suivre.

 #6 - 23-07-2013 19:04:40

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 568

Encore une ihstoire de boules et de pesées

OK merci j'ai compris. On crée un tableau de boules auquel on assigne des informations, style:

T[i].vraie (booléen, avec initialisation à "false" de toutes les boules)

Avec par exemple une mise à "true" si une pesée n'est pas équilibrée et que certaines boules n'ont pas été pesées (ces dernières sont forcément vraies).

On peut aussi assigner un poids:

T[i].poids (3 possibilités)

A chaque pesée, un algorithme va croiser les informations pour réduire le champs d'investigation. Bon quel algorithme, ça...

 #7 - 23-07-2013 19:14:11

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore une histoire de boules eet de pesées

@Nombrilist: C'est ça, quel algorithme oui mais aussi précisément quelles informations! Tu peux trouver ceci en cherchant la question 2 en même temps: si tu sais lister tous les genres de déductions que tu peux faire, tu sais ce dont tu auras besoin pour les faire. (Il n'y en a pas tant que cela)

 #8 - 23-07-2013 19:21:09

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encore une histoire de boules et dde pesées

Si j'ai 5 boules, je peux avoir 1+ 2+ 3+ 4+ 5+ 1- 2- 3- 4- 5-

1111111111

Je pèse 12 / 34 et ça penche à gauche
C'est donc que 1 ou 2 est plus lourde , ou bien 3 ou 4 est plus légère
Il me reste 1100000110

Si la balance était équilibrée, il me resterait 0000100001

 #9 - 23-07-2013 19:48:19

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore une ihstoire de boules et de pesées

@gwen27: Oui bravo! Maintenant si tu le souhaites tu peux réfléchir à comment une pesée transforme cette information en fonction de son issue (C'est peut être trivial). Ainsi que sur la condition de fin (qui n'est pas exactement celle que tu as dite mais la rectification est triviale).
PS: l'information que tu choisis de représenter est "mélangée" avec la manière dont tu l’implémentes, ça peut aider comme ça peut gêner je n'y ai pas encore réfléchi mais je l'indique juste. Il est possible que tu ai trouvé en plus de l'information exacte une implémentation très efficace, ça va me faire méditer. smile

 #10 - 23-07-2013 19:54:46

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encore une histoire de boules et de pesés

C'est vrai, s'il faut juste identifier, le résultat est une puissance de 2(1+2^n)

Pour l'exemple : 1000010000 ou 0100001000 .... Mais même si c'est le cas, il est plus facile , à mon avis de raisonner ainsi car cela permet de légitimer des OU plus facilement que 111111 au départ en codant l'intruse.

Une pesée à l'équilibre exclut 2 fois plus de cas que le nombre de boules sur la balance.

Une pesée déséquilibrée exclut 2 fois plus de cas que les boules hors de la balance PLUS autant de cas que de boules sur la balance.

C'est ce qui est utilisé dans le classique 1234 /5678 qui penche quand on a 12 boules avec pour seconde pesée 125 / 346.

Le premier raisonnement mène à 111111110000 (1/3 d'éliminé )

Le second à 111100000000000011110000 et ouvre la porte à des OU : 1 Lourde ou 6 légère ... etc. (2/3 d'éliminé)

Dans le premier  cas, on perd de l'information utile. En tout cas, j'essaye de raisonner comme ça quand je résouds ce type de problèmes et ça a l'air de marcher.

 #11 - 23-07-2013 20:45:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encore une histoire de buoles et de pesées

Le fait reste que n tel que 3^n soit supérieur ou égal  au double du nombre de boules est valide comme nombre de pesées car il est prouvé qu'une solution au moins est trouvable. Par contre la question peut être d'optimiser le nombre de pesées moyen, ou le nombre de boules sur la balance au final... Je pense que c'est là où ça nous mène.

 #12 - 24-07-2013 09:44:01

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

Encore une histoire de bouules et de pesées

Pour la question 1, au lieu de noter toutes les pesées on note par trois lettres les trois cas qui peuvent se produire : D, quand ça penche à droite, G, quand ça penche à gauche et E quand il y a égalité.

A suivre ....

 #13 - 24-07-2013 11:10:48

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

encore une histoire de biules et de pesées

@SabanSuresh: Noter D G ou E ne te sert a rien si tu ne note pas également de quelles boules tu parles. Donc au final ce que tu proposes reviens à mémoriser chaque pesée, ou dans le meilleur des cas une certaine quantité d'information par pesée. Ici on peut faire mieux tu mémoriser une quantité d'information indépendante du nombre de pesées déjà réalisées et pourtant pouvoir déduire autant par la suite.

 #14 - 24-07-2013 11:48:02

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Encore nue histoire de boules et de pesées

Pour retenir toutes les informations utiles, on retient 2 ensembles de boules :

- un ensemble "Eventuellement plus lourde" noté (+)

-un ensemble "Eventuellement plus légère" noté (-)

Au début de l'expérience, toutes les boules sont dans les ensembles (+) et (-).
Au fur et à mesure des pesées, on va rayer certains éléments de ces ensembles.

S'il y a une pesée équilibrée, on raye toutes les boules de la pesée des 2 ensembles (+) et (-).
S'il y a une pesée déséquilibrée, on raye toutes les boules qui ne sont pas dans la pesée des 2 ensembles (+) et (-), on raye de l'ensemble (+) toutes les boules qui sont du coté léger et on raye de l'ensemble (-) toutes les boules qui sont du coté lourd.

 #15 - 24-07-2013 12:18:18

vladimir37
Expert de Prise2Tete
Enigmes résolues : 30
Messages : 503
Lieu: nantes

Ecore une histoire de boules et de pesées

Descriptif de l'opération:
Sur un tas de [latex]p[/latex] boules, j'extrais deux groupes de [latex]n[/latex] boules
et je les compare.
S'ils ont le même poids, je les mets de côté et je constitue
un tas de [latex]i[/latex] boules qui sont toutes de même poids.
Je renouvèle l'opération sur le tas de [latex]p-2n[/latex] boules
restantes.
S'ils ont des poids différents, je les compare à un troisième
groupe de [latex]n[/latex] boules.Vu qu'il n'y a qu'une seule intruse,
deux des trois tas auront le même poids, je les laisse de côté
et ils vont rejoindre le tas de[latex] i[/latex] boules.
Je renouvèle l'opération sur le groupe de [latex]n[/latex] boules
que j'ai repéré.



Exemple:
Il me reste 5 boules.
J'extrais 2 boules.
S'ils ont des poids différents, je comparerai à un troisième tas de 2 boules (une des deux est la dernière du tas et l'autre fait partie du groupe de i boules).

Condition à respecter au premier tirage:
Le nombre de boules extraites est inférieur ou égal au tiers
du nombre de boules du tas inital.
[TeX]3n<p[/TeX]
Condition à respecter au-delà du premier tirage:
Le nombre de boules extraites est inférieur ou égal au tiers de la somme
du nombre de boules du tas inital et de la somme de boules identiques.
[TeX]3n<p+i[/TeX]

 #16 - 24-07-2013 13:50:34

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

encore ine histoire de boules et de pesées

@titoufred: Voila c'est ça. Bravo!

@vladimir37: Tu exhibes un protocole pour identifier la boule problématique.
Les informations que tu mémorises après chaque pesée se résument dans ton cas à la composition de tes différents groupes. Ces informations te suffisent pour faire fonctionner ton protocole. Cependant rien ne garantit que ton protocole soit optimal ni que les informations que tu mémorises te permettent de faire toutes déductions envisageables par la suite. (En fait je garanti le contraire tongue) Il y a plus efficace (mais on ne peut certainement pas l'exprimer de manière générique, donc n'essaye pas trop). Tu peux tenter de résoudre le problème historique: 13 boules, une unique intruse de poids différent -> 3 pesées suffisent. Si tu maitrises la solution de ce cas particulier tu pourra identifier le genre de déductions que tu fais, et les informations dont tu as besoin pour les faire. (ce qui donne la réponse à la question 1)

 #17 - 24-07-2013 14:05:51

vladimir37
Expert de Prise2Tete
Enigmes résolues : 30
Messages : 503
Lieu: nantes

Encore une histoire de obules et de pesées

@clydevil

Donne moi un contre-exemple afin de montrer que mon protocole ne couvre pas tous les cas.

 #18 - 24-07-2013 14:29:08

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore une istoire de boules et de pesées

@vladimir37: Je l'ai fait tongue en te rappelant l’énoncé historique:
13 boules 1 unique intruse -> 3 pesées suffisent. Avec ton protocole tu n'atteindras pas si peu de pesées.

 #19 - 24-07-2013 14:38:57

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encor une histoire de boules et de pesées

Question 2 : Si on laisse 1/3 des cas hors de la balance à chaque fois, on arrive à 3 cas pour chaque pesée dont deux sont déterminés par un déséquilibre et un par l'équilibre.

Pour 121 boules, il faut donc 5 pesées , nombre choisi au hasard puisque c'est le nombre de pesées nécessaire pour 82 à 243 boules.

Edit : Euh non, ch'uis c** !!! 121 x 2 = 242 donc c'est bien une limite. Au delà il faut 6 pesées .

5 pesées c'est pour 41 à 121 boules

 #20 - 24-07-2013 14:47:23

vladimir37
Expert de Prise2Tete
Enigmes résolues : 30
Messages : 503
Lieu: nantes

Encore une histoire de boules et de pesése

@ clydevil
J'ai vu le fil:
http://www.prise2tete.fr/forum/viewtopic.php?id=4915

Il date de 4 ans.roll

 #21 - 24-07-2013 15:40:26

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

encore une histoire de boulrs et de pesées

@gwen27: Oui pour 121. (Tu remarqueras que c'est uniquement un argument statistique que tu donnes, il ne fournit pas de certitude dans la mesure ou rien assure de pouvoir "trichotomiser" idéalement les cas restants à chaque pesée et que la condition de fin n'est pas exactement de finir sur 1 seule possibilité comme on a vu, c'est légèrement plus souple)
Pour 14 boules + 1 boule qu'on sait être bonne il ne faut que 3 pesées. (pourtant il y a 28 états des 14 boules et c'est supérieur à 27. Mais on ne veut pas forcement trouver précisément le type de défaut de la boule merdique ce qui nous économise des états à atteindre) Mais oui sinon 121 c'est ça tongue

@vladimir37: Oui c'est certainement plus vieux que 4 ans, ca se compte a priori en 10aines d’années c'est un classique. C'est pour cette raison que le but de ce post n'est pas de résoudre le classique. Tu peux cependant t'appuyer sur la solution du problème classique pour voir en quoi ton protocole n'est pas optimal.

 #22 - 24-07-2013 16:16:48

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encore une histoire ed boules et de pesées

Pour 14 boule 1 + bonne, on est juste dans le cas 13 boules si on regarde bien et on en laisse une fausse potentielle hors balance. Cela permet de récupérer le cas de 3 équilibres. La boule "bonne" est attribuée à ce cas qui ne permet pas de conclure autrement. Mais la trichotomie est acquise je pense en procédant en base 3.

C'est golgot qui a généralisé ce cas dans mon énigme précédente.

 #23 - 24-07-2013 18:04:21

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Encore une histoier de boules et de pesées

@gwen27: J'ai répondu a ton PM (j'ai encore zappe de cocher "garder une copie" donc j’espère que ce que j'ai baragouiner est clair)

 #24 - 24-07-2013 18:09:07

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,969E+3

Encore une histoire de bouels et de pesées

lollollol j'ai tout le temps le même souci mais je joue avec la règle du jeu. Je n'enregistre jamais mes messages même si je voudrais bien les rattraper parfois. big_smile

 #25 - 27-07-2013 20:42:07

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

encore une histoire se boules et de pesées

Comment fais-tu avec l'ordi pour 121 boules ?

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete