Des pirates et du rhum !

Un problème.

$N$ pirates veulent se partager équitablement un tonneau de $N$ litres de rhum. Ils se placent en ligne, du plus gradé (le capitaine) au moins gradé (un mousse). Initialement, le capitaine a le tonneau entier et les autres rien. S'ensuit une succession d'étapes du type suivant : deux pirates côte à côte mettent en commun leur rhum et se le partagent équitablement. Ils s'arrêtent lorsque l'écart entre le capitaine et le dernier mousse est inférieur à $1$ litre. On supposera qu'aucun pirate ne boit son rhum avant la fin du partage.

Quel est le nombre minimal d'étapes ?

Quel est le nombre d'étapes si les échanges se font au hasard ?

Réponses

  • Faut-il tenir compte de l'évaporation ?
  • Si on fait au hasard, expérimentalement ça a l'air de se comporter comme $N^3/C$ où $C$ est compris entre $3$ et $4$.
  • jacquot a écrit:
    Faut-il tenir compte de l'évaporation ?

    A priori non, bien qu'il y ait un lien avec l'équation de la chaleur.
    JLT a écrit:
    Si on fait au hasard, expérimentalement ça a l'air de se comporter comme $N^3/C$ où $C$ est compris entre 3 et 4.

    En effet, le temps n'est pas exponentiel en $N$ malgré les apparences.
  • Et expérimentalement toujours, si on emploie l'algorithme consistant à effectuer l'échange entre les deux voisins les moins gradés qui ont le plus grand écart, cela prend un temps $N^3/K$ où $K/C$ est environ égal à $5/2$.
  • @Siméon : tu sais prouver ce comportement dans le cas aléatoire ?
  • Je n'ai rien écrit de rigoureux mais j'ai quelques idées. Le problème ne te plaît pas ?
  • @Siméon : si, mais il ne me distrait pas assez de mes thématiques de recherche pour que je m'y plonge :-).
  • En tout cas, si on appelle $f(t,x)$ l'espérance de la quantité de vin du pirate $x$ à l'instant $t$, elle vérifie $f(0,x)=N\delta_{x,1}$ et l'équation de la chaleur discrète $f(t+1,x)-f(t,x)=\frac{1}{2N}\displaystyle \sum_{y\sim x}(f(t,y)-f(t,x))$ où la somme porte sur les voisins de $x$. J'imagine que cette EDP discrète a déjà été étudiée quelque part.
  • Bonjour,

    Pour la modélisation, avec tes notations, je ne trouve pas $\displaystyle {1 \over 2N}$ mais $\displaystyle {1 \over 2}$ devant la somme sur les voisins. En effet, entre les instants $\displaystyle t, t+1$ la quantité de rhum est divisée par deux.

    Puis en fait, je trouve :
    $\displaystyle f(t+1,x) = { f(t,x+1)+f(t,x) \over 2 } P_+(x, t+1) + { f(t,x-1)+f(t,x) \over 2 } P_-(x, t+1) + f(t,x) P_=(x, t+1)$

    où $\displaystyle P_+(x, t+1), P_-(x, t+1), P_=(x, t+1)$ sont respectivement les probabilités, au temps $\displaystyle t+1$, pour le pirate $\displaystyle x$, d'échanger avec $\displaystyle x+1, x-1$ ou de ne pas échanger.

    Avant de résoudre cette équation dans le cas d'échanges aléatoires, ce qui doit pouvoir se faire avec $\displaystyle f(x,t) = \sum_k C(k) e^{ikx}e^{-\alpha(k) t}$, la relation de dispersion étant $\displaystyle k \mapsto \alpha(k)$, je préfère la soumettre à votre vérification.

    Merci d'avance,
  • En fait dans mon équation il faut remplacer $\frac{1}{2N}$ par $\frac{1}{2(N-1)}$ (ce qui ne change pas grand-chose asymptotiquement). En effet, si $x\ne N$ alors $P_+(x,t+1)=1/(N-1)$, etc.

    Si $X(t)$ est le vecteur des $N$ tonneaux de rhum, on a $X(t)=AX(0)$ où $A$ est une matrice tridiagonale. On constate expérimentalement que le plus petit $m$ tel que $|X(t)_N-X(t)_1|<1$ vérifie $m\sim N^3/C$ où $C$ est proche de $7/2$.
  • Ah oui mais vous trichez un peu là ! On voudrait plutôt le comportement de $T_N$ où $T_N$ est le premier instant (aléatoire) où la contrainte est réalisée :-).
  • Je sais bien qu'on triche mais je ne sais pas résoudre le problème. Même en trichant je ne sais pas calculer la constante $C$.

    P.S. Je conjecture que $\displaystyle \sum_{k=1}^\infty \exp\left(-\frac{k^2\pi^2}{8C}\right)=1$, ce qui donnerait $C\simeq 3.5342917$ et serait en accord avec les essais numériques.
  • Bonjour @JLT et @Siméon,

    Avant de me lancer dans les calculs, je désire être sûr de bien comprendre l'énoncé.

    @JLT, dans le cas des échanges aléatoires, tu considères qu'un pirate $x$ partage son rhum avec un autre pirate $y$ choisi au hasard parmi les autres $N-1$ pirates. On pourrait considérer, de plus, qu'il n'est pas forcé de partager son rhum.

    Moi, je comprends autrement : dans le cas des échanges aléatoires, je considère que le pirate $x$ partage son rhum avec ces premiers voisins $x-1, x+1$ (ou son seul premier voisin s'il s'agit du capitaine ou du mousse) ou bien ne partage par son rhum.

    @Siméon, quelle est la situation que tu désires voir résolue ?
  • Les pirates sont numérotés de 1 à N. A chaque étape, on choisit au hasard de maniere uniforme un entier x entre 1 et N-1. Les pirates x et x+1 se partagent équitablement leur rhum.
  • Bonjour,

    Le cas continu, où l'on suppose qu'il y a un nombre infini de pirates, mène à une équation de la chaleur, dont on peut résoudre les équations différentielles à l'aide de la fonction erreur ; le capitaine et le mousse ayant chacun leur propre équation du premier ordre avec second membre une fonction erreur. Même dans ce cas continu, la condition d'arrêt est inextricable (en tout cas pour moi) et on se ramène à une résolution numérique. Autant directement modéliser numériquement le problème...

    Voici la mise en équation dans le cas discret (et pour les échanges au hasard).

    Comme proposé par @JLT, les pirates sont numérotés de $1$ à $N$. Le capitaine a le rang $1$, le mousse le rang $N$. A chaque étape, on choisit au hasard de manière uniforme un entier $x$ entre $1$ et $N-1$. Les pirates $x$ et $x+1$ se partagent équitablement leur rhum.

    Conditions initiales :
    Les conditions intiales s'écrivent : $$\displaystyle f(x,0) = N \delta_{x,N}, x \in \{1, 2, \cdots, N\}$$
    où $\delta$ est le symbole de Kronecker.

    Condition d'arrêt :
    La quantité de rhum du pirate $x$ à l'instant $t$ est $f(x,t)$ et est mesurée en litres (ou plus justement l'espérance de la quantité), où $t$ varie de $0$ à $T$. Le temps d'arrêt $T$ est obtenu lorsque la différence entre les quantités de rhum du mousse et du pirate est inférieure ou égale à un litre :
    $$\displaystyle \mid f(1,T) - f(N,T) \mid \leq 1.$$

    Evolution des quantités de rhum :
    On établit facilement qu'entre les instants $t$ et $t+1$, la quantité de rhum varie lorsqu'un pirate partage sa quantité avec son premier voisin derrière lui $x-1$ ou devant lui $x+1$. De plus la loi uniforme impose que la probabilité d'être choisi est $\displaystyle {1 \over N-1}$ et alors :
    $$\displaystyle x \in \{2, \cdots, N-1\}, f(x, t+1) - f(x,t) = {1 \over N-1} {f(x-1,t) - f(x,t) \over 2} + {1 \over N-1} {f(x+1,t) - f(x,t) \over 2},$$

    ou encore :
    $$\displaystyle x \in \{2, \cdots, N-1\}, f(x, t+1) = {1 \over 2(N-1)} f(x-1,t) + {1 \over 2(N-1)} f(x+1,t) + (1-{1 \over N-1}) f(x,t).$$

    Pour $x=1$, le capitaine ne partage qu'avec son seul voisin en $x=2$ et :
    $$\displaystyle f(1, t+1) = {1 \over 2(N-1)} f(2,t) + (1-{1 \over 2(N-1)}) f(1,t).$$

    Une autre façon d'aboutir à cette équation est d'écrire que, si le capitaine est choisi, avec la probabilité $\displaystyle {1 \over N-1}$, il partage son rhum avec son voisin, et s'il n'est pas choisi, avec la probabilité $\displaystyle 1-{1 \over N-1}$ il conserve sa quantité de rhum :
    $$\displaystyle f(1, t+1) = {1 \over N-1} {f(2,t) + f(1,t) \over 2} + (1-{1 \over N-1}) f(1,t).$$

    Pour $x=N$, le mousse ne partage qu'avec son seul voisin en $x=N-1$ et :
    $$\displaystyle f(N, t+1) = {1 \over 2(N-1)} f(N-1,t) + (1-{1 \over 2(N-1)}) f(N,t).$$

    La mise en équation mène donc à un système matriciel d'ordre $N$. On pose : $$\displaystyle \alpha_N = {1 \over 2(N-1)}, \quad X_N(t) = \begin{pmatrix} f(1,t)\\f(2,t)\\ \cdots\\\cdots\\\cdots\\ f(N,t)\end{pmatrix}, \quad X_N(0) = \begin{pmatrix} N\\0\\ \cdots\\\cdots\\\cdots\\ 0\end{pmatrix}, \quad A_N = \begin{pmatrix} 1-\alpha_N&\alpha_N& 0 & \cdots \\ \alpha_N & 1-2\alpha_N &\alpha_N& 0 & \cdots \\ 0 & \alpha_N & 1-2\alpha_N &\alpha_N& 0 & \cdots \\ \cdots& \cdots&\cdots&\cdots&\cdots&\cdots \\ \cdots&\cdots&0&\alpha_N & 1-2\alpha_N &\alpha_N \\ \cdots&\cdots&\cdots&0&\alpha_N&1-\alpha_N\end{pmatrix},$$

    donc $\displaystyle 0 < \alpha_N \leq \frac{1}{2}$, et alors on obtient, par récurrence : $$\displaystyle X_N(t+1) = A_N X_N(t), \quad X_N(T) =A_N^T X_N(0).$$

    Suite de la méthode :
    Il faut montrer que $\displaystyle \det{A_N(T) \neq 0}$ et donc que $A_N$ est inversible. On note que $A_N$ est une matrice réelle symétrique dont tous les coefficients sont positifs car $\displaystyle 1-2 \alpha_N \geq 0$.
    Puis on détermine le polynôme caractéristique $\chi_N$ et le spectre de $A_N$, on note $\displaystyle \{a_N^i, V_N^i\}$ un élément propre : $\displaystyle A_N V_N^i = a_N^i V_N^i, i \in \{1, 2, \cdots, N \}$. La matrice de passage est $P_N$, la matrice diagonale est $\displaystyle D_N = diag(a_N^1, a_N^2, \cdots, a_N^N)$, avec $\displaystyle A_N = P_N \, D_N\, P_N^{-1}$.

    Finalement, on arrive à : $$\displaystyle X_N(T) = P_N \, diag((a_N^1)^T, (a_N^2)^T, \cdots, (a_N^N)^T)\, P_N^{-1}\begin{pmatrix} N\\0\\ \cdots\\\cdots\\\cdots\\ 0\end{pmatrix} = \begin{pmatrix} N \sum_{k=1}^{N} (P_N)_{1k} (a_N^k)^T (P_N^{-1})_{k1} \\ N \sum_{k=1}^{N} (P_N)_{2k} (a_N^k)^T (P_N^{-1})_{k1} \\ \cdots\\ \cdots \\ \cdots \\ N \sum_{k=1}^{N} (P_N)_{Nk} (a_N^k)^T (P_N^{-1})_{k1} \end{pmatrix} .$$

    La condition d'arrêt devient : $$\displaystyle \mid N \sum_{k=1}^{N} (a_N^k)^T [(P_N)_{1k}-(P_N)_{Nk}] (P_N^{-1})_{k1} \mid \leq 1.$$

    Et là je suis bloqué. Même en rangeant les valeurs propres par ordre croissant, même en sachat que $\displaystyle 1 \in Sp{(A_N)}$, je ne vois pas comment donner une expression utile à cette somme. Par ailleurs, on a : $\displaystyle \sum_{k=1}^{N} (P_N^{-1})_{ik}(P_N)_{kj} = \delta_{ij}$. La matrice $A_N$ est une matrice stockastique ou de Markov, mais où cela mène-t-il ?

    Une idée ? Un théorème utile pour avancer ?
  • Bonjour @Siméon,

    J'ai travaillé sur les matrices tridiagonales et les matrices bi-stochastiques pour déterminer si l'on peut simplifier la condition d'arrêt. Pour cela, il faut écrire les éléments propres de la matrice $A_N$, c'est-à-dire trouver les valeurs propres et les vecteurs propres.

    On rappelle la matrice en question :

    $\displaystyle \alpha_N = {1 \over 2(N-1)}, \quad A_N = \begin{pmatrix} 1-\alpha_N&\alpha_N& 0 & \cdots \\ \alpha_N & 1-2\alpha_N &\alpha_N& 0 & \cdots \\ 0 & \alpha_N & 1-2\alpha_N &\alpha_N& 0 & \cdots \\ \cdots& \cdots&\cdots&\cdots&\cdots&\cdots \\ \cdots&\cdots&0&\alpha_N & 1-2\alpha_N &\alpha_N \\ \cdots&\cdots&\cdots&0&\alpha_N&1-\alpha_N\end{pmatrix}$

    $A_N$ est une matrice de dimension $N$, réelle, symétrique, tridiagonale, bi-stochastique (la somme de toute ligne et de toute colonne est $1$) et dont les éléments des diagonales supérieure et inférieure sont non-nuls.

    On peut écrire un algorithme (fini) qui détermine les vecteurs propres et le polynôme caractéristique (dont les racines sont les valeurs propres).

    Voici comment.

    Mais la condition d'arrêt reste inextricable. Il semble donc que seule une application numérique permettra de calculer le temps d'arrêt en fonction de $N$.

    Les valeurs propres sont simples :
    Comme la matrice est symétrique réelle, toutes ces valeurs propres sont réelles.
    Soit $B_{N-1}$ la matrice extraite de $A_N$ en supprimant la première ligne et la dernière colonne.
    $\displaystyle B_{N-1} = \begin{pmatrix} \alpha_N & 1-2\alpha_N &\alpha_N& 0 & \cdots \\ 0 & \alpha_N & 1-2\alpha_N &\alpha_N& 0 \\ \cdots& \cdots&\cdots&\cdots&\cdots& \\ \cdots&\cdots&0&\alpha_N & 1-2\alpha_N \\ \cdots&\cdots&\cdots&0&\alpha_N\end{pmatrix}$

    On a $\displaystyle det(B_{N-1} - \lambda I_{N-1}) = \alpha_N^{N-1} \neq 0$ et donc $rg(A_N - \lambda I_N) \geq N-1$, et donc : $\displaystyle \forall \lambda \in \R, \quad dim(ker(A_N - \lambda I_N)) \leq 1$ et $\displaystyle dim(ker(A_N - \lambda I_N))=1$ si $\displaystyle \lambda \in Sp(A_N)$.

    Comme $A_N$ est diagonalisable, en notant $\displaystyle \lambda_1, \lambda_2, \cdots, \lambda_p$ les valeurs propres réelles deux-à-deux distinctes de $A_N$, on a $\displaystyle \oplus_{k=1}^{p} ker(A_N - \lambda I_N)$ avec $\displaystyle dim(ker(A_N - \lambda_k I_N))=1, \quad k=1, 2, \cdots, p$ ce qui impose $p=N$ et $A_N$ a $N$ valeurs propres réelles et simples.

    Polynôme caractéristique :
    On développe le déterminant $\displaystyle P_n(\lambda)=det(A_{N} - \lambda I_{N})$ selon la dernière colonne et il vient : $\displaystyle P_n(\lambda)=(A_N(n) - \lambda) P_{n-1} (\lambda) - \alpha^2 P_{n-2} (\lambda)$
    avec $\displaystyle A_N(j)$ est l'élément diagonal de la matrice $A_N$.

    Initialisation : $\displaystyle P_0(\lambda)=1, \quad P_1(\lambda)=A_N(1) - \lambda = 1- \alpha_N - \lambda$.
    On a bien : $\displaystyle P_2(\lambda)=(A_N(1) - \lambda)(A_N(2) - \lambda) - \alpha_N^2 =( 1- \alpha_N- \lambda)(1- 2\alpha_N - \lambda) - \alpha_N^2$.

    On peut donc calculer de proche en proche jusqu'à $P_N(\lambda)$. Et les valeurs propres sont les racines. Cependant, la relation de récurrence ne me permet pas d'exprimer simplement $P_N(\lambda)$.

    Vecteurs propres:
    Soit $\lambda \in Sp(A_N)$ et $x =(x_1, x_2, \cdots, x_N)^t$ son vecteur propre (et donc non-nul). Alors on a :
    $$\displaystyle (1-\alpha_N) x_1 + \alpha_N x_2 = \lambda x_1 \\ \alpha_N x_{k-1} + (1-2\alpha_N)x_k + \alpha_N x_{k+1} = \lambda x_k, \quad 2 \leq k \leq N-1 \\ \alpha_N x_{N-1} + (1-\alpha_N) x_N = \lambda x_N$$

    Si $x_N=0$, alors tous les $x_j$ sont nuls. On peut donc poser $x_N=1$ et les autres composantes vérifient un système triangulaire supérieur :
    $$\displaystyle \alpha_N x_{k-1} + (1-2\alpha_N - \lambda )x_k + \alpha_N x_{k+1} = 0, \quad 2 \leq k \leq N-1 \\ \alpha_N x_{N-2} + (1-2\alpha_N - \lambda)x_{N-1} = - \alpha_N \\ \alpha_N x_{N-1} = \lambda - (1-\alpha_N)$$
    dont la solution est donnée par :
    $$\displaystyle x_{N-1} = {\lambda - (1-\alpha_N) \over \alpha_N} \\ x_{k-1} = - { \alpha_N x_{k+1} + (1-2 \alpha_N - \lambda)x_k \over \alpha_N}, \quad k = 2, 3, \cdots, N-1$$

    qui permet de calculer toutes les composantes de tous les vecteurs propres (pour toute matrice $A_N$). Ces relations dépendent de la valeur propre.

    On vérifie facilement que $1$ est valeur propre avec le vecteur propre $(1, 1, \cdots, 1)$ pour toute matrice $A_N$.
Connectez-vous ou Inscrivez-vous pour répondre.