Un problème de remplissage de verres

Un exemple de démonstration mathématique

Piste bleue Le 12 août 2009  - Ecrit par  Xavier Caruso Voir les commentaires (1)

Dans cet article, nous présentons et résolvons une énigme logique. En fait, celle-ci sert principalement de prétexte à la mise en place d’une démonstration mathématique. Mais une démonstration qui vous surprendra peut-être tant elle est différente de celles que vous avez pu rencontrer à l’école : beaucoup de phrases, pratiquement aucun calcul, surtout de la logique. Par contre, je vous préviens tout de suite, de même que beaucoup d’autres démonstrations mathématiques, elle ne sera pas forcément toujours docile et vous demandera certainement des efforts pour l’apprivoiser complètement. Mais le jeu en vaut sûrement la chandelle... alors, lisez et jugez par vous-même.

GÉNÉRALEMENT, les exposés de vulgarisation mathématique se fixent pour objectif de présenter une certaine théorie, en insistant d’une part sur les idées fondamentales qui la soutiennent et d’autre part sur les applications qu’elle peut avoir dans les autres domaines. Cet article ne s’inscrit pas du tout dans cette ligne, et au contraire détaille un aspect que l’on a souvent l’habitude de passer sous silence lorsque l’on vulgarise (peut-être pour ne pas réveiller les mauvais souvenirs d’école) : c’est la démonstration ! Car, il faut savoir que si les belles théories et les grandes idées constituent souvent les avancées les plus remarquables de la mathématique, toutes celles-ci sont justifiées jusqu’au moindre détail par de nombreuses démonstrations rigoureuses, et que l’essentiel du travail du mathématicien est de les construire.

L’énoncé du problème

On considère un damier rectangulaire sur lequel on a disposé sur chaque case un verre contenant une certaine quantité d’eau. Ni la taille du damier, ni les quantités d’eau ne sont pour l’instant fixées : on entend par là que le problème qui va suivre est posé pour des damiers de n’importe quelle taille, et pour des remplissages arbitraires des verres.

La vignette de cet article — une image de synthèse réalisée par Jos Leys, cliquez ici pour la voir en grand — montre un exemple de telle configuration. Bien que très jolie, elle présente au moins le défaut de ne pas être très précise : on ne saurait dire avec exactitude quelle quantité de liquide il y a dans chaque verre ni même si celui en haut à gauche est exactement deux fois plus rempli que son voisin de droite, ou un peu plus, ou un peu moins. Un second défaut, qui n’apparaît pas de façon flagrante sur cette vignette car le damier qu’elle représente est petit, est lié à la lisibilité : si on avait représenté un damier avec dix lignes et dix colonnes (comme les damiers classiques sur lesquels on joue aux dames) — et donc cent verres — je pense que vous admettrez sans trop de mal qu’il n’aurait pas forcément été facile de distinguer précisément tous les verres, par exemple à cause des chevauchements éventuels ou encore des reflets. Pour toutes ces raisons, plutôt que d’utiliser des images de synthèse ou des photographies, nous représenterons désormais les configurations de façon schématique comme ceci (« cl » pour centilitres) :

Figure 1

Étant donné une telle configuration, on s’autorise à prendre l’un des verres et à verser tout ou partie de son contenu dans le verre immédiatement en-dessous (s’il existe) ou immédiatement à droite (s’il existe). Voici deux animations montrant des mouvements autorisés.

La question est de savoir s’il est possible de parvenir, après un certain nombre de transvasements licites, à une configuration dans laquelle tous les verres sont également remplis. En fait, cette question n’est pas vraiment bien posée car la réponse dépend de la configuration initiale, c’est-à-dire de la quantité d’eau présente dans chaque verre au début de la manipulation. Typiquement, si au début, il y avait déjà par chance autant d’eau dans chaque verre, on est déjà arrivé à la position souhaitée ; il est donc clair que dans ce cas, la réponse est affirmative. Par contre, si au départ, tous les verres sont vides sauf celui en bas à droite, la réponse est négative car, à partir de cette configuration, aucun mouvement n’est possible : le seul verre qui n’est pas vide n’a ni voisin immédiatement en-dessous, ni voisin immédiatement à droite ! Plutôt donc que de demander si, oui ou non, il est possible de parvenir à une situation d’équilibre, il aurait été plus judicieux de formuler la question ainsi : déterminer les positions initiales pour lesquelles il est possible, après un certain nombre de transvasements licites, de parvenir à une configuration dans laquelle tous les verres sont également remplis.

Peut-être êtes-vous en train de vous demander pourquoi l’on s’intéresse à une énigme aussi saugrenue, sinon pour s’amuser (ce qui est en fait certainement une raison suffisante !). C’est vrai que, tel que je l’ai énoncé, mon problème ressemble plus à une amusette idiote (et sans doute même pas amusante) qu’à autre chose ; en tout cas, on a du mal à se convaincre que cela puisse être sérieux. J’expliquerai à la fin de cet article pourquoi j’ai choisi ce problème, et notamment (mais très brièvement) en quoi sa résolution est liée à d’autres questions mathématiques contemporaines.
Toutefois, pour ne pas donner l’impression que j’esquive l’objection, je vous livre une seconde interprétation que, j’espère, vous trouverez un peu moins artificielle. Imaginez que les verres soient remplacés par des châteaux d’eau, chacun d’eux étant utilisé pour alimenter un certain nombre de maisons (qui varie peu d’un château d’eau à l’autre). Imaginez également que chaque château d’eau soit relié à ses plus proches voisins par un tuyau, mais que le terrain soit en pente de telle sorte que l’altitude décroisse lorsque l’on se déplace vers le bas de la carte (vers le Sud) ainsi que vers le droite (vers l’Est) : chaque château d’eau est donc en mesure de ravitailler ses confrères qui sont situés immédiatement à droite et en dessous, mais pas ses deux autres voisins puisque bien sûr l’eau ne saurait monter d’elle-même. Hélas, la saison des pluies n’a pas profité à chaque région de la même façon et, à l’issue de celle-ci, les châteaux d’eau sont très inégalement remplis : certains ont largement de quoi couvrir les besoins des maisons qu’ils desservent, alors que d’autres, moins chanceux, sont en pénurie. Une question naturelle est de savoir s’il y a moyen de transvaser de l’eau entre les châteaux d’eau pour qu’ils soient au final également remplis et puissent donc répartir de façon équitable l’eau entre les différentes maisons. Eh bien, c’est exactement le problème qui a été posé précédemment dans le langage des verres ! Bien sûr, on pourra rétorquer que les châteaux d’eau ne se répartissent en général pas en rectangle, et que l’on n’a pas nécessairement besoin de la même quantité d’eau partout. Certes. Vous concèderez cependant, j’imagine, que le problème simplifié que nous nous sommes posés devrait apparaître comme une première étape dans l’étude très complexe de la gestion des châteaux d’eau. Il semble même à vrai dire plausible que la résolution de notre question — de notre modélisation, pourrions-nous dire — nous fournisse quelques idées directrices générales pour attaquer d’autres cas plus compliqués. C’est souvent en cela que réside l’intérêt d’une modélisation : elle n’est certainement jamais parfaitement conforme à la réalité, mais elle permet malgré tout généralement d’appréhender les phénomènes majeurs. Il sera toujours temps ensuite d’étudier les imperfections et de proposer de nouvelles modélisations... ce que, d’ailleurs, l’on peut faire, et qui a même été fait, dans notre contexte.

À partir de maintenant, je ne parlerai plus que de verres, mais si cela vous dérange, libre à vous de remplacer partout par « châteaux d’eau ».

