Commentaire de
Liberté d'expression

En bref.

Deux contraintes tirées du « problème des pesées » : une contrainte formelle et une contrainte sémantique.

Mais encore...

Ces deux textes illustrent le fait que l'on peut dériver des contraintes très diverses (et par là des textes très différents) d'une structure mathématique donnée. Il s'agit ici de la structure des solutions du « problème des pesées ».

L'énoncé de ce problème et la discussion de ses solutions figurent dans la section Références. Il suffit pour le moment de savoir que ce problème fait intervenir douze pièces de monnaie, que nous nommerons A, B, C, ... L, et une balance à deux plateaux. Une solution du problème est une suite de trois pesées. Une pesée consiste à placer quatre pièces dans chaque plateau de la balance.

Le premier texte, Liberté d'expression, repose sur la solution suivante :

Plateau	gauche	droit
Pesée 1	A B C D	E F G H
Pesée 2	A B E F	C I J K
Pesée 3	A E G I	F H J L

Cette structure est transformée en une contrainte formelle de la façon suivante :

• chaque pièce correspon à un mot ;
• chaque pesée correspond à un vers de douze syllabes : les mots associés aux quatre pièces du plateau de gauche forment le premier hémistiche (six syllabes), ceux du plateau de droite le deuxième hémistiche ;
• les trois vers obtenus riment, au moins approximativement.

Notez que ceci impose des contraintes assez fortes sur le nombre de syllabes de chaque mot. D'autre part, les changements de place des mots d'un vers à l'autre rendent pratiquement indispensable l'usage de mots pouvant avoir différentes natures grammaticales (pourquoi : conjonction et nom ; savoir : nom et verbe).

---

Dans le deuxième texte, À l'arrêt, fortement inspiré de l'histoire que Raymond Queneau raconte de 99 façons différentes dans ses Exercices de style, une autre solution du problème des pesées est utilisée pour définir une contrainte sémantique. Chaque pièce est associée, non plus à un mot mais à un objet ou un personnage du récit. La correspondance obéit aux règles suivantes :

• chaque pesée devient un paragraphe de l'histoire ;
• les pièces intervenant dans une pesée correspondent à des objets ou personnages explicitement cités dans le paragraphe ;
• les pièces placées sur le plateau de gauche correspondent à des objets situés dans l'autobus ; celles du plateau de droite, à des objets situés sur le trottoir.

La solution retenue est :

Plateau	gauche	droit
Pesée 1	A C F H	D G K L
Pesée 2	A B J K	F H I L
Pesée 3	D H J K	A B E G

La correspondance entre les pièces et les éléments du récit est la suivante :

• A = le zazou au cou trop long.
• B = le pardessus du zazou.
• C = le chauffeur d'autobus.
• D = l'ami du narrateur.
• E = l'inconnu, ami du zazou.
• F = les autres voyageurs.
• G = un arrêt d'autobus.
• H = le quidam qui bouscule le zazou.
• I = le galon du chapeau du zazou.
• J = la place assise.
• K = le narrateur.
• L = le chapeau du zazou.

Ainsi, la première pesée comprend A, C, F, H à gauche et D, G, K, L à droite. Le premier paragraphe de l'histoire mentionne donc le zazou, le chauffeur, les voyageurs et le quidam qui se trouvent dans l'autobus, et l'ami du narrateur, l'arrêt d'autobus, le narrateur et le chapeau qui sont sur le trottoir. Il ne mentionne pas le pardessus, l'inconnu, le galon ni la place assise. Les deux autres paragraphes correspondent de la même façon aux deux autres pesées.

Note : en plus des règles qui contraignent le contenu de l'histoire, ce texte respecte une contrainte formelle : ses lignes sont isocèles.

Références.

Le problème des pesées.

Ce problème bien connu s'énonce comme suit :

On vous donne douze pièces de monnaie d'apparence identique, en affirmant que l'une d'entre elles a un poids légèrement différent des autres, sans préciser si elle est plus lourde ou plus légère. Vous disposez d'une balance à deux plateaux supposée parfaite. En trois pesées ne faisant intervenir que les pièces données, vous devez trouver quelle pièce est différente des autres, et si elle est plus lourde ou plus légère.

