Problème de partage

Un énorme gâteau est posé sur la table. Alain, passant par là, s'en régale d'avance ! Sauf que non, Bernard vient d'arriver et en veut, lui aussi. Il se trouve qu'Alain est muni d'un couteau et tue Bernard, fin de l'histoire. Non, je plaisante :) Alain est muni d'un couteau et peut partager ; cependant, Alain a une façon très particulière de partager : quelles que soient les circonstances,

(L'histoire ne dit pas qui va prendre quelle part. Comme nous allons le voir, la question ne va pas se poser...)

Ainsi donc, Alain partage le gâteau de taille supposée égale à \( 1 \) en deux parts,

  • une grosse part de taille \( t \),
  • une petite part de taille \( 1-t \).

Exemple avec \( t = \frac{2}{3} \), après partage pour Alain + Bernard :

Avant même qu'Alain ou Bernard ne choisisse sa part, voilà Charles qui arrive à son tour. Et lui aussi en veut. Alain coupe alors la grosse part \( t \) en deux sous-parts,

  • une grosse sous-part de taille \( t^2 \),
  • une petite sous-part de taille \( t (1 - t) \).

Exemple avec \( t = \frac{2}{3} \), après partage pour Alain + Bernard + Charles :

Avant même qu'Alain ou Bernard ou Charles ne choisisse sa part, voilà Damien qui arrive à son tour. Et lui aussi en veut. Se pose alors la question : quelle est la plus grosse part ?

  • il est clair que ce ne peut être la part de taille \( t (1 - t) \), qui est nécessairement plus petite que les 2 autres ; mais
  • est-ce la part de taille \( t^2 \) ?
  • est-ce la part de taille \( 1 - t \) ?

La réponse est : cela dépend de \( t \).

  • si, comme dans l'exemple illustré, \( t = 2 / 3 \), alors
    • \( (2/3)^2 = 4/9 \)
    • \( 1 - 2/3 = 1/3 = 3/9 \)
    • \( 4/9 \gt 3/9 \) donc \( t^2 \gt 1-t \) ;
  • si en revanche \( t \) vaut \( 3/5 \) par exemple, alors
    • \( (3/5)^2 = 9/25 \)
    • \( 1 - 3/5 = 2/5 = 10/25 \)
    • \( 9/25 \lt 10/25 \) donc \( t^2 \lt 1 - t \).

Il est clair qu'il existe une valeur de \( t \) comprise entre \( 3/5 = 0.6 \) et \( 2/3 = 0.6666 \dots \) pour laquelle les deux parts \( t^2 \) et \( 1 - t \) sont égales. Quelle est cette valeur de \( t \) ? On est amené à résoudre l'équation :

\[ t^2 = 1 - t \]

Et l'on trouve :

\[ t = \frac{\sqrt{5} - 1}{2} \approx 0.61803398874989484820458683436563811772 \dots \]

Vous connaissez sans doute le nombre d'or,

\[ \phi = \frac{1 + \sqrt{5}}{2} \approx 1.61803398874989484820458683436563811772 \dots \]

Le nombre \( t \) que nous avons trouvé a une parenté évidente avec \( \phi \),

\[ t = \phi - 1 = \frac{1}{\phi} \]

Bien entendu, l'histoire ne s'arrête pas là. Eric, François, Georges, ... viendront, obligeant Alain à itérer sa méthode de partage, indéfiniment.

Supposons que cette histoire se passe dans la salle d'à côté, mais à huis clos. Nous ne connaissons pas la valeur de \( t \) qui caractérise Alain. Nous ne connaissons que le nombre \( n \) de personnes, que nous voyons entrer dans la salle, l'une après l'autre. Combien existe-t-il de configurations de gâteau possibles après ces partages pour \( n \) personnes ? Par configuration, techniquement, on entend "multi-ensemble des expressions algébriques décrivant la taille des parts" :

1 personne2 personnes3 personnes4 personnes\( \dots \)\( n \) personnes

Une seule configuration :

  • \( 1 \) part de taille \( 1 \)

Une seule configuration :

  • \( 1 \) part de taille \( t \)
  • \( 1 \) part de taille \( 1 - t \)

Une seule configuration :

  • \( 1 \) part de taille \( t^2 \)
  • \( 1 \) part de taille \( t (1 - t) \)
  • \( 1 \) part de taille \( 1 - t \)

Deux configurations :

  • \( 1 \) part de taille \( t^3 \)
  • \( 1 \) part de taille \( t^2(1 - t) \)
  • \( 1 \) part de taille \( t (1 - t) \)
  • \( 1 \) part de taille \( 1 - t \)
  • \( 1 \) part de taille \( t^2 \)
  • \( 2 \) parts de taille \( t (1 - t) \)
  • \( 1 \) part de taille \( (1 - t)^2 \)

\( \dots \)

?

Il est clair que toutes les expressions algébriques donnant la taille des parts sont de la forme :

\[ t^a (1-t)^b \]

avec \( a \) et \( b \) entiers naturels. Traçons les courbes d'équations \( y = t^a (1-t)^b \) pour les petites valeurs de \( a \) et \( b\) :

Mais à vrai dire, on ne s'intéresse qu'à l'intervalle \( t \in \left [ \frac{1}{2}, 1 \right ]\), par conséquent :

Quand \( n = 1 \), la configuration est unique et correspond au segment de droite rouge.

Quand \( n = 2 \), le segment de droite rouge se fait remplacer par 2 segments de droite bleus, \( t \) et \( 1 - t \). Par ailleurs, \( t \) domine \( 1 - t \). Il n'y a qu'une seule configuration.

Quand \( n = 3 \), la courbe bleue qui était dominée (\(1 - t\)) reste tandis que la courbe bleue qui dominait (\( t \)) se fait remplacer par 2 courbes vertes, \( t^2 \) et \( t(1 - t) \). Il n'y a qu'une seule configuration.

Les prémisses d'une disjonction des cas sont perceptibles : pour \( t \lt \phi - 1 \), la courbe \( 1-t \) domine la courbe \( t^2 \) mais pour \( t \gt \phi - 1 \), c'est l'inverse.

Quand \( n = 4 \),

  • si \( t \lt \phi - 1 \), la courbe bleue \( 1 - t \) a disparu : elle s'est fait remplacer par 2 courbes vertes, \( t(1 - t) \) et \( (1 - t)^2 \). A noter que la courbe verte \( t(1 - t) \) compte désormais double (on l'avait déjà simplement, avant).
  • si \( t \gt \phi - 1 \), la courbe verte \( t^2 \) a disparu : elle s'est fait remplacer par 2 courbes oranges \( t^2 (1 - t) \) et \( t^3 \) .

