NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 08/03/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths     

            

Énigmes de Pesées

 

Débutants

Général

BILLES

 

Glossaire

Général

 

 

INDEX

 

Jeux, énigmes

 

Débutants

Introduction

Dix Sacs

Six poids

9 billes (mono)

4 billes (ambi)

Poids-étiquettes

Autres pesées

12 par dichotomie (ambi)

12 par combinaisons (ambi)

12 billes (++)

 

Sommaire de cette page

>>> Possibilités de mouvement de plateaux

>>> Tentative de solution

>>> Une des solutions

>>> Les contraintes – Vers un algorithme de résolution

>>> Liste des solutions

>>> Programmation

 

Mono: une bille est plus lourde (ou plus légère)

Ambi: une bille  est plus lourde ou plus légère sans que nous le sachions a priori

 

 

 

 

Énigme de la pesée impossible

des DOUZE BILLES

ou BALLES, BOULES, PIÈCES

Méthode par combinaisons de pesées

ou Méthode ternaire

 

Nous connaissons la méthode classique de résolution par dichotomie: pesées de plus en plus réduites pour atteindre la balle intruse: pesée 4-3-2.

La méthode par combinaison de pesées consiste à effectuer trois pesées de deux fois quatre billes: pesée 4-4-4. 

Cette page propose cette solution avec toutes les explications pour la bâtir. En prime, la liste des 884 solutions possibles.

 

 

 

Possibilités de mouvement de plateaux

Notation pour une pesée

Pour une pesée, il existe trois issues qui seront notées (– = +).

D'où l'idée d'utiliser une numération ternaire.

 

 

 Gauche       equilibre       Droite

–1                 0                 +1 

 

Trois pesées

Avec trois pesées il existe 2 x 13 possibilités de mouvements des plateaux: soit 26 mouvements (ou issues de pesées).

Ça tombe bien: 1 bille peut être plus lourde ou plus légère parmi 12 billes; soit 24 possibilités.

 

Déductions

Par exemple sur la première ligne du tableau à laquelle on associe la bille n°1:

*      Si la bille 1 est la plus lourde, sa présence sur le plateau gauche lors des trois pesées donnera les issues: GGG.

*      Si la bille 1 est la plus légère, sa présence sur le plateau gauche lors des trois pesées donnera les issues: DDD.

 

Le tableau indique également les nombres ternaires associés et sa conversion décimale.

 

Idée

Comment combiner les billes sur les plateaux de sorte que chaque possibilité de bille intruse provoque une suite d'issues différentes ?

Même s'il y a 24 possibilités pour 26 issues de pesées, il existe quelques contraintes qui limitent les solutions.

 

 

Tableau des issues de trois pesées

Voir Table des nombres ternaires équilibrés

 

Rappel: conversion du nombre [1, 1, -1] en ternaire équilibré: 1x9 + 1x3 – 1x1 = 11 en base 10.

 

 

Tentative de solution

 

Chaque pesée comporte 4 billes à gauche, quatre billes à droite.

 

Que peut-on déduire de ces trois pesées?

*      Si le plateau gauche descend trois fois (GGG), la bille 1 est identifiée comme étant la plus lourde. C'est la seule qui est présente les trois fois à gauche.

*      Si le plateau gauche descend deux fois et le droit une fois (GGD), la bille 2 en est responsable.

*      Etc.

 

Les huit issues de pesées permettent d'identifier la bille lourde parmil les huit billes.

 

Très bien!  Nous avons compris le principe, mais maintenant il faut passer à douze billes. Les cas où les plateaux sont en équilibre vont nous aider.

 

 

 

 

Une des solutions

 

Solution: tableau des trois pesées successives

 

 

Mettre sur le plateau gauche (1, 2, 3, 4) et à droite (5, 6, 7, 8), puis (1, 2, 10, 12) et (3, 4, 7, 11) et enfin (1, 3, 6, 9) et (2, 5, 11, 12).

Les trois mouvements de plateaux sont alors spécifiques à chaque bille et selon qu'elle est plus lourde ou plus légère.

 

Exemple: suivez le chemin de la bille 4. Si c'est elle qui est la plus lourde, on observera GDE: le plateau gauche descend, puis le plateau droit lors de la deuxième pesée et enfin équilibre en troisième pesée, car cette bille n'est pas dans la pesée. Si, au contraire, on a "droit, gauche et équilibre", c'est que c'est la bille 4 qui est plus légère.

 

Chemin des billes
On indique en rouge le numéro de la balle lorsqu'elle est lourde. GGG est le chemin de la balle 1 lourde; DDD est celui de la balle 1 légère. On ne l'indique pas pour mieux observer l'exclusivité des chemins. Chacun des chemins doit se trouver sur une ligne différente. Comme prévu, il rste une ligne libre.

On aurait pu faire d'autres choix. Mes lesquels ? Ce tableau est très utile pour évaluer les contraintes à respecter pour aboutir à la discrimination de la balle fautive.

 

 

Les contraintes – Vers un algorithme de résolution

Quelles sont les propriétés des ces trois pesées pour aboutir à une solution ?

En fait, quelles sont les règles qui peuvent conduire à un algorithme de recherche des solutions ?

Règle 1

Toutes les billes sont impliquées dans chaque pesée et une seule fois en trois groupes de quatre.