On peut envisager deux types de solutions à ce problème :

1. des solutions de type « algorithmique » dans lesquelles le résultat de chaque pesée influe sur la suite : prendre telles et telles pièces pour la première pesée ; puis, si la balance penche à gauche, prendre telles pièces pour la seconde, si elle penche à droite prendre telles autres, etc.
2. des solutions de type « synthétique » : on décide dès le départ quelles seront les pièces utilisées dans chaque pesée. On effectue les trois pesées en notant à chaque fois le résultat (la balance penche à gauche, penche à droite ou est équilibrée). Enfin, de ces trois observations on déduit quelle est la pièce différente des autres.

Les solutions que j'ai utilisées pour engendrer des textes à contraintes sont du deuxième type, et je ne m'intéresserai qu'à celles-ci dans cette page.

La méthode proposée ci-dessous permet d'engendrer une solution (et, par extension, toutes les solutions possibles) de façon systématique, sans tâtonnements.

Méthode de résolution

1. Préparez 13 cartes portant chacune trois lettres sur chaque face, de la façon suivante :

   Carte 1, recto : D D D, verso : G G G
   Carte 2, recto : D D G, verso : G G D
   Carte 3, recto : D D X, verso : G G X
   Carte 4, recto : D G D, verso : G D G
   Carte 5, recto : D G G, verso : G D D
   Carte 6, recto : D G X, verso : G D X
   Carte 7, recto : D X D, verso : G X G
   Carte 8, recto : D X G, verso : G X D
   Carte 9, recto : D X X, verso : G X X
   Carte 10, recto : X D D, verso : X G G
   Carte 11, recto : X D G, verso : X G D
   Carte 12, recto : X D X, verso : X G X
   Carte 13, recto : X X D, verso : X X G

2. Retirez l'une des quatre cartes 1, 2, 4 ou 5.
3. Mélangez les cartes restantes.

   Répétez ce qui suit tant qu'il vous reste des cartes en main :

4. Posez une carte sur la table, avec l'une ou l'autre face visible.
5. Comptez le nombre de D et le nombre de G apparaissant en première position sur toutes les cartes déjà posées. Comptez de même les D et les G en deuxième position, et en troisième position.
6. Si aucun des six nombres que vous venez de compter ne dépasse 4, repartez à l'étape 4.
7. Si la dernière carte posée n'a pas encore été retournée, retournez-la pour faire apparaître son autre face et repartez à l'étape 5.
8. Reprenez en main la dernière carte posée et repartez à l'étape 7.

La suite des cartes posées détermine une solution du problème des douze pièces. Pour mettre en œuvre cette solution, c'est-à-dire pour identifier effectivement la pièce anormale parmi les 12 que l'on vous donne, procédez comme suit :

1. Posez une pièce sous chacune des 12 cartes.
2. Pour effectuer la première pesée, regardez la première lettre de chaque carte. Si c'est un D, placez la pièce correspondante dans le plateau de droite. Si c'est un G, placez la pièce dans le plateau de gauche. Si c'est un X, la pièce ne participe pas à cette pesée.
3. Notez sur un papier le résultat de la première pesée : D si la balance penche à droite, G si elle penche à gauche, X si elle est équilibrée. Puis remettez chaque pièce sous la carte où elle était.
4. Pour la deuxième pesée, sélectionnez les pièces de la même façon mais en utilisant cette fois la deuxième lettre écrite sur les cartes. Notez le résultat de la deuxième pesée sous celui de la première.
5. Procédez de même pour la troisième pesée en regardant la troisième lettre des cartes, et notez le résultat à la suite des deux autres.
6. Votre papier porte une suite de trois lettres. Cherchez parmi les cartes s'il y en a une qui porte les mêmes lettres dans le même ordre. S'il y en a une, la pièce recherchée est celle qui se trouve au-dessous, et elle est plus lourde que les autres.
7. Si aucune carte ne porte les trois bonnes lettres, retournez toutes les cartes et cherchez à nouveau celle qui montre les trois bonnes lettres. La pièce recherchée est celle qui se trouve au-dessous, et elle est plus légère que les autres.