Il y a deux configurations.

Dans la configuration \( t \gt \phi - 1 \), les prémisses d'une disjonction des cas sont perceptibles : la courbe bleue \( 1 - t \) et la courbe orange \( t^3 \) se partagent la domination de l'intervalle \( \left [ \phi - 1, 1 \right ] \). Elle s'intersectent au point d'abscisse \( t \) satisfaisant l'équation

\[ t^3 = 1 - t \] \[ t \approx 0.6823278038280193273694837397110482568 \dots \]

Cela devient vite assez compliqué de poursuivre à la main. Voici ce à quoi ressemble le tracé de toutes les courbes \( t^a (1-t)^b \) pour \( a + b \leq 25 \) :

Je trouve plus esthétique la version modifiée ci-contre à droite, où au lieu de représenter \( t^a (1-t)^b \), on représente \( \ln \left( t^a (1-t)^b \right) \) : l'échelle est logarithmique en ordonnées.

On voit clairement apparaître verticalement des "colliers de perles en forme de losange"...

Version LOGARITHMIQUE

Avant de changer de sujet : j'ai fait de ce problème de gâteau à partager une suite sur OEIS : A341534.

Hop, sérendipité : la dernière illustration semble beaucoup plus intéressante que le problème initial. Que peut-on en dire ?

Soient deux courbes de la famille, i.e. deux couples \( (a, b), (a', b') \) d'entiers naturels et

A quelle condition ces 2 courbes s'intersectent-elles sur l'intervalle \( ]0, 1[ \) ? L'équation à résoudre est :

\[ t^a (1-t)^b = t^{a'} (1-t)^{b'} \]

qui se réécrit aussi :

\[ t^{a-a'} (1-t)^{b-b'} = 1 \]