Comment démontrer que c’est possible,
et comment démontrer que ça ne l’est pas ?

On a déjà dit que le but de cet article était de faire une démonstration mathématique. Mais, qu’est-ce que cela signifie ? Et, déjà, qu’y a-t-il à démontrer ? Rappelez-vous, pour l’instant nous avons simplement posé une question : étant donné une configuration initiale, est-il possible d’atteindre une configuration dans laquelle tous les verres sont également remplis ? Nous n’avons jamais demandé de démontrer quoi que ce soit. En fait, la démonstration n’est rien d’autre que la justification de la réponse que l’on va donner à la question et, du moins en mathématiques, on ne peut jamais en faire l’économie : autrement dit, il n’est pas possible de se contenter de répondre « oui » ou « non », il faut toujours expliquer pourquoi avec une démonstration.

Admettons un instant que l’on démarre avec une configuration initiale pour laquelle la réponse est « oui », par exemple celle de la figure 1. Comment allons-nous faire pour démontrer que la réponse est effectivement « oui » ? Dans ce cas, c’est assez simple à vrai dire : il « suffit » [1] d’expliciter une suite de transvasements qui fonctionne. Par exemple, cette animation

peut tout à fait tenir lieu de démonstration, d’autant plus que les volumes d’eau sont constamment indiqués, ce qui permet à tout un chacun de vérifier qu’il n’y a aucune arnaque dans le film.

Que doit-on faire, par contre, si la réponse est « non » ? Il faut démontrer — prouver véritablement — qu’il est impossible d’arriver à une situation équilibrée. Évidemment, il n’est pas du tout suffisant de dire « j’ai essayé (méthodiquement) toute la journée hier chez moi, et je n’ai pas réussi » : il est clair que vous n’allez convaincre personne comme cela. Non pas que l’on ne vous croira pas. Effectivement, vous avez sans doute essayé d’arrache-pied, et vous avez sans doute échoué (et pour cause, c’était impossible), mais la raison était peut-être simplement que vous n’avez pas été assez adroit ou pas assez malin. De même que si vous dites que vous n’arrivez pas à résoudre un Sudoku force 8, même après y avoir passé des heures, les gens ne vont pas croire que c’est parce qu’il était impossible, mais plutôt que c’est parce qu’il était trop dur pour vous. Donc l’argument « Je n’ai pas réussi » n’est pas acceptable. De même d’ailleurs que l’argument « Je l’ai donné à un ami spécialiste qui n’a pas réussi ».

Il faut donc trouver autre chose. Mais quoi ? Plutôt que de s’embarquer dans des principes généraux, prenons un exemple. En fait, nous avons déjà rencontré un exemple dans lequel la réponse était « non » (celui où seul le verre en bas à droite était rempli), mais il est tellement évident (rappelons qu’alors aucun mouvement n’est possible) qu’il n’est probablement pas très parlant. Étudions donc en un autre, ou plutôt une famille toute entière d’autres. En effet, supposons simplement que, dans la configuration initiale, le verre en haut à gauche est vide, et au moins un autre ne l’est pas. Il nous reste plein de liberté pour remplir les autres verres comme on le souhaite, mais nous allons démontrer que pour tous ces exemples, la réponse est « non ». Comment s’y prendre ? La clé consiste à remarquer qu’aucun mouvement autorisé ne peut apporter de l’eau supplémentaire au verre en haut à gauche [2]. Ainsi, si comme nous l’avons supposé, ce verre est vide au départ, il le restera nécessairement tout au long de l’opération. On en déduit que si on pouvait arriver à une position dans laquelle tous les verres sont également remplis, c’est que, dans cette position, tous les verres sont vides. Comme, par ailleurs, l’eau ne peut être que transférée d’un verre à un autre et qu’en tout cas elle n’est jamais jetée, s’il n’y a pas du tout d’eau à la fin, c’est certainement qu’il n’y en avait pas au début. En mettant bout à bout les deux phrases précédentes, on vient de dire que le seul cas dans lequel l’opération est possible, c’est lorsqu’il n’y a pas d’eau au début. Or, nous avons supposé qu’au début, au moins un verre n’était pas vide (donc qu’il y avait de l’eau), c’est donc que l’opération est impossible. Vous êtes convaincu ?

Une première observation

Maintenant que, je pense, le problème et la forme de la réponse attendue ont été suffisamment expliqués, il est temps d’aborder sa résolution, c’est-à-dire la fameuse démonstration tant plébiscitée. La première observation essentielle est que, si le mouvement est possible, la quantité d’eau qu’il y aura au final dans chaque verre est facile à déterminer. En effet, puisque l’on ne fait que transvaser de l’eau d’un verre à un autre, la quantité totale d’eau est conservée au cours de l’opération. Ainsi, si à la fin, tous les verres contiennent la même quantité d’eau, c’est qu’ils contiennent chacun la fraction correspondante de la quantité d’eau totale du départ. Voici un exemple qui éclaircira peut-être cette dernière phrase. Si la situation de départ est

il y a en tout et pour tout 9 + 18 + 15 + 18 + 15 + 12 + 9 + 3 + 9 = 108 cl d’eau dans les verres. Après chaque transvasement, l’eau peut certes passer d’un verre à un autre, mais la quantité totale d’eau, elle, reste constante égale à 108 cl. Donc, si on arrive à une position équilibrée dans laquelle tous les verres sont également remplis, il y aura nécessairement $108 \div 9 = 12$ cl d’eau par verre. Autrement dit, il revient au même de chercher à mettre exactement la même quantité d’eau dans chaque verre (ce qui est ce que l’on demande) et de chercher à mettre exactement 12 cl dans chaque verre. L’avantage de la deuxième formulation est que l’on sait déjà un peu mieux où l’on va.

Ceci peut vous paraître anodin mais, dans ce cas à vrai dire assez simple, cette information est d’une utilité plus que précieuse pour pouvoir conclure quant à l’impossibilité de la manœuvre. En effet, remarquez qu’il y a seulement 9 cl d’eau dans le verre en haut à gauche et que l’on a déjà dit et utilisé que ce verre ne pouvait que se vider. Ainsi, on n’arrivera jamais à mettre les 12 cl d’eau nécessaires dans ce verre. Voici donc un nouveau cas que l’on arrive à traiter par cette simple remarque.

Remarquez également que la méthode s’applique de la même manière dans la situation déjà rencontrée précédemment où le verre en haut à gauche est vide, et où au moins un autre ne l’est pas.

Le choix d’une unité de volume.
Pour l’instant, nous avons utilisé les centilitres pour exprimer les volumes mais, pour la suite du raisonnement, il sera bien plus commode d’utiliser une autre unité moins conventionnelle. Posons pour cela une définition.

Définition 1
On appelle dose le volume moyen de liquide qu’il y a par verre dans la position initiale (c’est-à-dire la somme de tous les volumes divisée par le nombre de verres).

Par exemple, dans le dernier exemple présenté, une dose vaut 12 cl, et après conversion, les volumes s’expriment en doses comme le montre la figure que voici

À partir de maintenant, nous compterons tous nos volumes en doses. L’avantage certain qu’il y a à raisonner en doses plutôt qu’en litres ou en centilitres est que notre objectif devient de remplir chaque verre à hauteur d’une dose exactement. Autrement dit, nous n’avons plus à nous encombrer d’un nombre supplémentaire qui précise le volume que l’on doit mettre dans chaque verre, ce nombre lorsqu’il est exprimé en doses est toujours 1.

Recherche de contraintes