Exemple

Recherche de la solution :

On choisit d'enlever la carte 1.

2 verso G G D	Ligne 1 : 0 D, 1 G Ligne 2 : 0 D, 1 G Ligne 3 : 1 D, 0 G
2 verso G G D 11 verso X G D	Ligne 1 : 0 D, 1 G Ligne 2 : 0 D, 2 G Ligne 3 : 2 D, 0 G
2 verso G G D 11 verso X G D 9 verso G X X	Ligne 1 : 0 D, 2 G Ligne 2 : 0 D, 2 G Ligne 3 : 2 D, 0 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G	Ligne 1 : 1 D, 2 G Ligne 2 : 0 D, 2 G Ligne 3 : 2 D, 1 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D	Ligne 1 : 1 D, 2 G Ligne 2 : 0 D, 2 G Ligne 3 : 3 D, 1 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X	Ligne 1 : 1 D, 3 G Ligne 2 : 1 D, 2 G Ligne 3 : 3 D, 1 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D	Ligne 1 : 2 D, 3 G Ligne 2 : 1 D, 2 G Ligne 3 : 4 D, 1 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 recto D G D	Ligne 1 : 3 D, 3 G Ligne 2 : 1 D, 3 G Ligne 3 : 5 D, 1 G	Il y a un 5, on essaie l'autre face.
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G	Ligne 1 : 2 D, 4 G Ligne 2 : 2 D, 2 G Ligne 3 : 4 D, 2 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X	Ligne 1 : 2 D, 4 G Ligne 2 : 3 D, 2 G Ligne 3 : 4 D, 2 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X 10 verso X G G	Ligne 1 : 2 D, 4 G Ligne 2 : 3 D, 3 G Ligne 3 : 4 D, 3 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X 10 verso X G G 5 verso G D D	Ligne 1 : 2 D, 5 G Ligne 2 : 4 D, 3 G Ligne 3 : 5 D, 3 G	Il y a un 5, on essaie l'autre face.
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X 10 verso X G G 5 recto D G G	Ligne 1 : 3 D, 4 G Ligne 2 : 3 D, 4 G Ligne 3 : 4 D, 4 G
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X 10 verso X G G 5 recto D G G 3 verso G G X	Ligne 1 : 3 D, 5 G Ligne 2 : 3 D, 5 G Ligne 3 : 4 D, 4 G	Il y a un 5, on essaie l'autre face.
2 verso G G D 11 verso X G D 9 verso G X X 8 recto D X G 13 recto X X D 6 verso G D X 7 recto D X D 4 verso G D G 12 recto X D X 10 verso X G G 5 recto D G G 3 recto D D X	Ligne 1 : 4 D, 4 G Ligne 2 : 4 D, 4 G Ligne 3 : 4 D, 4 G	Toutes les cartes sont placées et les lignes sont complètes.

Nous avons donc trouvé une façon de résoudre le problème des 12 pièces, que l'on peut représenter en plaçant nos pièces (étiquetées de A à L) sous les cartes sélectionnées :

2 verso G G D A

11 verso X G D B

9 verso G X X C

8 recto D X G D

13 recto X X D E

6 verso G D X F

7 recto D X D G

4 verso G D G H

12 recto X D X I

10 verso X G G J

5 recto D G G K

3 recto D D X L

Nous pouvons maintenant effectuer les pesées indiquées par ces carte :

1. Pour la première pesée, nous mettons dans le plateau de gauche toutes les pièces qui ont un G en première ligne, soit A, C, F et H ; et dans le plateau de droite celles ayant un D en première ligne, soit D, G, K et L.
2. Pour la deuxième pesée, le plateau de gauche reçoit les pièces qui ont un G sur la deuxième ligne : A, B, J, K ; et le plateau de droite celles ayant un D sur cette ligne : F, H, I, L.
3. Enfin, la troisième pesée s'effectuera avec à gauche les pièces ayant un G sur la dernière ligne : D, H, J, K ; et à droite celle avec un D en dernier : A, B, E, G.