L'existence et la valeur de solutions éventuelles ne dépend que de \( a - a' \) et de \( b - b' \). Il paraît donc naturel de définir

\[ \Delta a = a - a' \] \[ \Delta b = b - b' \]

pour se ramener à l'équation

\[ t^{\Delta a} (1-t)^{\Delta b} = 1 \]

En procédant par disjonction des cas,

\[ t^{|\Delta a|} = (1-t)^{|\Delta b|} \]

Petit changement de notations,

\[ p = |\Delta a| \] \[ q = |\Delta b| \]

Nous nous intéressons maintenant aux équations :

\[ t^p = (1-t)^{q} \]

Fonction \( \xi \) qui à la solution de \( t^p = (1-t)^q \) dans \( [0, 1[ \), associe \( \frac{p}{q} \)

Il semblerait qu'à chaque "collier de perles en forme de losange" C soient associés 2 nombres :

  • l'abscisse de C, autrement dit la racine \( t \) de l'équation \( t^p = (1-t)^q \) ;
  • le rationnel \( r = \frac{p}{q} \), qui d'une certaine manière permet de numéroter C

Soit \( \xi \) la fonction qui à \( t \) associe \( r \). On peut en déterminer une expression, comme suit :

 \[ t^p = (1 - t)^q \] \[ p \ln(t) = q \ln(1 - t) \] \[ \frac{p}{q} = \frac{\ln(1 - t)}{\ln(t)} \]

On a donc :

\[ \xi: [0, 1[ \rightarrow \mathbb{R} \] \[ t \mapsto \xi(t) = \frac{\ln(1-t)}{\ln(t)} \]

Quelques propriétés de \( \xi \) :

\[ \xi(r) \xi(1-r) = 1 \] \[ \xi(0) = 0 \] \[ \xi(1^-) = +\infty \] \[ \xi'(0) = 0 \]

Quelques valeurs :

\[ \begin{array}{|l|l|} \hline t & r = \xi(t) \\ \hline 0.381 \dots = 2 - \phi = \frac{3 - \sqrt{5}}{2} & \frac {1}{2} \\ 0.500 \dots = \frac{1}{2} & 1 \\ 0.569 \dots = \frac{1}{\rho^2} & \frac{3}{2} \\ 0.618 \dots = \frac{1}{\phi} & 2 \\ 0.682 \dots = \frac{1}{\psi} & 3 \\ 0.724 \dots & 4 \\ 0.754 \dots = \frac{1}{\rho} & 5 \\ 0.778 \dots & 6 \\ \hline \end{array} \]

où \( \phi \) est le nombre d'or, \( \psi \) le "supergolden ratio" et \( \rho \) le nombre plastique.

\( \xi ^{-1} \), la réciproque de \( \xi \), doit être également très intéressante, voire encore plus intéressante.

Mais je ne trouve pas de forme close pour \( \xi ^{-1} \).

(Ce serait naïf, je pense, de croire pouvoir en trouver une facilement : cette fonction doit être le rêve de tout algébriste !)

Nombre de partitions de \( n \) dont les parts sont de taille \( p \) ou \( q \), vu comme multiplicité d'un certain point.

En regardant attentivement l'illustration "logarithmique", on constate que, pour un "collier de perles" C donné,

Dire que sur chaque niveau il peut y avoir zéro courbe passant par là, ou bien une seule, ou bien plusieurs (auquel cas on voit ce niveau parce qu'on y voit une intersection) revient simplement à associer à C une suite d'entiers positifs ou nuls, le nombre de courbes la famille passant par ce niveau.

Exemple

Considérons le collier de perles C défini, au choix, par :

Voici ce collier de perles C, illustré (en rouge) :

De haut en bas, les niveaux \( k = 0, 1, 2, \dots \) sont situés à altitude (= ordonnée) \( k \frac{\ln(t)}{q} = k \frac{\ln(1-t)}{p} \) valeur décroissante dans les négatifs quand \( k \) augmente.

La distance qui sépare 2 niveaux consécutifs, ce que j'appelerai la longueur d'onde de C, est \( \lambda = -\frac{\ln(t)}{q} = \frac{0.569840 \dots}{2} = 0.2811995\dots \)

Par le point de niveau 0, ne passe qu'une seule courbe de la famille (en l'occurrence la courbe \( t^0 (1-t)^0 \)). Si l'on nomme \( u_k \) le nombre de courbes de la famille passant par le point de niveau \( k \), alors \( u_0 = 1 \). Par le point de niveau 1, ne passe aucune courbe de la famille ; par conséquent, \( u_1 = 0 \) ; et ainsi de suite, il n'y a qu'à lire le dessin ci-contre.

\[ \begin{array}{lll} u_{0} & = & 1 \\ u_{1} & = & 0 \\ u_{2} & = & 1 \\ u_{3} & = & 1 \\ u_{4} & = & 1 \\ u_{5} & = & 1 \\ u_{6} & = & 2 \\ u_{7} & = & 1 \\ u_{8} & = & 2 \\ u_{9} & = & 2 \\ u_{10} & = & 2 \\ u_{11} & = & 2 \\ u_{12} & = & 3 \\ u_{13} & = & 2 \\ u_{14} & = & 3 \\ u_{15} & = & 3 \\ u_{16} & = & 3 \\ u_{17} & = & 3 \\ \end{array} \]

Quelle est donc cette suite ?

\[ 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, \dots \]

Réponse (d'OEIS) : A103221: Number of partitions of n into parts 2 and 3. Et la formule qui va avec : la série/fonction génératrice de cette suite est :

\[ g.f. : \frac{1}{(1-x^2)(1-x^3)} \]

Vérifions un minimum, pour \( k = 17 \) :

\[ \begin{array}{lllllll} 17 & = & 2 + 3 + 3 + 3 + 3 + 3 & = & 1 \times 2 + 5 \times 3 & \rightarrow & (1, 5) \\ 17 & = & 2 + 2 + 2 + 2 + 3 + 3 + 3 & = & 4 \times 2 + 3 \times 3 & \rightarrow & (4, 3) \\ 17 & = & 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 & = & 7 \times 2 + 1 \times 3 & \rightarrow & (7, 1) \\ \end{array} \]

Pas d'autre façon d'obtenir 17. \(u_{17} = 3\) façons d'obtenir 17... OK, ça semble exact.

Niveau de C \( (p = 3, q = 2) \) par lequel passe la courbe \( t^a (1-t)^b \) en fonction de \( a \) et de \( b \)

Exactement 3 cases contiennent 17 ; ça concorde !

\[ \begin{array}{lll} (1, 5) & \rightarrow & t (1 - t)^5 \\ (4, 3) & \rightarrow & t^4 (1 - t)^3 \\ (7, 1) & \rightarrow & t^7 (1 - t) \\ \end{array} \]
\(b\), puissance de \( (1 - t) \) \( \uparrow \)
5 15 17 19 21 23 25 27 29
4 12 14 16 18 20 22 24 26
3 9 11 13 15 17 19 21 23
2 6 8 10 12 14 16 18 20
1 3 5 7 9 11 13 15 17
0 0 2 4 6 8 10 12 14
0 1 2 3 4 5 6 7 \( \rightarrow \) \( a \), puissance de \( t \)

Ces observations semblent se généraliser à tous les couples d'entiers positifs \( (p, q) \) avec \( p \) et \( q \) premiers entre eux. Autrement dit, \( u_k \) est le nombre de partitions de \( k \) en parts de tailles \( p \) ou \( q \), et la suite \( (u_k)_{k \in \mathbb{N}} \) a pour série génératrice :

\[ g.f. : \frac{1}{(1-x^p)(1-x^q)} \]

Longueur d'onde \( \lambda \) en fonction de \( t \)

Rappel,

\[ \lambda = -\frac{\ln(t)}{q} \]

Donc \( \lambda \) est fonction de \( t \), on peut le noter \( \lambda = \Lambda(t) \), avec :

\[ \Lambda(t) = -\frac{\ln(t)}{\mbox{dénominateur}(\xi(t))} \]

Représentons sur un diagramme en bâtons cette fonction \( \Lambda \) ; cela implique de devoir compléter la définition de \( \Lambda \), en attribuant une valeur aux images des \(t \) tels que \( \xi(t) \) est irrationnel ; nous choisissons : \( 0 \). Cela donne alors :

Noter au passage que :

\[ \Lambda(1-t) = \Lambda(t) \]

(démonstration assez facile).

La ressemblance entre ce diagramme en bâtons et le verger d'Euclide lorqu'il est vu en perspective, ou bien encore avec la fonction de Thomae, est frappante !

Courbe paramétrée par \(t \)

La formule vue plus haut,

\[ \frac{p}{q} = \frac{\ln(1-t)}{\ln(t)} \]

déclenche une interprétation géométrique : \( \frac{p}{q} \) est la pente de la droite qui relie les points de coordonnées \( (0, 0) \) et \( (q, p) \). Mais alors, pourquoi ne pas voir aussi dans \( \frac{\ln(1-t)}{\ln(t)} \) la pente de la droite qui relie les points de coordonnées \( (0, 0) \) et \( (\ln(t), \ln(1-t)) \) ? Ajoutons un signe moins pour rendre les coordonnées en question positives : soit donc C la courbe paramétrée :

\[ \begin{array}{rcl} x & = & -\ln(t) \\ y & = & -\ln(1-t) \\ \end{array} \]

L'élimination de \(t\) dans le système d'équations ci-dessus fournit des équations cartésiennes de C :

\[ \begin{array}{rcl} e^{-x} + e^{-y} & = & 1 \\ y & = & -\ln(1-e^{-x}) \\ \end{array} \]

On a alors une interprétation de ce qu'est \( \lambda \). C'est la plus grande unité de longueur que l'on peut choisir et telle que \( x \) et \( y \) soient commensurables (= x est un nombre entier de fois cette unité de longueur, y aussi, et ces deux nombres entiers sont premiers entre eux). Exemple pour \( \frac{p}{q} = \frac{3}{2} \) :

\[ \implies x = 2 \lambda, y = 3 \lambda \] \[ \mbox{PGCD}(2, 3) = 1 \]

et dans le cas général,

\[ x = q \lambda, y = p \lambda \] \[ \mbox{PGCD}(p, q) = 1 \]

LR, 02/01/2021.