Dans le paragraphe précédent, nous avons pris un unique exemple pour illustrer notre propos, mais l’argument que nous avons développé a une portée beaucoup plus générale. Exactement, il démontre que l’opération de transvasement est impossible pour toutes les positions initiales dans lesquelles le verre en haut à gauche contient strictement moins d’une dose d’eau. De façon très semblable, on peut démontrer que l’opération est aussi impossible pour les positions initiales où le verre en bas à droite contient strictement plus d’une dose d’eau. En effet, il s’agit cette fois-ci de remarquer que la quantité d’eau contenue dans le verre en bas à droite ne peut qu’augmenter au cours du temps. Ainsi, s’il y avait au début strictement plus d’une dose d’eau dans ce verre, on ne saurait revenir à une situation où le verre contiendrait exactement une dose, ce qui est pourtant nécessaire pour égaliser les volumes d’eau dans chaque verre. Pour l’instant, nous avons donc dégagé deux contraintes qui permettent déjà d’apporter d’emblée une réponse — en l’occurrence négative — pour un certain nombre de situations initiales. Hélas, il reste encore un grand nombre de cas que l’on ne sait pas (encore) traiter. Continuons donc sur notre lancée en essayant de trouver d’autres contraintes qui assureront que l’opération est impossible. Si l’on essaie de reprendre la démarche précédente, on en vient à se demander s’il n’existe pas certaines zones dans lesquelles ne peut pas sortir. Pour les définir, nous avons besoin d’une deuxième définition.

Définition 2
Une ligne brisée convenable est une ligne brisée imaginaire tracée sur le damier sur les lignes marquant les séparations entre les cases, qui part du coin inférieur gauche, arrive au coin supérieur droit et a la propriété de toujours aller soit vers le haut, soit vers la droite.

Une ligne brisée convenable découpe le damier en deux zones : celle située à sa gauche (ou en dessus, c’est pareil), et celle située à sa droite (ou en dessous, c’est pareil). Voici plusieurs dessins montrant des lignes brisées convenables (en gras sur la figure), accompagnées des découpages qui en résultent (en vert et en rouge sur la figure).

Nous dirons dans la suite qu’un verre est vert s’il est à gauche de la ligne brisée, et qu’il est rouge s’il est à droite. Que se passe-t-il lorsque l’on accomplit un transvasement licite ? Trois cas sont possibles.

  • Premier cas. On verse de l’eau provenant d’un verre vert dans un autre verre vert. La quantité d’eau totale contenue dans les verres verts est alors inchangée, de même que la quantité d’eau totale contenue dans les verres rouges.
  • Deuxième cas. On verse de l’eau provenant d’un verre rouge dans un autre verre rouge. Comme précédemment, les quantités d’eau totales contenues dans les verres verts d’une part et les verres rouges d’autre part sont inchangées.
  • Troisième cas. On verse de l’eau provenant d’un verre vert dans un verre rouge. Dans ce cas, la quantité d’eau totale contenue dans les verres verts diminue, alors que celle contenue dans les verres rouges augmente.

Et il n’y a pas de quatrième cas puisqu’il est impossible, en suivant les règles imposées, de verser de l’eau d’un verre rouge dans un verre vert. Ainsi, au cours du temps, la quantité d’eau dans la zone rouge ne peut qu’augmenter (alors que celle dans la zone verte ne peut que diminuer). Or, si l’opération est possible, il doit y avoir à la fin dans la zone rouge autant de doses d’eau qu’il n’y a des cases dans cette zone. Puisque la quantité d’eau rouge (i.e. d’eau dans la zone rouge) ne peut qu’augmenter, pour que l’opération soit possible, il faut qu’il y ait dans la position initiale au plus autant de doses d’eau dans la zone rouge qu’il n’y a de cases dans cette zone. Nous avons donc obtenu une nouvelle contrainte, et même toute une famille de contraintes puisque l’on en a une pour chaque découpage ! Pour les deux derniers découpages donnés en exemple, on retrouve les contraintes que nous avions énoncées tantôt concernant le remplissage des verres en haut à gauche et en bas à droite. Faites l’exercice pour vous en assurer !

Afin de mieux les mettre en valeur et de pouvoir plus facilement y faire référence par la suite, les mathématiciens aiment énoncer leurs résultats intermédiaires (à l’instar de celui que nous venons d’obtenir) sous forme de lemmes. Ainsi, voici ce que l’on pourrait trouver dans un article (ou un cours) de mathématiques.

Lemme 1
Fixons une configuration initiale. S’il existe un découpage par une ligne brisée convenable pour lequel la quantité d’eau contenue dans la zone à droite de la ligne brisée (la zone rouge), lorsqu’elle est exprimée en doses, excède strictement le nombre de cases de cette zone, alors l’opération d’« équilibrage » est impossible.

Conditions nécessaires et conditions suffisantes

Arrêtons-nous un instant pour faire le point sur notre démonstration. Jusqu’à présent, nous avons trouvé des contraintes (on rappelle qu’il y en a une pour chaque découpage du damier par une ligne brisée convenable), et démontré que dès que l’une d’entre elles n’était pas satisfaite, il était impossible d’équilibrer les volumes des verres en respectant les règles. Ces contraintes sont ce que l’on appelle des conditions nécessaires : elles sont nécessaires à la faisabilité de l’opération d’équilibrage dans le sens où pour celle-ci soit réalisable, il faut qu’aucune contrainte ne soit mise en défaut.

Par contre, nous n’avons pour l’instant aucune information sur la faisabilité de l’opération lorsque les contraintes sont satisfaites. Autrement dit, nous ne savons pas encore si l’ensemble des contraintes que nous avons trouvés constitue une condition suffisante, c’est-à-dire s’il suffit que toutes les contraintes soient satisfaites pour que l’opération soit possible. Dans la suite, nous allons démontrer que c’est bel et bien le cas, mais vous allez constater qu’il reste encore beaucoup de travail pour cela.

À partir de maintenant, on considère donc une situation initiale qui respecte les contraintes : on suppose que pour tout découpage du damier par une ligne brisée convenable, il n’y a pas plus de doses d’eau dans la zone rouge (celle à droite de la ligne brisée) qu’il n’y a de cases dans cette zone. Et on souhaite démontrer que l’opération de transvasement est possible. Pour cela, comme nous l’avons déjà expliqué, il « suffit » d’exhiber une suite de mouvements licites qui conduit à l’équilibre recherché. En fait, contrairement à ce que pourrait laisser sous-entendre le « suffit », cela n’est pas simple, et la raison principale en est que l’on ne souhaite pas simplement traiter une configuration initiale bien déterminée, mais au contraire on souhaite traiter simultanément toute une énorme famille (infinie notamment) de configurations initiales, à savoir celles pour lesquelles les contraintes sont respectées. Il s’agit donc de fournir une stratégie générale, accompagnée de — et c’est au moins tout aussi important — la garantie qu’elle fonctionnera dans tous les cas envisagés.

Le cas d’un rectangle à une seule ligne :
illustration du principe de démonstration par récurrence

La démonstration étant assez élaborée, je préfère commencer par présenter un cas plus simple sur lequel il sera plus aisé d’expliquer les idées principales. Ce cas est celui où le damier n’a qu’une seule ligne. Le nombre de colonnes ainsi que les volumes d’eau contenu précisément dans chaque verre ne sont par contre pas précisés ; on sait simplement qu’ils satisfont les contraintes. On est donc dans la situation schématisée ainsi :