On vérifiera que la somme sur chaque ligne vaut 78:
1 + 2 + 3+ ... + 12 = 12 x 13 / 2 = 78

Règle 2

On place quatre billes à droite, quatre billes à gauche et quatre billes de côté et on les numérote.

Toute les solutions commencent par

[1, 2, 3, 4] versus [5, 6,7, 8] et [9, 10, 11, 12]

Règle 3

Une bille du plateau gauche est lourde si le plateau gauche descend.

Etc. 

 

Les quatre billes du plateau gauche sont sur les lignes qui commencent par G (zone bleue)
Choix de 4 parmi 9 = 126 possibilités

Les quatre billes du plateau droit sont sur les lignes qui commencent par D (zone verte).
Choix de 4 parmi 9 = 126 possibilités

Les quatre billes mise de côté sont sur les lignes qui commencent par E (zone jaune).
Choix de 4 parmi 8 = 70

Bilan: 126 x 126 x 70 = 1 111 320 cas à explorer

 

Règle 4 – Intervention de la numérotation décimale

Les chemins pour une bille est double: un chemin direct pour identifier si elle est lourde et un chemin opposé pour identifier si elle est légère.

 

GDE (4) = chemin balle 4 pour lourde

DGE (-4)  = chemin balle 4 pour légère

 

 

Parmi les combinaisons, il faut exclure celle pour lesquelles le chemin inverse est déjà affecté à une bille.

Dit-autrement, si le chemin prend le numéro décimal 4, on exclut le chemin numéroté -4 pour une autre bille.

En logique: l'inverse d'un membre du plateau droit n'est pas membre du plateau gauche.

Règle 5 – Intervention de la numérotation ternaire

Chaque pesée doit respecter la répartition en trois groupes de quatre.

La première est acquise par construction. Le chiffre de poids fort en ternaire est -9 pour gauche; +9 pour droite et 0 pour équilibre. La somme est nulle.

 

Pour obtenir la bonne répartition lors de la deuxième pesée, la somme des chiffres de poids intermédiaires (3) doit être nulle.

Comme elle doit être nulle pour le chiffre de poids faible (1).

Une sommation sur les chiffres du milieu pour tous les numéros de billes sélectionnées fera l'affaire. idem pour le chiffre de droite.

 

 

 

Liste des solutions

L'implémentation de l'algorithme en programme montre qu'il y a 884 solutions au problème de la pesée des douze billes.

 

Le tableau montre les six premières solutions.

Voir Toutes les solutions

 

Tableau de l'affectation des billes  (rouge) à un nombre qui, convertit en ternaire, donne l'issue de la pesée pour cette bille

 

Lecture de la table – Première ligne:

Affectation des billes à un numéro (à gauche) et  conversion ternaire pour établir les trois pesées (à droite). Ex: la bille 1 est associée à -1310 = [-1, -1, 1], soit trois pesés sur le plateau de gauche. Pour la bille 2, on a -1210 = [-1, -1, 0], soit deux pesées à gauche et, elle est mise de côté pour la troisième pesée.

 

 

 

Ligne 2 et ligne 3 du tableau ci-dessus 

 

 

Ligne 884 du tableau exhaustif 

Voir Liste exhaustive des 884 solution

 

 

 

Programmation

 

Commentaires

Le package combinatoire est appelé (calcul des combinaisons avec l'instruction choose).

Le compteur de solution kt est initialisé.

 

Trois listes (M, E et P) pour la liste des possibilités en Moins, Égal ou Plus. Règle 3.

 

Trois listes (MM, EE et PP) qui contiennent les combinaisons de 4 parmi les nombres des listes originelles. Les variables en q comptent la quantité de combinaisons pour chaque liste.

Trois boucles pour associer chacune des combinaisons (Mc, Ec et Pc) de chacune des trois listes.

 

On vérifie que les membres en moins de Mc (plateau de gauche) ne sont pas dans ceux de Pc (plateau de gauche). Règle 4 d'exclusivité.

 

Pour les 12 valeurs retenues dans Mc, Ec et Pc, conversion en ternaire équilibré (instruction ter de conversion ternaire équilibré, à créer).

 

Ti, T2 et T3 sont les sommes des chiffres de poids foret, moyen et faible des 12 nombres ternaires

 

On ne conserve que les cas où ces trois totaix sont nuls. Règle 5.

Ces valeurs retenues sont affichées (lprint).

 

En fin de programme, on demande la valeur du compteur kt.

Voir ProgrammationIndex

 

 

 

 

 

Retour

*    Énigme des douze balles – Méthode par dichotomie

*      Autres types de problèmes de pesées

Suite

*    Énigme des douze billes – Liste des solutions

*      Énigme des douze balles – Compléments

Voir

*     Adam en douze heures

*    Alexandrins longs et courts

*    Arbre de Distribution

*    Échecs

*    Énigmes de transvasements

*    Faire 12 avec cinq fois le même nombre

*    JeuxIndex

*    Jeux avec 10

*    Jeux de partage

*    Les 12 travaux d'Hercule

*    Pentaminos

*    Sudoku

*    Transfo Boulanger

DicoNombre

*    Nombre 12

Sites

Voir liste

 

*    Solution du problème des douze pièces – Jean-Christophe Michel – Méthode avec numération ternaire

Cette page

http://villemin.gerard.free.fr/aJeux1/Pesee/Balle12c.htm