Un algorithme de découpe de gâteau

Pour couper un gâteau en parts égales, on pourrait bien sûr utiliser une règle graduée. Mais le plus souvent, ne disposant que d’un couteau, comment couper le gâteau en 3 sans léser personne ? Eh bien, l’informatique répond à cette question : pour couper en 3, il suffit de savoir couper en 2.

Partager un gâteau rectangulaire

Considérons un gâteau rectangulaire, un quatre-quarts par exemple. Nous allons appliquer une méthode systématique, que les informaticiens appellent un algorithme, pour le partager en deux parties : un tiers d’un côté, deux tiers de l’autre. Pour cela, on commence par le couper en 2 parties égales et on écarte la partie droite (colorée en rouge). Cela signifie qu’on ne la coupera plus et qu’elle appartient à la partie 2/3 que l’on construit. On coupe ensuite la partie blanche en 2 et on écarte la partie gauche (colorée en jaune). Cela signifie qu’on ne la coupera plus et qu’elle appartient à la partie 1/3 que l’on construit. On coupe la partie blanche en 2 et on écarte la partie droite. On coupe la partie blanche en 2 et on écarte la partie gauche. Et ainsi de suite, on continue à couper en 2 la partie blanche restante et à écarter successivement les parties droite et gauche.

Mathématiquement, on ne devrait jamais s’arrêter, puisqu’il faut toujours recouper le morceau blanc du gâteau. En pratique, il devient rapidement impossible de recouper le gâteau, car cette partie est trop petite. Au bout d’un certain nombre de coupes, on s’arrête donc et on « recolle » les morceaux de même couleur. La partie gauche (ici jaune) est très proche du tiers du gâteau. Il reste encore à couper la partie droite (rouge) en 2 pour obtenir une découpe en 3 tout à fait acceptable.

Notez que pour des raisons purement culinaires, cette technique est déconseillée dans le cas d’un mille-feuilles. Mais bien entendu, elle permet de réaliser un gabarit en papier aux dimensions de votre gâteau !

Pourquoi ça marche ?

Pourquoi donc cet algorithme fonctionne-t-il ?

En fait, il faut revenir aux bases. Nous sommes habitués à l’écriture des nombres en base 10, ce qui correspond au fait que, quand on se déplace vers la gauche, chaque chiffre a une valeur 10 fois supérieure :

2010 = 2 . 10³ + 0 . 10² + 1 . 10¹ + 0

De façon similaire, en base 2, qu’on appelle aussi écriture binaire, chaque chiffre plus à gauche a une valeur 2 fois supérieure à la valeur de son voisin :

1001101₂ = 1 . 2⁶ + 0 . 2⁵ + 0 . 2⁴ + 1 . 2³ + 1 . 2²  + 0 . 2¹ + 1

On note XXXX₂ la représentation des nombres en base 2.
Tout nombre entier a une représentation en base 2 et en base 10. Par exemple, 1001101₂ = 73 et 2010 = 11111011010₂.

Pour les nombres réels non entiers (avec des chiffres non nuls derrière la virgule), les représentations ne sont pas équivalentes. Un exemple souvent cité est celui de 1/10 = 0,1 qui s’écrit en binaire avec un nombre infini de chiffres.

1/10 = 0,0001100110011001100110011001100110011₂…
= 0 + 0 . 2^-1 + 0 . 2^-2 + 0 . 2^-3 + 1 . 2^-4 + 1 . 2^-5 + 0 . 2^-6 + 0 . 2^-7 + 1 . 2^-8 + 1 . 2^-9 +…

Revenons à notre algorithme de découpe. On veut couper le gâteau en 3 parts égales, donc le diviser en 3. Regardons l’écriture de la fraction 1/3 en base 2 :

1/3 = 0,01010101010₂…

La valeur 1/3 représentée en base 2 est donc « 0, » suivi de « 01 » répété infiniment. Cela traduit le fait que 1/3 est la limite de la somme : 2^-2 + 2^-4 + 2^-6 +… c’est-à-dire de la somme 1/4 + 1/16 + 1/64 +…

L’écriture binaire dicte en conséquence les moitiés de part à conserver pour construire 1/3. Remplaçons les chiffres après la virgule : 0 par D et 1 par G, on obtient :

0  1  0  1  0  1  0  1  0  1  0  1  0  1  …
D G D G D G D G D G D G D G  …

À chaque fois que l’on rencontre un 0, on met le morceau coupé à droite (partie rouge), il ne fera pas partie du tiers que l’on construit. Quand on rencontre un 1, on met le morceau à gauche (partie jaune), il fera partie du tiers que l’on construit. On continue ainsi à mettre les morceaux successivement à droite et à gauche, jusqu’à ne plus pouvoir couper.

Et si on est plus nombreux ?

L’algorithme précédent s’adapte à un autre nombre de parts. Ainsi, considérons 7 convives. On écrit alors 1/7 en base 2 :

1/7 = 0,0010010010010₂…

On constate que 1/7 s’écrit « 0, » suivi d’une infinité de « 001 » répétés. Cela donne donc DDGDDGDDGD…

Pour couper en 7 parts, on coupe donc de façon successive en 2 et on met les morceaux à droite, une deuxième fois à droite, puis à gauche, de façon répétée. Une fois la première part obtenue (le premier septième), il faut encore couper le reste en 6, par exemple en le coupant en 2 puis chaque morceau en 3. Cela prend du temps (selon la précision avec laquelle on souhaite obtenir le résultat), mais on parvient à couper le gâteau en 7 parts raisonnablement égales.

Plus généralement, l’algorithme de découpe en n parts est déduit de la représentation binaire de la fraction 1/n.

L’algorithme que nous venons de décrire est un cas particulier de l’algorithme suivant, encore plus général, qui permet d’obtenir une part de taille r, avec r compris entre 0 et 1. Par exemple, pour diviser par 3, c’est-à-dire multiplier par 1/3, on applique cet algorithme avec r = 1/3 :

• Couper en 2.
• Si r < 1/2
  donc, en écriture binaire, le premier chiffre après la virgule est 0,
  mettre le morceau à droite.
• Si r ≥ 1/2
  donc, en écriture binaire, le premier chiffre après la virgule est 1,
  mettre le morceau à gauche.
• Si r ≥ 1/2,
  remplacer r par r – 1/2.
• Remplacer r par 2 r :
  en écriture binaire, cela revient à supprimer le premier chiffre après la virgule.
• Recommencer jusqu’à ce que r soit égal à 0 ou qu’on ne puisse plus couper.