où l’on ne sait pas combien de verres se cachent derrière les points de suspension. Comme nous le disions précédemment, on sait par contre que les contraintes sont toutes satisfaites. Qu’est-ce que cela signifie concrètement dans notre cas particulier ? Pour répondre à cette question, il s’agit d’abord de comprendre ce qu’est une ligne brisée convenable. En fait, comme il n’y a qu’une seule ligne de verres, une ligne brisée convenable ne pourra se déplacer qu’une fois vers le haut, et sera obligée d’aller vers la droite toutes les autres fois : on rappelle qu’une ligne brisée convenable ne peut se déplacer que vers le haut ou vers le droite et, ici, étant donné qu’il n’y a qu’une ligne, on ne peut pas se déplacer deux fois vers le haut. Ainsi, à partir du coin inférieur gauche, elle n’a d’autre choix que de commencer par un certain nombre de déplacements vers la droite (éventuellement aucun), puis d’aller une fois vers le haut avant de rejoindre finalement le coin supérieur droit en continuant à se déplacer uniquement vers la droite. Comme un dessin est souvent bien plus clair qu’une longue explication, voici la liste exhaustive des quatre lignes brisées convenables et des découpages qu’elles engendrent lorsqu’il n’y a que trois verres.

Dans le cas général, il y a toujours une ligne brisée convenable de plus qu’il n’y a de verres. De cette description, on déduit que, dans le cas d’une seule ligne, les contraintes s’énoncent plus simplement comme suit :

  • le dernier verre contient au plus une dose d’eau
  • les deux derniers verres contiennent (à eux deux) au plus deux doses d’eau
  • les trois derniers verres contiennent (à eux trois) au plus trois doses d’eau

et ainsi de suite avec autant de lignes qu’il n’y a de verres. Remarquez que dans le découpage correspondant à la première ligne brisée (celle qui monte le plus tard possible), il n’y a aucun verre rouge et donc aucune contrainte associée : il est donc normal que l’on récupère autant de contraintes que de verres, même s’il y a une ligne brisée convenable supplémentaire.

Il est maintenant temps d’énoncer notre stratégie. Nous allons voir qu’elle est assez simple ; prouver qu’elle fonctionne dans tous les cas sera par contre plus délicat.

Stratégie (pour le cas d’une seule ligne)
1. On verse de l’eau du premier verre dans le deuxième jusqu’à ce qu’il (le premier) ne contienne plus qu’une dose d’eau.
2. Puis, on verse de l’eau du deuxième verre dans le troisième jusqu’à ce qu’il (le deuxième) ne contienne plus qu’une dose d’eau.
3. Puis, on verse de l’eau du troisième verre dans le quatrième jusqu’à ce qu’il (le troisième) ne contienne plus qu’une dose d’eau.
Et ainsi de suite... jusqu’au dernier verre.

L’énoncé de la stratégie, tel que je l’ai rédigé, suppose implicitement qu’il y a au moins quatre verres, mais si ce n’est pas le cas, il suffit bien sûr de supprimer les phrases superflues. Peu importe. Demandons-nous plutôt ce qu’il faut faire pour démontrer que la stratégie fonctionne ? Il y a plusieurs points qui peuvent poser problème. Par exemple, dès la première étape, il faut que nous nous assurions que le premier verre contient au moins une dose d’eau. De même, pour être certain de pouvoir réaliser la seconde étape, il faut s’assurer qu’après le mouvement de la première étape, il y a dans le deuxième verre au moins une dose d’eau. Pareillement, il faut aussi s’assurer qu’après les mouvements de la première et de la deuxième étape, il y a dans le troisième verre au moins une dose d’eau. Et ainsi de suite jusqu’à l’avant-dernier verre. Finalement, il restera à démontrer qu’il y a bien à la fin de la manipulation une dose d’eau dans chaque verre. Dans tous les cas, on se rend compte qu’il y a au moins autant d’affirmations à démontrer qu’il y a de verres dans la rangée... ce qui ne semble pas du tout évident ! Malgré tout, nous allons y parvenir en utilisant ce que les mathématiciens appellent la démonstration par récurrence. Ceci signifie que, plutôt que de démontrer directement ce que l’on souhaite, nous allons passer par un chemin légèrement détourné et démontrer les deux assertions qui suivent

  • Initialisation : la stratégie fonctionne lorsqu’il y a un unique verre ;
  • Hérédité : pour tout nombre entier $n$, si la stratégie fonctionne lorsqu’il y a $n$ verres, elle fonctionne aussi lorsqu’il y a $n+1$ verres [3].

Avant de rentrer dans le vif du sujet, essayons de nous convaincre que si l’on arrive effectivement à démontrer ces deux affirmations, on aura bien démontré ce que l’on voulait, c’est-à-dire que la stratégie fonctionne quel que soit le nombre de verres. D’après l’initialisation, la stratégie fonctionne lorsqu’il y a un verre. Fort de ce résultat, on peut appliquer la phrase d’hérédité avec $n = 1$, et on déduit que la stratégie fonctionne avec deux verres. On applique alors à nouveau la phrase d’hérédité, mais cette fois-ci avec $n = 2$, et comme ceci on déduit que la stratégie fonctionne avec trois verres. Et ainsi de suite, on démontre bien que la stratégie fonctionne quel que soit le nombre de verres.

Concentrons-nous maintenant sur la démonstration des phrases d’initialisation et d’hérédité. Pour l’initialisation, cela est immédiat : lorsqu’il y a un unique verre, l’équilibre est déjà fait et donc, en ne faisant rien comme le précise la stratégie, on aboutit à la situation désirée. Pour démontrer l’hérédité, on fixe un nombre entier $n$, on suppose que l’on sait déjà démontrer que la stratégie fonctionne pour $n$ verres et on veut démontrer que c’est encore le cas lorsqu’il y a $n+1$ verres. Il semble intéressant à ce niveau d’établir un lien entre la stratégie avec $n+1$ verres et celle avec $n$ verres. Le lemme suivant répond à la question.

Lemme 2
Appliquer la stratégie avec $n+1$ verres revient
  • à verser de l’eau du premier verre dans le deuxième jusqu’à ce qu’il (le premier) ne contienne plus qu’une dose d’eau, puis
  • à effacer mentalement le premier verre, et appliquer la stratégie (avec $n$ verres) aux $n$ verres restants.

Ce lemme vous paraît peut-être évident, mais sa démonstration cache quand même une belle subtilité : il s’agit de vérifier que le volume d’une dose — qui rappelons-le, dépend de la configuration — est le même lorsqu’il est calculé avec la configuration initiale avec $n+1$ verres et lorsqu’il est calculé avec la configuration à laquelle on applique la stratégie à $n$ verres ! Vérifions-le donc. Pour éviter au plus possible de nous embrouiller, appelons ancienne dose la dose correspondant à la configuration initiale à $n+1$ verres, et appelons nouvelle dose la dose correspondant à la configuration à laquelle on applique la stratégie à $n$ verres. Bien sûr, la dose d’eau dont il est question dans la première étape correspond à l’ancienne dose, puisque de toute façon la nouvelle n’est à ce niveau pas encore définie. Par définition de la dose, il y a en tout $n+1$ anciennes doses de liquide. Après le premier mouvement, il y a une ancienne dose dans le verre de gauche, et donc il reste $n$ anciennes doses dans les autres verres. Ainsi, si l’on efface le premier verre, il reste $n$ anciennes doses pour $n$ verres, ce qui signifie que la nouvelle dose est égale à l’ancienne dose.

Nous sommes maintenant prêts à démontrer l’hérédité. Nous devons démontrer qu’il est possible d’accomplir les deux étapes de la stratégie telle que reformulée dans le lemme, c’est-à-dire que :

  • il y a au moins une dose d’eau dans le premier verre, et
  • il est possible d’appliquer la stratégie à la configuration à $n$ verres que l’on obtient après avoir fait le premier mouvement puis effacé le premier verre ; autrement dit, les contraintes correspondant à cette configuration sont toutes satisfaites.

