Nouvelle Enigme !
bonjour tout le monde. voici l'énigme :
vous disposez d'une balance à double plateau, ainsi que de 243 billes.toutes les billes sont de même poids, excepté une légèrement plus lourde.
comment, en seulement 5 pesées, obtenir avec certitude la bille légèrement plus lourde ?
@ la prochaineENIGMAN
Exactement comme quand on a 9 billes en 2 pesées, mais en 5 pesées : 32=9 et 35=243.
Allez, à moi ! Toute nouvelle énigme : J'ai 59049 billes d'un gramme, une est légèrement plus lourde. En 10 pesées, comment la trouver.
si avec 9 billes faut 2 pesee, combien faut il de pesée pour 10 billes?
vu qu'on ne peut pas faire mieux avec deux pesées, il en faudra nécessairement 3. Par exemple : appliquer la méthode pour 9 avec les 9 premières billes, et à la fin on compare avec la dixième pour trouver laquelle est la plus lourde.Envoyé par Penelope20k
Bonsoir,
Pour quelques nouveaux à ces problèmes de pesée, la raison pour laquelle on ne peut pas faire 10 avec deux pesées est assez simple: le nombre de cas distincts possibles avec 10 billes est 10, un cas par bille. Chaque pesée a trois issues possibles. Avec deux pesées on a 3 x 3 = 9 résultats distincts. Par le principe du pigeonnier, il y nécessairement au moins un des résultats de pesée qui correspond à 2 cas ou plus, donc une ambiguïté...
Ce qui m'amène à une variante très connue, que j'ai pas mal étudiée...
Le problème classique est 12 billes dont une est plus ou plus légère, on ne sait pas, que les autres. Il faut déterminer laquelle en 3 pesées, ainsi que savoir si elle est plus lourde ou plus légère. C'est classique, et a déjà été posé sur ce forum.
Mais les nouveaux peuvent chercher une solution. Disons que c'est le problème A.
Mais le nombre de cas est 12 x 2 (la multiplication par deux vient de ce que la bille soit plus légère, soit plus lourde) = 24. On est donc loin du maximum, 3 pesées permettant de distinguer 27 cas.
Problème B: On a 13 billes, et pas 12, mais on dispose d'une bille supplémentaire (une seule!) que l'on sait être de bon poids. Trouver la bille anormale en 3 pesées.
Cela fait 26 cas. Mais on peut atteindre 27 avec la modification suivante
Problème C: On a 13 billes, dont AU MAXIMUM une est de mauvais poids. En trois pesées, déterminer s'il y en a une anormale ou non, si oui laquelle, et si elle est plus lourde ou plus légère. Comme dans le cas B on dispose d'une bille supplémentaire que l'on sait être de bon poids.
Il me semble que sur ce forum, les problèmes B et C n'ont pas été posés?
Cordialement,
Il me semble que Yat (le specialiste des billes sur ce forum) a deja resolu les probleme B et C.
Tout lien m'intéresse! J'ai fouillé un peu le forum pour cela il y un mois, et je ne les avais pas trouvé...
Hop, en fait c'etait avec des pieces
http://forums.futura-sciences.com/th...18-pieces.html
La seule solution que j'y vois est celle du poste http://forums.futura-sciences.com/post218269-18.html
Je vais la regarder en détail, mais a priori elle ne marche pas parce qu'elle n'utilise pas de pièce témoin. Ou plus exactement, si elle marche je suis très intéressé, parce que cela ruine une conjecture personnelle, qu'on ne peut pas y arriver sans pièce témoin...
A première vue (à vérifier...), le problème est dans
II) a) les deux plateaux sont équilibrés : La fausse pièce est C4 ou C5
Car alors la troisième pesée ne permet pas de savoir à coup sûr à la fois laquelle est fausse et si elle est plus légère ou plus lourde. Or mon énoncé demande aussi de déterminer cela...
Cordialement,
Si on doit savoir si la bille est plus légère ou plus lourde, en effet, ça ne marche pas. Bon, l'énoncé B disait "Trouver la bille anormale en 3 pesées.", et pas "mêmes questions que pour le A", ce qui ne manque pas de préter à confusion.
Par contre, j'aimerais bien correspondre à l'étiquette que m'a collé Evil.Saien, mais je ce n'est pas moi qui avais posté la solution des énigmes proposées à l'époque, et je pense que tes énigmes B et C vont me donner du fil à retordre...
Tu as raison, petit manque de rigueur. Le fait que je cherchais un problème "complet" (27 cas pour 27 résultats) explique pourquoi j'ajoute la question de savoir si elle est plus lourde ou plus légère.
Au passage, si on enlève cette question, on peut peut-être aller plus loin que 13, mais je n'ai pas étudié ce cas.
Michel
EDIT: Je précise que j'ai des solutions pour C (donc pour B)!
Alors pour la C, et la B par la même occasion :
Sur un plateau, le groupe A de 5 billes, sur l'autre le groupe B de 4 billes plus la bille témoin.
I Ca penche.
Les situations ou un plateau donné est plus lourd ou plus léger sont symétriques, donc disons par convention que c'est le groupe A qui est le plus lourd. Je laisse deux billes de A sur le premier plateau, avec 3 de B, et je ne laisse qu'une bille de B sur le deuxième plateau. Avec des billes témoin (j'en ai 5 à disposition maintenant).
IA Le premier plateau est plus lourd
La bille est parmi les trois qui n'ont pas bougé. Si elle est sur le premier plateau elle est plus lourde, si elle est sur le deuxième elle est plus légère. On met donc une de chaque d'un coté et deux témoins de l'autre, et la solution nous donne la bille.
IB Le deuxième plateau est plus lourd
La bille fait partie des 3 du deuxième plateau qui ont changé de coté, et elle est trop légère. Une pesée permet donc de l'isoler
IC les deux plateaux sont équilibrés
La bille fait partie des 3 du premier plateau qui ont été enlevées, elle est trop lourde.
II Ca ne penche pas
La bille est parmi les 4 laissées de coté. On en met trois sur un plateau, trois billes témoin en face. Si ça penche on a trois billes candidates et on sait si la bille fautive est plus lourde ou plus légère. Si ça ne penche pas, on a la dernière bille candidate et il ne reste plus qu'à la comparer avec le témoin pour savoir si elle est plus lourde, plus légère, ou s'il n'y a pas de fausse bille.
La question suivante est celle-ci:
Dans la solution proposée, la deuxième et la troisième pesée sont conditionnelles aux résultats des pesées précédentes.
Est-il possible de trouver trois pesées pré-déterminées, telles que leur résultats combinées permettent de trouver la bille anormale, et si elle est plus lourde ou plus légère?
C'est possible pour 4 billes (4 = (32-1)/2). En les notant abcd, et t la témoin, on fait ab/ct et bc/dt...
Voilà qui est intéressant... je pensais que c'était impossible jusqu'à aujourd'hui.
En fait, dans une première approche, je me suis rendu compte qu'il suffisait de cumuler les différentes pesées possibles, les différentes boules étant soit testées soit témoin en fonction de ce qui s'est passé avant... Donc, si mes billes sont ABCDEFGHIJKLM et un témoin T, en cumulant toutes les pesées de la solution proposée plus haut, j'ai les trois pesées suivantes :
ABCDE/FGHIT
ABFGH/IJKLT
AIFJC/GKMDT
On peut aisément faire le bilan des trois états de la balance, dans l'hypothèse ou une bille donnée est plus lourde, en notant 0 une balance équilibrée, 1 si ça penche à gauche et 2 à droite. On obtient :
A 111
B 110
C 101
D 102
E 100
F 211
G 212
H 210
I 221
J 021
K 022
L 020
M 002
Et bien sur, il suffit d'inverser les 1 et les 2 quand la bille est plus légère, et le 000 conclut donc qu'aucune bille n'est fausse.
(
Dans un deuxième temps, je me suis aperçu qu'on avait une méthode beaucoup plus systématique (et donc plus rapide) de la chose, en partant directement de ce genre de tableau : Il suffit d'attribuer les codes à chaque bille (en faisant gaffe à éviter les symétriques des codes déjà attribués), et de reconstituer les pesées ensuite.
Par exemple :
A 001
B 010
C 011
D 012
E 100
F 101
G 102
H 110
I 111
J 112
K 120
L 121
M 122
Evidemment, c'est pas équilbré alors il faut bricoler un tout petit peu pour qu'on ait bien 5 billes à gauche et 4 à droites à chaque pesée. On peut par exemple inverser E, H, I et M pour obtenir :
A 001
B 010
C 011
D 012
E 200
F 101
G 102
H 220
I 222
J 112
K 120
L 121
M 211
Et, en reconstituant on obtient les pesées suivantes :
FGJKL/EHIMT
BCDJM/HIKLT
ACFLM/DGIJT
J'avais fait la théorie complète il y a quelques années. Je me suis demandé si ça valait le coup de la publier proprement. Je me le demande encore. Si cela t'intéresse je peux t'envoyer mon texte par mail...
Michel
Oui, ça m'intéresse grandement. Je te serais bien reconnaissant de me l'envoyer, j'adore les problèmes de balance.
En tout cas je ne vais plus les voir du même oeil, maintenant que la méthode que tu m'as fait découvrir m'a permis d'automatiser le tout sous excel et générer en quelques minutes une solution pour 40 billes en 4 pesées.
En fait, je vais t'expliquer la méthode générale, ça tient en 1/2 page sans les raisonnements et preuves, faciles à retrouver. Ce sera la publication, si cela se trouve originale, sur FS!
J'utilise la base 3 symétrique. La base ternaire usuelle est avec les chiffre 0, 1 et 2. Mais on peut utiliser une base aux propriétés assez extraordinaires, sur laquelle j'ai écrit un certain nombre de choses. On utilise comme chiffre -1, 0 et +1, que je note - 0 et +.
Ainsi les premiers nombres s'écrivent
00+ 0+- 0+0 0++ +--
En effet on 5 = 9 - 3 - 1, ou 4 = 3 + 1
Je numérote les boules de 1 à 13, en base 3 symétrique. J'inverse le numéro des boules paires. Inverser un numéro en base 3 symétrique est très simple : on remplace les - par des + et réciproquement. L'inversion des pairs permet de limiter le déséquilibre à 1, donc de limiter à une boule témoin...
Chaque trit (ternary digit!) correspond à une balance. S'il vaut - la boule est à gauche, s'il vaut + la boule est à droite, si 0 elle est laissée de côté.
Ensuite, j'écris le résultat des pesée, - si ça penche à gauche, + si à droite, 0 si équilibre.
La valeur absolue du nombre obtenu ainsi est le numéro de la boule, et le signe indique si la boule est plus lourde ou plus légère (selon la parité).
Ainsi, le résultat gauche, gauche, gauche donne ---, c'est à dire -13. La boule vaut 13, le signe est inversée et le numéro impair, elle est plus légère.
Le résultat droite, égal, gauche donne +0-, c'est à dire 9-1=8, c'est la boule n° 8, signe positif mais numéro pair, elle est plus légère.
Le résultat 000 indique évidemment l'absence de boule anormale.
La généralisation à tout nombre de boules est immédiate.
Je n'ai jamais vu écrit une telle solution systématique, valable pour tout nombre de boules... Si cela a déjà été publié, cela m'intéresse beaucoup!
Joli, non?
Michel
Dernière modification par invité576543 ; 01/12/2005 à 16h46.
Complément:
Pour le problème A, il suffit d'enlever la boule 7 et la boule témoin. En effet, on vérifie que la boule 7 est toujours sur le plateau opposé à la boule témoin.
Cela donne une solution systématique au problème A, avec n'importe quel nombre de boules...
En effet !
Moi j'étais resté sur la base 0 1 2 (comme tu as pu le voir), et même si ça roule bien au début, je suis quand même obligé de faire une petite manip à la main.
Là avec cette base un peu spé, ça roule tout seul. Mais j'avais jamais vu ça, une base avec des digits négatifs. On doit pouvoir faire des choses marrantes avec ça.
Surtout la base 3 symétrique! Plusieurs choses:
- Elle minimise le nombre de retenues dans les additions; (c'est d'ailleurs assez impressionnant)
- la soustraction est triviale, on inverse à vue et on additionne;
- elle est plus économe que la base 2 avec le signe -; en effet cela nécessite le même nombre de signes (3), mais l'écriture est plus compacte si on moyenne sur -n à +n;
- en écriture "décimale", le cas double est à 1/2 (+.----- et 0.++++++++), ce qui fait que l'arrondi se fait par troncature; ce qui est beaucoup plus satisfaisant qu'une double écriture pour les entiers.
- les 3sym-adiques incorporent le signe directement;
En fait c'est LA base pour travailler dans Z et extensions, alors que la base 2 est adaptée au travail dans N.
La base 9 symétrique (chiffres de -4 à +4) est très intéressante aussi:
- beaucoup moins de retenues dans les additions que la base 10;
- soustraction plus simple;
- moins de signes que la bases 10 (9 signes au lieu de 11 en comptant le - pour les nombres négatifs;
- même compacité;
- et surtout une table de multiplication qui s'apprend en quelques minutes; il n'y a que 6 cas à apprendre (2x2, 2x3, 2x4, 3X3, 3x4 et 4x4);
les bambins auraient apprécier!
Dans les applications, une que j'utilise couramment dans des programmes de dessin de polyèdres est la numérotation des éléments du cube. C'est long à exposer, mais les 27 éléments du cubes (le cube lui-même, les 6 faces, les 12 arêtes et les 8 sommets) sont numérotés de -13 à + 13. Le cube c'est 000, les sommets les nombres sans aucun 0 en ternaire symétrique, les arêtes les nombres avec un seul 0, les faces les nombres avec deux 0. Les éléments opposés sont l'inverse l'un de l'autre. L'arête joignant deux sommets a pour numéro la somme des numéros des sommets. Le sommet commun à trois faces a pour numéro la demi somme des faces. Etc...
Les 48 symétries s'écrivent alors de manière assez simple. (L'inversion c'est ... l'inversion!, les rotations s'obtiennent comme combinaisons de permutations de position des trits et la négation de certains d'entre eux...)
Toutes ces propriétés sont triviales à comprendre en base 3 symétrique... Ce se généralise au tesseract, etc... ainsi qu'au tétraèdre. Je butte sur l'icosaèdre, mais j'ai de bonnes pistes, en travaillant sur le "penteract".
L'application de la base 3 symétrique à tous les problèmes de balance à deux plateaux est évidente!
Michel
Dernière modification par invité576543 ; 01/12/2005 à 17h58.
Faire une soustraction en additionant le complement a 2 marche avec n'importe quelle base
Ce qui marche dans n'importe quelle base, c'est le complément à la base, pas à 2!Faire une soustraction en additionant le complement a 2 marche avec n'importe quelle base
En base 10,
2324 - 456 = 2324 + 544 - 1000
En base 9sym (petit pb d'écriture... souligné veut dire "-")
23401 - 34421 = 23401 + 34421
C'est plus simple... C'est assez trivial, mais je trouve ça marrant...
Il me semblait que le "complement a 2" signifie: complement + 1
Quoi qu'il en soit, comment on converti un nombre de la base 9sym dans la base 10 ?
En gros, on a 431 (9sym) = 015 (9) = 15 (10) ?
Pas vraiment! C'est comme dans n'importe quelle base. Tu additionnes les produits des chiffres avec les puissances successives de la base:Il me semblait que le "complement a 2" signifie: complement + 1
Quoi qu'il en soit, comment on converti un nombre de la base 9sym dans la base 10 ?
En gros, on a 431 (9sym) = 015 (9) = 15 (10) ?
431 (9sym) = -4 x 81 - 3 x 9 + 1 = -350 (10)
En base 2!
En base 10 on complémente les chiffres à 9 = base -1 (5 <-> 4, 8 <-> 1):
2345 - 458 = 2345 -999 + 541
et on ajoute 1, parce que le 999 est un peu gênant!
2345 - 458 = 2345 -1000 + 542
Ce qui revient à complémenter les chiffres à 9, sf le dernier qui est complémenté à 10.
C'est général à toute base. Le complément à 2, c'est bien complémenter tous les bits à 1 = base - 1 (donc les inverser 0 <-> 1) et ajouter 1, pour la même raison que dans le cas de la base 10!
Michel
Merci bien Michel pour ces précisions !
En effet, c'est interessant. Est-ce que ce système de base est répandu ?
A bientôt,
Pierre
Bonjour,
Pas à ma connaissance, mais cette connaissance est très limitée! Dans mon expérience personnelle, je l'ai (re)trouvé par moi-même quand j'en ai eu besoin pour aller au bout du problème des poids. Je me rappelle une allusion à cette base dans une discussion sur les circuits intégrés, en rapport avec la minimisation de la probabilité de retenue et donc du temps moyen pour faire une addition. Je n'ai pas rencontré ce système sur la Toile. J'ai trouvé des sites qui parlaient d'un système spécial de numérotation des éléments du cube ou du tétraèdre, dont le rapport avec la 3sym était évident pour moi, mais aucun n'en parlait.
Cordialement,
Merci pour toutes ces explications. Les applications de ces bases sont très intéressantes. Les nombres semblent beaucoup plus faciles à manipuler, mais as-tu noté des points qui par contre étaient très handicapants par rapport aux bases classiques ?
Pour les polyèdres, ça m'intrigue aussi... l'exemple du cube est un peu particulier parce que ça revient grossomodo à manipuler des vecteurs (ou les sommes sont remplacées par les demi-sommes et vice-versa, il me semble), mais je ne vois pas bien comment ça se généralise. Tu pourrais décrire un peu comment ça se passe pour le tétraèdre, par exemple ?
Curieusement, pas grand chose. Le signe du nombre ne semble pas évident, mais c'est simplement le signe du chiffre de poids fort.
La division est peut-être plus compliquée, il faut choisir le signe de la retenue. Le fait que la base ne soit pas paire fait perdre la division par 2 de manière simple.
3204 divisé par 2:
1xxx, je retiens +1 -> 1204
Si on connaît ses tables on sait que 2x3 = 13 et 2x4 =11
14xx, je retiens -1 -> 104
144x, je retiens -1 -> 14
1443 et 1/2
La gymnastique des retenues ne nous est pas usuelle, mais elle tombe sous le sens quand on connaît les tables... (Ou même plus simplement on choisit l'inverse du signe du chiffre suivant en sautant les 0 le cas échéant.) Comme les tables sont bien plus petites, cela se compense?
Le plus gros défaut c'est d'être moins bien adapté à l'électronique que la base 2!! La logique à deux états est quand même plus simple que la logique à trois états...
Pour les cubes de toutes dimension, c'est effectivement juste un encodage du vecteur, la symétrie de la base permettant de mapper la symétrie du vecteur par rapport au centre et la symétrie du nombre. Les 27 centres des éléments forment un réseau exact 3x3x3, ce qui appelle la base 3, mais 3sym est évidemment mieux que la base 3 "naturelle".Pour les polyèdres, ça m'intrigue aussi... l'exemple du cube est un peu particulier parce que ça revient grossomodo à manipuler des vecteurs (ou les sommes sont remplacées par les demi-sommes et vice-versa, il me semble), mais je ne vois pas bien comment ça se généralise. Tu pourrais décrire un peu comment ça se passe pour le tétraèdre, par exemple ?
Le tétraèdre se déduit du cube, simplement parce que le groupe du tétraèdre est un sous-groupe de celui du cube. Le sommets sont les sommets du cube avec un nombre impair de + (par exemple), les arêtes ont le numéro de la face du cube correspondante, et les faces ont comme numéro l'inverse du sommet opposé. On interprète des 12 numéros restant (ceux des arêtes du cube) comme les numéros des dièdres de face (4 faces, 3 dièdres par face).
L'icosaèdre (en fait la réunion des deux icosaèdres, le convexe et le croisé) peut être obtenu par diverses projection de polytopes de dimension supérieure, avec une nette affinité avec la dimension 5. On devrait trouver une numérotation sur 5 trits, mais je pataugeais la dernière fois que je m'amusais avec cela...
Michel
Dernière modification par invité576543 ; 02/12/2005 à 11h30.
