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 ?
$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 ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
A priori non, bien qu'il y ait un lien avec l'équation de la chaleur.
En effet, le temps n'est pas exponentiel en $N$ malgré les apparences.
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,
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$.
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.
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 ?
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 ?
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$.