Pour le premier point, on se souvient que par hypothèse, il y a dans les $n$ derniers verres au plus $n$ doses d’eau. Comme il y a $n+1$ doses en tout, c’est que le volume d’eau contenu dans le premier verre est au moins égal à une dose. Passons maintenant au deuxième point : on souhaite démontrer que
dans la configuration restante après avoir accompli l’étape 1 et supprimé le premier verre :

  • le dernier verre contient au plus une dose d’eau
  • les deux derniers verres contiennent (à eux deux) au plus deux doses d’eau
  • les trois derniers verres contiennent (à eux trois) au plus trois doses d’eau
  • ...
  • les $n$ derniers verres contiennent (à eux tous) au plus $n$ doses d’eau.

Pour la dernière assertion il suffit de remarquer, qu’après l’étape 1, il y a exactement une dose d’eau dans le verre effacé, et donc qu’il reste exactement $n$ doses d’eau pour les autres, c’est-à-dire pour les $n$ derniers. Les autres assertions s’obtiennent, quant à elles directement, une fois que l’on a noté qu’elles ne concernent pas les deux premiers verres, mais que l’étape 1, quant à elle, ne modifie que la quantité d’eau de ces verres-ci.

Ainsi se termine la démonstration de l’hérédité, et par là-même celle du bon fonctionnement de la stratégie dans notre cas particulier à une ligne.

Passage au cas bidimensionnel

Nous en arrivons donc au cas du rectangle quelconque (pouvant avoir plusieurs lignes). Bien que la méthode générale suive grosso modo les mêmes idées, il faut avouer qu’elle est incomparablement plus difficile à mettre en œuvre et mérite sans doute une piste rouge (même si les notions supposées connues ne vont pas au delà de la manipulation simple d’expressions algébriques). Si vous avez déjà un peu mal à la tête à ce stade de l’article, je vous conseille donc de passer directement au prochain chapitre Conclusion, quitte bien entendu à revenir sur cette partie lorsque vous aurez l’esprit un peu plus frais.

Diagrammes de Young.
Comme précédemment, notre idée directrice est d’effacer les verres un par un. Toutefois, on voit déjà un problème technique surgir à ce niveau du raisonnement : lorsqu’on retire une case à un rectangle, la figure résultante n’est en général plus du tout un rectangle, et donc ne relève pas a priori du cadre que nous nous sommes fixé. Nous allons donc avoir besoin de raisonner sur des figures plus générales que les rectangles, qui sont ce que les mathématiciens appellent les diagrammes de Young [4]. Nous avons en fait déjà largement manipulé ces bestioles dans cet article puisque ce sont exactement les zones rouges qui apparaissaient tantôt, c’est-à-dire les zones situées à droite d’une certaine ligne brisée convenable. Appelons surface d’un diagramme de Young le nombre de cases qu’il contient.

GIF - 2.8 ko

Afin de pouvoir progresser dans notre démonstration, nous avons besoin de dégager un certain nombre de propriétés (très classiques) des diagrammes de Young. La première d’entre elles est plutôt une définition alternative de ces objets qui ne fait aucune référence à la notion de ligne brisée convenable. Elle dit qu’un diagramme de Young n’est rien d’autre qu’un ensemble de cases du damier possédant la propriété suivante : si une case est dans le diagramme, alors toutes les cases situées à sa droite, ainsi que toutes celles situées en-dessous d’elle font également partie du diagramme. En guise d’exercice, je vous propose de vous convaincre que les deux définitions sont équivalentes.
Un coin d’un diagramme de Young est une case qui n’a aucune voisine à sa gauche, et aucune au-dessus dans le diagramme (voir figure ci-contre). Il est assez évident que tout diagramme de Young (non vide) possède au moins un coin ; on peut par exemple prendre la case la plus à gauche située dans la première ligne du diagramme. Avec notre seconde définition, il est aussi à peu près clair que lorsqu’on retire un coin d’un diagramme de Young, on obtient encore un diagramme de Young (sauriez-vous expliquer pourquoi ?).

GIF - 11 ko

On peut aussi — et on aura besoin de — faire des opérations plus complexes sur les diagrammes de Young que juste retirer un coin. Par exemple, étant donné deux diagrammes de Young $D_1$ et $D_2$ inclus dans un même rectangle (ou même, comme sur la figure ci-contre, inclus dans un autre diagramme de Young), nous pouvons définir les deux nouveaux ensembles de cases suivants :

  • l’intersection de $D_1$ et $D_2$ notée $D_1 \cap D_2$ qui réunit toutes les cases qui sont à la fois dans $D_1$ et $D_2$
  • la réunion de $D_1$ et $D_2$ notée $D_1 \cup D_2$ qui réunit les cases qui sont dans $D_1$ ou dans $D_2$
Lemme 3
Si $D_1$ et $D_2$ sont des diagrammes de Young inclus dans un même rectangle, alors $D_1 \cap D_2$ et $D_1 \cup D_2$ sont encore des diagrammes de Young.

Démontrons le lemme, en commençant par exemple par $D_1\cap D_2$. Pour cela, on choisit arbitrairement une case dans $D_1 \cap D_2$ (c’est-à-dire par définition à la fois dans $D_1$ et $D_2$) et on souhaite démontrer que toutes les cases à droite et en dessous de celle-ci sont encore dans $D_1 \cap D_2$. Mais, puisque $D_1$ et $D_2$ sont des diagrammes de Young, ces cases sont dans $D_1$ et $D_2$ ; elles sont donc dans l’intersection comme voulu. Pour la réunion $D_1 \cup D_2$, l’argument est tout à fait analogue, et je vous laisse le rédiger par vous-même.

GIF - 3.7 ko
Lemme 4
On considère $D$ un diagramme de Young inclus dans un damier rectangulaire et $c$ une case du damier qui n’est pas dans $D$ mais dont les voisines de droite et de dessous (si elles existent) sont dans $D$.

Alors l’ensemble $D'$ obtenu en ajoutant à $D$ la case $c$ est un diagramme de Young.

La démonstration est à nouveau relativement simple : il s’agit de fixer une case $c'$ dans $D'$ et de montrer que toutes les cases à droite ou en-dessous de $c'$ appartient encore à $D'$. Il y a deux cas. Si $c'$ est dans $D$, alors les voisines en question sont dans $D$ (puisque $D$ est un diagramme de Young) et donc aussi dans $D'$. Sinon, c’est que $c'$ est la case $c$. Mais alors, sa voisine immédiatement à droite est dans $D$ par l’hypothèse du lemme et donc, en utilisant à nouveau que $D$ est un diagramme de Young, il en est de même de toutes les cases situées à sa droite. Pareillement, on démontre que toutes les cases situés en dessous de $c$ sont dans $D$, ce qui est bien ce qu’il fallait faire.

Généralisation du problème de gestion d’eau.
À partir de maintenant, et simplement pour les besoins de la démonstration, nous n’allons plus travailler simplement dans le contexte des rectangles, mais dans celui des diagrammes de Young. Afin de pouvoir continuer, nous allons donc avoir besoin de généraliser la condition suffisante du lemme 1 à notre nouveau cadre. Pour cela, on n’a d’autre choix que de reprendre complètement l’argumentation du chapitre Recherche de contraintes en remplaçant partout les damiers rectangulaires par des damiers en forme de diagramme de Young. Par chance, aucune difficulté supplémentaire n’apparaît et, avec un peu de persévérence, on montre l’équivalent du lemme 1 qui s’énonce ainsi.

