Hello!


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?

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.