On peut remarquer que cette solution est précisément celle qui a été utilisée pour contraindre le texte À l'arrêt (cf. ci-dessus). Comme quoi le hasard fait parfois bien les choses :-)

Il ne reste plus qu'à interpréter les résultats des pesées. Supposons, par exemple, qu'à la première pesée la balance a penché à gauche, à la deuxième elle a penché à droite, et à la troisième elle était équilibrée. Ces résultats sont notés : G D X. Or il y a une carte qui porte ces trois lettres, c'est la carte 6 associée à la pièce F. Nous en concluons que la pièce F est plus lourde que les autres.

Pour un autre exemple, supposons maintenant qu'à la première pesée la balance est équilibrée et que les deux autres fois elle penche à droite, ce qu'on note : X D D. Aucune carte ne présente ces trois lettres sur sa face visible. Il faut donc retourner les cartes, ce qui revient à transformer tous les D en G et les G en D (on peut le vérifier ci-dessus dans la description des deux faces de chaque carte). Nous voyons alors apparaître la séquence X D D sur l'autre face (recto) de la carte 10, associée à la pièce J. Nous en concluons que la pièce J est plus légère que les autres.

Explication

Quand la balance penche d'un côté lors d'une pesée, cela signifie soit que la pièce recherchée est plus lourde que les autres, et qu'elle est dans le plateau du côté où cela penche, soit qu'elle est plus légère et qu'elle est dans le plateau opposé. Si la balance est équilibrée c'est que la pièce recherchée ne participe pas à cette pesée.

Les résultats d'une série de trois pesées permettent de savoir quel cheminement a suivi la pièce recherchée parmi les plateaux de la balance. Par exemple, si les pesées ont donné  G D X (penche à gauche, penche à droite, équilibrée) cela signifie :

• soit que la pièce est plus lourde et qu'elle a été dans le plateau de gauche, puis dans le plateau de droite, puis absente ;
• soit qu'elle est plus légère et qu'elle a été à droite, puis à gauche, puis absente.

Pour que ces informations suffisent à identifier à coup sûr une pièce parmi les 12, il ne faut pas que deux pièces suivent le même cheminement. Il ne faut pas non plus que deux pièces suivent des cheminement « opposés » (que l'une soit toujours à droite quand l'autre est à gauche et vice versa), car dans ce cas on n'aura pas moyen de savoir si c'est l'une qui est trop légère ou l'autre qui est trop lourde.

Un cheminement est une suite de trois lettres prises parmi D, G et X. Il y a donc 3×3×3 = 27 cheminements possibles. Parmi ceux-ci, nous devons en choisir 12 à attribuer à nos 12 pièces en respectant les trois règles suivantes :

1. deux pièces n'ont jamais le même cheminement ;
2. deux pièces n'ont jamais des cheminements opposés ;
3. à chaque pesée il doit y avoir autant de pièces dans chaque plateau.

Il faut faire un cas particulier pour le cheminement X X X. En effet, si une pièce suit ce cheminement cela signifie qu'elle n'intervient dans aucune pesée. La balance sera équilibrée les trois fois. Cela permet bien d'identifier la pièce recherchée (c'est la seule qui n'a participé à aucune pesée) mais il n'y a aucun moyen de savoir si elle est plus lourde ou plus légère que les autres. Si on veut pouvoir résoudre complètement le problème il ne faut donc pas attribuer le cheminement X X X à une pièce.

Il nous reste 26 cheminements à répartir selon les règles ci-dessus. Ce sont eux que l'on retrouve sur les deux faces de nos 13 cartes, les cheminements opposés figurant toujours sur les deux faces d'une même carte. Ainsi, en plaçant nos 12 pièces sous 12 de ces 13 cartes, on est sûr de toujours respecter les règles 1 et 2. La méthode que nous avons décrite pour placer les cartes, en les retournant si nécessaire, a pour objet de satisfaire la règle 3.