Lemme 5
Fixons une configuration initiale sur un damier en forme de diagramme de Young. S’il existe un (autre) diagramme de Young inclus dans le damier accueillant un volume d’eau (exprimé en doses) strictement supérieur à sa surface, alors l’opération d’équilibrage est impossible.

On peut — et cela sera utile pour la suite — reformuler ce lemme de façon un peu plus mathématique. Pour cela notons, lorsque $D$ désigne un diagramme de Young inclus dans le damier, $S(D)$ sa surface et $V(D)$ le volume d’eau total, exprimé en dose, qu’il y a dans les verres sur les cases de $D$. Contrairement à $S(D)$, la quantité $V(D)$ dépend non seulement du diagramme de Young, mais aussi du remplissage des verres. Le lemme se reformule alors ainsi :

Lemme 6
Fixons une configuration initiale sur un damier en forme de diagramme de Young. S’il existe un diagramme de Young $D$ inclus dans le damier pour lequel $V(D) > S(D)$, alors l’opération d’équilibrage est impossible.

La démonstration proprement dite.
Nous voulons à présent nous intéresser aux configurations initiales pour lesquelles les contraintes sont satisfaites, c’est-à-dire pour lesquelles $V(D) \leq S(D)$ pour tout diagramme de Young $D$ inclus dans le damier. Sans grande surprise, nous allons démontrer qu’il est toujours possible d’arriver à une position dans laquelle tous les verres du damier sont également remplis.

Voici la trame de la stratégie que nous allons utiliser.

Trame de la stratégie
1. On fixe un coin du diagramme (par exemple la case située la plus à gauche sur la première ligne), on prend le verre dans ce coin, et on verse une certaine quantité (exprimée en dose) $x$ de son contenu dans le verre situé immédiatement à sa droite (s’il existe), et une certaine quantité $y$ de son contenu dans le verre situé immédiatement en-dessous (s’il existe).
2. On repose le verre à sa place, on l’efface mentalement et on réapplique la stratégie à la configuration restante (qui compte un verre de moins, donc).

Pourquoi s’agit-il d’une trame de stratégie, et non d’une stratégie ? Tout simplement car elle ne précise pas les quantités $x$ et $y$ que l’on doit verser ; on serait donc bien en mal d’appliquer ces consignes à la lettre. Pour prendre un analogie culinaire, imaginez une recette qui demanderait de verser un peu de lait, de mélanger avec quelques œufs et une bonne dose de farine, avant de mettre tout ça au four un certain temps. Cela semble du délire : une recette de cuisine se doit de préciser les quantités, la durée de cuisson, etc. Ici, c’est exactement pareil : nous avons le devoir de préciser au manipulateur (au cuisinier) quelles quantités verser.

Nous cherchons donc à présent des nombres $x$ et $y$ — qui bien sûr vont certainement dépendre de la configuration initiale — pour lesquelles la trame de stratégie précédente devient une véritable stratégie qui fonctionne. Comme dans le cas du rectangle à une seule ligne, on raisonne par récurrence sur le nombre de cases du damier. L’initialisation ne pose comme précédemment aucun problème : il y a alors une unique case et l’équilibre est déjà fait. Nous passons donc directement à l’hérédité ; autrement dit, on suppose que le problème est déjà résolu lorsque l’on va réappliquer la stratégie... évidemment, pourvu que les hypothèses soient satisfaites. Ainsi dire que la stratégie fonctionne signifie que :

  • il est possible de réaliser l’étape 1, et à l’issue de celle-ci, le verre situé dans le coin choisi contient exactement un volume d’eau égal à une dose ;
  • la configuration obtenue après l’etape 1 et après avoir retiré la coin choisi vérifie encore $V(D) \leq S(D)$ pour tout diagramme de Young $D$ ;
  • la configuration obtenue au final (après l’étape 2) est équilibrée.

Même si le dernier point est peut-être celui qui vous paraît le plus évident, il cache, comme dans le cas du précédent chapitre, une subtilité relative à la notion de dose. En effet, il y a a priori une ambiguïté à son sujet car celle-ci peut être calculée soit par rapport à la configuration initiale — on parlera alors d’« ancienne dose » — , soit par rapport à la configuration que l’on obtient après avoir effectué l’etape 1 puis retiré la case $c$ — on parlera alors de « nouvelle dose ». Or, après avoir terminé les deux étapes de la stratégie :

  • il y a, dans le verre de la case $c$ un volume d’eau égal à une ancienne dose, et
  • (en supposant que la stratégie fonctionne pour un damier comptant une case de moins), il y a dans les autres verres une quantité d’eau égale à une nouvelle dose.

Il nous faut démontrer que l’ancienne dose est égale à la nouvelle dose. On procède comme dans le chapitre précédent, en argumentant ainsi. Si le diagramme de Young complet (avec la case $c$) compte $n+1$ cases, il y a en tout par définition $n+1$ anciennes doses d’eau. Après le mouvement de l’étape 1 et le retrait $c$, il reste donc $n$ ancienne doses d’eau (puisqu’à l’étape 1 a pour finalité de laisser une ancienne dose d’eau dans le verre situé sur la case $c$) et $n$ verres, ce qui assure que la nouvelle dose s’égalise avec l’ancienne.

GIF - 4.9 ko

Venons-en à présent à la démonstration des deux autres points que nous avons soulevés. Il devient nécessaire à ce niveau, pour ne plus alourdir de façon démesurée le texte, de donner des noms aux objets que l’on va manipuler dans la suite. Ainsi, nous appellerons $c$ le coin choisi, et $c_x$ et $c_y$ les cases situées respectivement juste à droite et juste en-dessous de $c$ (si elles existent). Nous noterons également $v$ le volume d’eau contenu initialement dans le verre posé sur la case $c$. En outre, afin de ne pas avoir à préciser systématiquement dans la suite si les calculs de $V(D)$ sont effectuées relativement à la configuration initiale ou relativement à celle obtenue après l’étape 1 et le retrait de la case $c$, nous allons préciser cela dans l’écriture : nous noterons $V_0(D)$ lorsque le calcul sera fait à partir de la configuration initiale, et $V_1(D)$ sinon. Remarquez qu’a priori les volumes $V_0(D)$ sont exprimés en ancienne dose (puisqu’ils sont calculés en référence à la configuration initiale), alors que, de leur côté, les volumes $V_1(D)$ sont exprimés en nouvelle dose. Toutefois, comme nous avons dit que ces deux notions coïncident, nous pourrons considérer qu’ils sont exprimés dans la même unité, et nous n’aurons pas besoin de nous encombrer avec des problèmes de conversion. On prendra garde par contre au fait que les $V_1(D)$ dépendent a priori de $x$ et de $y$, contrairement aux $V_0(D)$ qui ne dépendent eux que de la configuration initiale.

