Bienvenue sur  ! | Les sites de JeuxOnLine... |
Bienvenue sur ! | Les sites de JeuxOnLine... |
Archives des forums MMO/MMORPG > Forums divers > Le bar de la Taverne > Douze boules de billard et une balance.
Douze boules de billard et une balance.
Par Corwin d Ambre le 11/7/2002 à 23:25:21 (#1793921)
Vous disposez d'une simple balance à plateaux, donc ce qu'elle peut faire c'est vous dire si le plateau de gauche est plus lourd que celui de droite ou inversément, c'est tout.
En trois pesées et pas une de plus, déterminez quelle est la boule de billard qui a un poids différent et si elle est plus lourde ou moins lourde que les autres.
Bonne chance.
Par Missmite le 11/7/2002 à 23:44:37 (#1793988)
tellement facile que ca marche pas, j'ai rien dit :)
Par Corwin d Ambre le 12/7/2002 à 0:41:20 (#1794212)
Provient du message de Missmite
dychotomie :) trop facile :p
tellement facile que ca marche pas, j'ai rien dit :)
Aha ! On fait moins la maligne ! :p
Et on dit dichotomie.
Par DarkJPA le 12/7/2002 à 0:43:54 (#1794222)
Par DarkJPA le 12/7/2002 à 0:48:11 (#1794237)
tu mets 6 boules sur un cote et 6 de l'autre et tu regardes vers ou ca balance.
ensuite tu separes chacune des deux parties de 6 boules en deux, et donc tu prends 3 boules du cote le plus lourd et 3 du cote le plus leger pour les regrouper et les poser sur un cote et le reste de l'autre et tu reregardes vers ou ca balance.
arf non en fait ca bloque la... il faut quand meme savoir avant si la boule est plus ou moins lourde...
Par Missmite le 12/7/2002 à 2:01:18 (#1794450)
(bon d'accord j'avoue : une solution de type monte carlo ne se trompe jamais mais des fois ne trouve pas :p )
Par Caline le 12/7/2002 à 2:27:47 (#1794501)
A la troisième pesée tu en pèses deux parmi les 3 ; si leur poids est égal, c'est la troisième mise de coté la plus lourde, sinon c'est celle du coté où ça penche :)
Par Lumina le 12/7/2002 à 3:05:51 (#1794576)
4 et 4 boules, plus 4 de coté.
- Si il y a déséquilibre => cas A et on nomme 1 à 4 celles qui semblent légères, 5 à 8 celles qui semblent lourdes et 9 à 12 les normales.
- Si il y a équilibre => cas B et on nomme 1 à 8 les normales, 9 à 12 celles de coté.
2me pesée : cas A
on met 1, 2, 5 et 9 sur le premier plateau.
on met 3, 4, 6 et 10 sur le second plateau.
- balance penche vers le premier plateau => la fausse boule se trouve parmis 3, 4 et 5. (cas A1)
- balance penche vers le second plateau => la fausse boule se trouve parmis 1, 2 et 6. (cas A2)
- équilibre => la fausse boule est 7 ou 8 : on compare 7 avec 1 et on déduit la solution automatiquement.
2ème pesée : cas B
on met 9, 10 et 11 sur le premier plateau.
on met 1, 2 et 3 sur le second plateau.
- balance penche vers le premier plateau => la fausse boule est plus lourde que les autres : on compare alors 9 et 10 et on déduit automatiquement si c'est 9 ou 10 (ou 11 : cas d'égalité des plateaux).
- balance penche vers le premier plateau => la fausse boule est plus legere que les autres : on compare alors 9 et 10 et on déduit automatiquement si c'est 9 ou 10 (ou 11 : cas d'égalité des plateaux).
- égalité => on compare 1 et 12 et sait alors si elle est plus legere ou plus lourde.
3ème pesée : cas A1
on met 4 et 5 sur le premier plateau.
on met 9 et 10 sur le second plateau.
- balance penche vers le premier plateau => 5 est fausse (et plus lourde)
- balance penche vers le second plateau => 4 est fausse (et plus legere)
- égalité => 3 est fausse (et plus legere)
3ème pesée : cas A2
on met 1 et 6 sur le premier plateau.
on met 9 et 10 sur le second plateau.
- balance penche vers le premier plateau => 6 est fausse (et plus lourde)
- balance penche vers le second plateau => 1 est fausse (et plus legere)
- égalité => 2 est fausse (et plus legere)
Voilà !
Pour ceux qui doutent, oui, j'ai trouvé la solution toute seule. :)
[edit](lien effacé pour notre Jet :p ..)[/edit]
Par Lumina le 12/7/2002 à 3:07:26 (#1794578)
Provient du message de Caline
Ca ne marche pas ton truc en cas d'égalité à la seconde pesée ;)
tu fais une pesée avec 6 de chaque coté et tu gardes les 6 du coté le plus lourd, tu refais une pesée avec 3 de chaque coté et tu gardes les 3 du coté le plus lourd...
Par Fynn Mag Kenna le 12/7/2002 à 7:07:49 (#1794831)
Si la balance est en équilibre c'est que l'intruse est parmi les 2 premières et c'est réglé avec une nouvelle pesée (2 pesées en tout)
sinon on prends le tas de 5 qui semble le plus lourd on écarte une d'entre elles pour avoir 2 boules sur chaque plateau.
- s'il y a équilibre la plus lourde est celle qui a été mise de côté (2 pesées)
- sinon on compare la masse des 2 boules sur le plateau le plus chargé (3 pesées)
Par Glorinfeld Jade le 12/7/2002 à 7:38:26 (#1794854)
Par Lumina le 12/7/2002 à 8:26:19 (#1794905)
En fait, je peux même démontrer assez simplement que ma solution est la seule possible (à la numérotation pres) :)
Démonstration :
- trouver une boule fausse parmis 12, et en meme temps découvrir si elle est plus legere ou plus lourde necessite de résoudre 24 cas.
- une balance permet de déterminer 3 états (plus lourd, plus leger, egal). Donc en deux pesées je peux montrer jusqu'à maximum 9 états différents.
- apres la premiere pesée, je dois donc avoir séparé les 24 cas du problème en 3 groupes de maximum 9 états. Simplement, compte tenu de la symétrie legere/lourde du problème, chaque groupe ne contiendra qu'un nombre pair d'états possibles. La seule séparation possible est donc 3x8.
- La seule facon de séparer en 3x8 à la premiere pesée, c'est de mettre 4 boules sur un plateau, 4 sur l'autre, et les 4 dernieres de coté. La suite se trouve automatiquement ou presque.
Par Corwin d Ambre le 12/7/2002 à 12:52:23 (#1795968)
Non seulement vous trouvez la solution mais en plus nous avons pas mal d'opinions en commun, je peux le voir d'après vos posts. Un signe ? ;)
Et puis mention spéciale à Caline qui est quand même notre modératrice préférée ;) Qui doit répondre à mon MP d'ailleurs...
Par Lumina le 12/7/2002 à 15:56:42 (#1796898)
Par Jet le 12/7/2002 à 16:10:31 (#1796941)
Pour ceux qui doutent, oui, j'ai trouvé la solution toute seule. :)
Et si vous détestez les enigmes, n'allez pas sur ce site : http://web.wanadoo.be/enigmes/
(et encore moins dans le classement ..)
comment oses-tu publier mes liens persos toi d'abord !!
même si tu as trouver le lien en faisant une recherche sur beshop c'est pas une raison de donner le lien à tout le monde :p
Par Elladan Araphin le 12/7/2002 à 16:19:55 (#1796977)
Désolé Lumina. :o
Par olyvrin le 15/7/2002 à 0:37:05 (#1806043)
Mais prouver - et en quelques lignes, s'il vous plait - que cette solution est unique, celà relève d'une exigence intellectuelle hors norme :)
Maintenant, si on généralise le problème à N boules dont K ont un poid différents des N-K autres, existe t-il une méthode générale pour déterminer s'il est possible de résoudre le problème en X pesées ?
Par Lumina le 15/7/2002 à 4:04:14 (#1806535)
réponse de l'informaticien : "non, il n'existe pas de méthode générale."
A mon avis, olyvrin, le problème est trop difficile pour trouver une solution générale.
Aussi :
1) tu ne dis pas si les boules fausses sont toutes de meme poids ou pas.
2) si je prend le simple exemple suivant : 1 boule fausse parmis 2. On ne peut alors pas résoudre le problème.
On peut peut-etre faire un début de formalisation un peu plus générale du problème ainsi :
*Toutes les boules fausses ont même poids, et toutes les boules vraies ont meme poids.
*On note P la propriété initiale "je sais si les boules fausses sont de poids plus faible ou plus lourd que les boules vraies".
*A l'état initial, il y a A boules vraies non identifiées, B boules fausses non identifiées, C boules vraies identifiées, D boules vraies identifiées. On connait ces 4 valeurs (sinon, c'est un autre problème encore plus compliqué). Par contre, P peut-etre aussi bien vraie que fausse.
*De préférence, il y a un nombre strictement inférieur de boules fausses que de boules vraies.
*Le but est de trouver le nombre minimal N de pesées nécessaires pour que P soit vraie et pour que toutes les boules soient identifiées.
Alors à la main on peut s'amuser à remplir un tableau à défaut de trouver un algorithme ... A | B | C | D | P || minimum de pesées
0 | 0 | 0+ | 0+ | V || 0
0 | 0 | 1+ | 0 | F || impossible que P devienne vraie
0 | 0 | 1+ | 1+ | F || 1
1 | 1 | 0+ | 0+ | V || 1
1 | 1 | 0 | 0 | F || impossible à résoudre
1 | 1 | 0+ | 1+ | F || 2
1 | 2 | 0 | 0 | F || 2
.. | .. | .. | .. | .. || ..
1 | 11 | 0 | 0 | F || 3 (problème posé par Corwin)
.. | .. | .. | .. | .. || ..
[edit : enfin bon, ce tableau est loin d'etre parfait ..]
Par olyvrin le 15/7/2002 à 13:20:12 (#1807800)
Clairement, il faut prendre quelques précautions pour bien spécifier l'espace des problèmes possibles. Par exemple, dire si toutes les boules "trop légères" (respectivement "trop lourdes") ont le même poids. Il est clair qu'avec certaines valeurs de N (le nombre de boules) et de K (le nombre de boules faussées), comme par exemple N=2 et K=1, le problème n'a pas de sens.
D'un point de vue informatique, une solution du problème est un arbre de décision (i.e. une structure de type "si alors sinon") qui spécifie la marche à suivre pour déterminer les numéros des boules défectueuses.
Or la taille de cet arbre de décision est bornée en fonction du nombre maximum de pesées autorisées, qui détermine en fait la profondeur de l'arbre.
Maintenant, si on a un arbre de décision "candidat", dont on ne sais pas s'il est correct ou faux, on peut vérifier en un nombre fini d'étapes si ce "candidat" est effectivement un arbre de décision correct pour le problème. Pour ce faire, il faut générer toutes les configurations de boules possibles, (sur la base d'une numérotation arbitraire des boules de 1 à N), et vérifier que le diagnostic fait par l'arbre de décision est correct pour *chaque* configuration. (Exemple de configuration : boule 1 trop légère, boule 2 ok, boule 3 trop lourde, etc...)
Or il y a un nombre fini de configurations possibles pour une valeur de N et une valeurs de K donnée.
On peut donc écrire un programme qui, étant donné N, K et X (i.e. le nombre de pesées), génère tous les arbres de décision "candidats" (il y en a un nombre fini), puis pour chaque, vérifie la validité du candidat par génération et test de toutes les configurations (il y en a aussi un nombre fini) possibles de boules.
Ce programme va résoudre le problème en un temps d'exécution fini.
Bien sur, cette approche "force brute" demande un temps de calcul qui explose de manière dramatique lorsque les valeurs de N et K augmentent. A tel point qu'en pratique, elle ne permettra pas de résoudre le problème en un temps acceptable d'après les critère humain, c'est à dire moins de quelques années de calcul :)
Le seul intérêt de l'algorithme que j'ai esquissé est de monter que le problème est décidable, c'est à dire peut être résolu en un temps fini par une machine.
Il existe beaucoup de problèmes qui sont traitables en théorie (donc décidables), mais pas en pratique, même avec des machines très puissantes, au delà d'une certaine taille des données d'entrées. J'ignore si le problème généralisé des boules est dans ce cas, car peut être y a t-il un algorithme plus efficace que celui que j'ai proposé :)
Par contre, il existe dans la "zoologie" des problèmes indécidables, c'est à dire pour lesquels on peut démontrer mathématiquement qu'il n'existe pas d'algorithme pour les résoudre.
Par Caline le 15/7/2002 à 16:16:33 (#1808489)
Bravo à Lumina qui nous éclaire de sa Lumière neuronale :)
Par Lumina le 15/7/2002 à 19:24:31 (#1809367)
Provient du message de olyvrin
C'est exactement ce que je voulais dire quand je disais que pour un informaticien, il n'y a pas de solution : le problème est trop long à résoudre en temps humain !
Bien sur, cette approche "force brute" demande un temps de calcul qui explose de manière dramatique lorsque les valeurs de N et K augmentent. A tel point qu'en pratique, elle ne permettra pas de résoudre le problème en un temps acceptable d'après les critère humain, c'est à dire moins de quelques années de calcul :)
Sinon, pour les problèmes NP et NP-complet, je sais bien ce que c'est, j'ai quand même fait mes classes comme tout le monde. ;)
Par Tharkis le 2/8/2002 à 3:37:38 (#1896377)
Par Kastïelle le 2/8/2002 à 13:34:14 (#1898670)
Par Bispritbi Drenn le 2/8/2002 à 18:08:01 (#1900636)
{
}
else
{
}
Très utile
JOL Archives 1.0.1
@ JOL / JeuxOnLine