Dire qu’« il est possible de réaliser l’étape 1, et à l’issue de celle-ci, le verre situé le coin choisi contient exactement un volume d’eau égal à une dose » se traduit simplement dans notre nouveau langage par les formules
\[x \geq 0, \quad y \geq 0 \quad \text{et} \quad v - x - y = 1.\]
De même dire que « la configuration obtenue après l’etape 1 et après avoir retiré le coin choisi vérifie encore $V(D) \leq S(D)$ pour tout diagramme de Young $D$ » s’écrit $V_1(D) \leq S(D)$ pour tout tel diagramme [5]. Le problème revient donc à démontrer qu’il existe des nombres $x$ et $y$ satisfaisant toutes ces conditions. Commençons par essayer de comprendre un peu mieux celles faisant intervenir les diagrammes de Young $D$. Il y a quatre cas à distinguer.

  • Premier cas : $D$ ne contient ni la case $c_x$ ni la case $c_y$. Alors, comme le mouvement de l’étape 1 ne modifie que le contenu des cases $c$, $c_x$ et $c_y$, on a $V_1(D) = V_0(D) $. Comme par hypothèse $V_0(D) \leq S(D)$, la condition est, dans ce cas, automatiquement vérifiée.
  • Deuxième cas : $D$ contient les deux cases $c_x$ et $c_y$. Alors, après l’étape 1, on a versé les volumes $x$ et $y$ de liquide à l’intérieur de $D$. Ainsi $V_1(D) = V_0(D) + x + y$. Par ailleurs, le lemme 4 montre que l’ensemble $D'$ obtenu en ajoutant la case $c$ à $D$ est encore un diagramme de Young. Ainsi, a-t-on $V_0(D') \leq S(D')$. Par ailleurs $S(D') = S(D) + 1$ et $V_0(D') = V_0(D) + v$. On en déduit
    \[\begin{array}{rcl} V_1(D) & = & V_0(D') - v + x + y \, \leq \, S(D') - v + x + y \\ & = & S(D) + 1 - v + x + y \, = \, S(D) + 1 - (v-x-y) \end{array}\]
    Ainsi, si l’on arrive à trouver $x$ et $y$ vérifiant $v - x - y = 1$ (qui est ce que l’on souhaite), la condition $V_1(D) \leq S(D)$ sera automatiquement satisfaite. On n’a donc pas à s’en soucier.
  • Troisième cas : $D$ contient la case $c_x$, mais pas la case $c_y$. On a alors $V_1(D) = V_0(D) + x$, et la condition devient $x \leq S(D) - V_0(D)$.
  • Quatrième cas : $D$ contient la case $c_y$, mais pas la case $c_x$. De même que précédemment, on obtient $y \leq S(D) - V_0(D)$.

Parmi tous les diagrammes de Young $D$ contenant $c_x$ mais pas $c_y$, il y en a certainement un pour lequel la quantité $V_0(D) - S(D)$ est minimale ; notons $D_x$ ce diagramme. De même, parmi tous les diagrammes de Young $D$ contenant $c_y$ mais pas $c_x$, il y en a un pour lequel la quantité $V_0(D) - S(D)$ est minimale, et on le note $D_y$. On est ainsi ramené à démontrer qu’il existe des nombres $x$ et $y$ vérifiant
\[\left\{ \begin{array}{l} 0 \leq x \leq S(D_x) - V_0(D_x) \\ 0 \leq y \leq S(D_y) - V_0(D_y) \\ x+y = v - 1 \end{array} \right.\]
En fait, il suffit pour cela de démontrer les quatre inégalités suivantes [6]

  • $S(D_x) - V_0(D_x) \geq 0$
  • $S(D_y) - V_0(D_y) \geq 0$
  • $v - 1 \geq 0$
  • $S(D_x) - V_0(D_x) + S(D_y) - V_0(D_y) \geq v - 1$

Les deux premières ne posent aucun problème puisqu’elles découlent directement de notre hypothèse (on rappelle que l’on a bien supposé $V_0(D) \leq S(D)$ pour tout diagramme de Young $D$ inclus dans le damier). La suivante est déjà un peu plus délicate. Notons $D_1$ le diagramme de Young réunissant toutes les cases du damier, et $D_2$ celui obtenu en retirant uniquement la case $c$. Clairement, $V_0(D_1) = V_0(D_2) + v$ et $S(D_1) = S(D_2) + 1$. Par ailleurs, la définition d’une dose nous dit que $S(D_1) = V_0(D_1)$, d’où on trouve
\[v - 1 = [V_0(D_1) - V_0(D_2)] - [S(D_1) - S(D_2)] = S(D_2) - V_0(D_2) \geq 0\]
comme souhaité.

La dernière inégalité est encore plus difficile. Pour la vérifier, introduisons les diagrammes de Young $D_x \cap D_y$ et $D_x \cup D_y$. La surface de $D_x \cup D_y$ se calcule ainsi : on commence par additionner $S(D_x)$ et $S(D_y)$, mais ce n’est pas tout car, si on s’arrête ici, on aura compté deux fois les cases de $D_x \cap D_y$, il faut donc encore soustraire $S(D_x \cap D_y)$. On obtient finalement la formule $S(D_x \cup D_y) = S(D_x) + S(D_y) - S(D_x \cap D_y)$, soit encore $S(D_x) + S(D_y) = S(D_x \cup D_y) + S(D_x \cap D_y)$. Le même raisonnement est valable avec les volumes et conduit à $V_0(D_x) + V_0(D_y) = V_0(D_x \cup D_y) + V_0(D_x \cap D_y)$. Par ailleurs, étant donné que $c_x$ et $c_y$ appartiennent à $D_x \cup D_y$, on conserve un diagramme de Young si l’on ajoute à $D_x \cup D_y$ la case $c$ (c’est le lemme 4). Appelons $D$ ce nouveau diagramme, et remarquons que $S(D_x \cap D_y) = S(D) - 1$ et $V_0(D_x \cup D_y) = V_0(D) - v$. On a alors
\[\begin{array}{rcl} & & S(D_x) - V_0(D_x) + S(D_y) - V_0(D_y) \\ & = & [S(D_x) + S(D_y)] - [V_0(D_x) + V_0(D_y)] \\ & = & [S(D_x \cup D_y) + S(D_x \cap D_y)] - [V_0(D_x \cup D_y) + V_0(D_x \cap D_y)] \\ & = & [S(D) - 1 + S(D_x \cap D_y)] - [V_0(D) - v + V_0(D_x \cap D_y)] \\ & = & [S(D) - V_0(D)] + [S(D_x \cap D_y) - V_0(D_x \cap D_y)] + (v-1) \, \geq \, v-1. \end{array}\]
CQFD [7]

Conclusion

Ouf, c’est terminé ! Établissons quand-même un bilan pour nous assurer que nous avons bien démontré tout ce dont nous désirions. Dans les parties Une première observation et Recherche de contrainte, nous avons formulé un certain nombre de contraintes, et démontré que si elles n’étaient pas toutes réalisées, l’équilibrage était impossible à réaliser. Nous avons ensuite démontré — et ce n’était pas une mince affaire — qu’au contraire, si toutes les contraintes étaient satisfaites, alors l’équilibrage était possible en expliquant, cerise sur le gâteau, comment le réaliser. Nous savons donc répondre dans tous les cas. Pour couronner nos efforts et mettre en valeur le résultat obtenu, il est courant en mathématiques d’énoncer un théorème [8]. Nous n’allons donc pas déroger à cette règle.

Théorème
La réponse à la question posée dans la partie L’énoncé du problème est affirmative si, et seulement si, pour tout découpage du damier par une ligne brisée convenable (voir définition 2), le volume d’eau présent initialement à droite de la ligne brisée, lorsqu’il est exprimée en doses (voir définition 1), n’excède pas le nombre de cases situées à droite de la ligne brisée.

Une remarque d’ordre rédactionnelle : le plus souvent, on essaie de faire en sorte que l’énoncé d’un théorème soit le plus possible indépendant du reste du texte, ceci afin de permettre au lecteur de commencer par lire le résultat principal puis de décider en fonction de cela si, oui ou non, il prend le courage de lire le reste, typiquement de s’investir dans la démonstration. Ici, il n’était à vrai dire pas vraiment raisonnable de pousser cette ligne de conduite jusqu’au bout : il aurait fallu répéter entièrement l’énoncé du problème ainsi que les définitions de dose et de ligne brisée convenable. Un choix qui s’impose souvent est celui que j’ai fait ici : on suppose certaines notions connues mais, le cas échéant, on renvoie aux parties de l’article où elles sont définies.

Finissons par un petit commentaire sur la locution « si, et seulement si » qui apparaît dans l’énoncé du théorème. Pour bien comprendre sa signification, lisons la phrase en la remplaçant une fois par « si » et une autre fois par « seulement si ». Dans le premier cas, on obtient « La réponse à la question [...] est affirmative si pour tout découpage [...] », ce qui fait donc référence au fait que la condition est suffisante ou, si vous préférez, à la seconde partie de la preuve. Au contraire, l’assertion « La réponse à la question [...] est affirmative seulement si pour tout découpage [...] » signifie que l’opération est impossible dans le cas où une des contraintes n’est pas satisfaite. On fait donc référence cette fois-ci à la première partie de la preuve, i.e. à la nécessité de la condition. Ceci est une vérité générale : la conjonction « si » précède toujours une condition suffisante, au contraire de « seulement si » qui sert à introduire une condition nécessaire.

Pourquoi ai-je choisi ce problème ?

Plusieurs raisons à cela. En voici quelques unes.

Il s’agit d’un problème qui porte sur des objets de la vie de tous les jours (les verres et de l’eau) et pas a priori sur des concepts mathématiques abstraits : on n’a besoin d’aucune connaissance mathématique particulière pour comprendre son énoncé. Pourtant, il en va tout autrement lorsque l’on se penche sur sa résolution. Cela illustre assez bien à mon sens que les mathématiques s’imposent souvent d’elles-même dans des situations où elles n’étaient au départ pas vraiment attendues. Elles ne sont donc pas qu’un mal nécessaire à ingurgiter pour réussir à l’école.

La démonstration que j’ai présentée permet d’introduire des notions fondamentales de raisonnement. Il est vrai que certaines sont très reliées aux mathématiques, comme la récurrence. Mais d’autres ne le sont pas du tout. Je pense notamment aux notions de conditions nécessaires et suffisantes — ou, ce qui revient au même, aux locutions « si » et « seulement si » — qui apparaissent dès que l’on souhaite mener un raisonnement... et qui d’ailleurs sont malheureusement parfois très malmenées en dehors du monde mathématique. À ce sujet, une petite question pour voir si vous avez bien compris : d’après vous une condition sine qua non (littéralement « sans quoi non ») est-elle une condition nécessaire ou une condition suffisante ?

Voir la réponse

Une condition nécessaire.

Si vous n’avez pas sauté le chapitre Le cas bidimensionnel, vous vous rappelez certainement que pour les besoins de la démonstration, nous avons dû généraliser le problème en passant du cadre des rectangles à celui des diagrammes de Young. C’est en fait un phénomène qui revient plus ou moins couramment en mathématiques : parfois, un problème est trop ardu, et c’est seulement en l’englobant dans une plus grande généralité que la solution apparaît. Contrairement à certaines idées reçues, je ne crois pas que les mathématiciens fassent de la généralisation pour le plaisir ; la généralisation, au contraire, s’impose très souvent d’elle-même comme ici.

Récemment, pour ma recherche, j’œuvrais à comprendre le comportement des dimensions de certaines variétés de Deligne-Lusztig affines généralisées et, de fil en aiguille, j’en suis arrivé à me poser la question traitée dans cet article. Ce problème, qui semblait à première vue plus une amusette qu’autre chose, est donc lié de très près à des problèmes contemporains d’arithmétique ! Bien entendu, la question telle que je l’ai rencontrée ne concernait pas directement des verres d’eau disposés en rectangle, mais demandait plutôt de calculer la H-représentation d’un certain cône convexe défini par générateurs... mais j’imagine que vous comprendrez sans mal que j’ai souhaité, pour cet article, la reformuler en termes plus accessibles au profane. À vrai dire, je triche un peu : la question qui est apparue dans mes travaux n’est pas exactement équivalente à celle que j’ai traitée ici, mais correspond plutôt au cas où les verres sont disposés en triangle, les règles de transvasement étant inchangées. Par exemple

Saurez-vous vous inspirer de la démonstration que je viens de donner pour résoudre ce nouveau problème ?

Article édité par Étienne Ghys

Notes

[1L’emploi de « suffit » signifie simplement qu’il est suffisant de faire ce que l’on dit. Si vous préférez, si l’on parvient à faire ce que l’on dit, alors on a gagné. Cela ne sous-entend pas du tout — comme c’est souvent le cas en français courant — que c’est facile ! Nous verrons d’ailleurs dans la suite que c’est le point le plus délicat de notre démonstration.

[2C’est assez évident si l’on a bien compris les règles du jeu, mais c’est peut-être encore plus clair si l’on pense en termes de château d’eau. Le château d’eau en haut à gauche, i.e. le plus au Nord-Ouest, est aussi le plus en altitude ; il ne peut donc recevoir de l’eau d’aucun des autres châteaux d’eau.

[3Voici une autre formulation qui évite les $n$ : si la stratégie fonctionne lorsqu’il y a un certain nombre de verres, alors elle fonctionne aussi s’il y en a un de plus. Dans la suite, je continuerai à utiliser la lettre $n$. Si cela perturbe votre lecture, vous ne perdrez pas grande chose à le remplacer partout par votre nombre préféré, par exemple 42. Bien entendu, dans ce cas les $n+1$ seront remplacés par 42 + 1, c’est-à-dire 43.

[4Les diagrammes de Young sont des objets mathématiques très importants qui interviennent dans de nombreux problèmes de combinatoire, ainsi que dans d’autres domaines des mathématiques modernes.

[5À partir de maintenant, sauf mention explicite du contraire, les diagrammes de Young considérés seront supposés inclus dans le damier privé de la case $c$ ; ainsi, par exemple, lorsque l’on écrira « pour tout diagramme de Young », il faudra comprendre que l’on ne retient que les diagrammes ayant cette propriété.

[6Si cela — le fait que les quatre inégalités qui suivent suffisent à assurer l’existence de $x$ et $y$ — ne vous paraît pas évident, je vous invite à réinterpréter le problème en termes de déplacements d’eau comme suit. On se donne deux verres contenant respectivement des volumes d’eau égaux à $S(D_x) - V_0(D_x)$ et $S(D_y) - V_0(D_y)$ (supposés positifs) et on se demande s’il est possible d’utiliser cette eau (et uniquement celle-ci) pour remplir un troisième verre dont le volume est $v-1$ (également supposé positif) ; les nombres $x$ et $y$ correspondent alors aux quantités d’eau prélevées respectivement dans le premier et le deuxième verre. En ces termes, il est à peu près évident que la seule contrainte est qu’il y ait assez d’eau, c’est-à-dire que $S(D_x) - V_0(D_x) + S(D_y) - V_0(D_y) \geq v-1$, ce qui est exactement l’inégalité que nous nous proposons de démontrer.

[7Ce Qu’il Fallait Démontrer.

[8En fait, souvent le théorème s’énonce avant la démonstration et sert à annoncer un résultat précis, et par là-même fixer le cap du raisonnement. Malgré tout, je ne pense pas que cela s’imposait pour cet article puisque la question posée au début était à mon sens suffisante pour fixer un cap, et il aurait été dommage, trouvé-je, de donner la réponse d’emblée d’autant plus qu’elle est un peu technique.

Partager cet article

Pour citer cet article :

Xavier Caruso — «Un problème de remplissage de verres» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Un problème de remplissage de verres

    le 9 septembre 2009 à 22:59, par ospoz

    Merci beaucoup pour cet excellent article. Il serait très intéressant d’avoir plus d’articles de ce type.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM