Choux romanesco, Vache qui rit et intégrales curvilignes

Papier toilette

Les vacances d'hiver sont enfin là, l'occasion pour ce blog de revêtir ses habits de Noël. Il me fallait un sujet de saison, un sujet familial qui plaise à tous. C'est donc tout naturellement que je vais aujourd'hui parler de l'épineux problème du papier toilette. Ce n'est pas moi qui ai commencé, mais Donald Knuth (l'inventeur du TEX) dans son papier "The toilet paper problem" publié en 1984 dans l'American Mathematical Monthly ! Là, c'est vraiment Noël avant Noël !

Je sais pas où mettre mon 42, alors je le mets làLe PQ mathématique Renova, en vente dans tous les bons magasins. Le cadeau de Noël idéal.

Le Toilet Paper Problem
Vivons l'espace de quelques instants la vie d'un responsable petits coins d'une grande société. Pour éviter les manques, chaque cabinet possède deux rouleaux de papier toilette. Il existe cependant deux types d'usagers de toilettes : les grands-choisisseurs et les petits-choisisseurs.
Quand ils ont le choix, les grands-choisisseurs utilisent toujours le rouleau le plus plein, alors que les petits-choisisseurs se serviront de celui qui est le plus entamé. Quand les deux rouleaux sont de même taille, le plus proche sera utilisé. C'est quand les deux rouleaux sont vides qu'il faut commencer à s'inquiéter. A quel point faut-il redouter ce problème ? Quand un rouleau arrive à son terme, qu'en est-il de l'autre ? C'est ça, le Toilet Paper Problem !

Supposons qu'un utilisateur ait une probabilité p d'être un grand-choisisseur et une probabilité q=1-p d'être un petit-choisisseur. Au matin, les deux rouleaux sont de longueur n, et chaque usager ne se servira que d'une seule feuille (ou du moins, d'une seule unité de PQ) lors de son passage. On s'intéresse à Mn(p), le nombre moyen de portions de papier toilette restant quand l'un des deux rouleaux arrive à son terme.

On peut procéder à quelques calculs simples :

Mn(1) = 1. Si chaque usager est un grand-choisisseur, les deux rouleaux seront choisis alternativement. Après 2n-1 passages, il ne restera plus qu'une seule feuille.
Mn(0) = n. Si tous les utilisateurs sont des petits-choisisseurs, un seul rouleau sera utilisé à partir du moment où il sera entamé. Quand il sera vidé, l'autre sera toujours intact.
M1(p) = 1. Quelle que soit la personne qui rentre, si chaque rouleau n'a qu'une feuille, il n'en restera plus qu'une quand il resortira.

M2(p) = 2-p. Pour s'en convaincre, on peut se faire un petit arbre de probabilités

M2pM2(p) = 1×p + 2×(1-p) = 2-p

M3(p) = 3-2p-p2+p3 : de la même façon, on peut se faire un arbre de probabilités (bien qu'à ce niveau là, il faudrait plutôt envisager un graphe).

M3p


M3(p) = 1×p2 + 2×p.q + 1×p2.q + 2×p.q2 + 3×q2 
= 3-2p-p2+p3

Récursivité
Pour généraliser ces calculs, introduisons la notation Mm,n(p), le nombre moyen de feuilles restant quand l'un des rouleaux est vidé si l'on part d'un rouleau à m feuilles et d'un autre à n feuilles. On supposera n>m.

Par définition, on a :

Mn,n(p) = Mn(p)
M0,n(p) = n

Quand les deux rouleaux sont égaux (et non vides), on se sert sur le premier rouleau, ce qui donne :

Mn,n(p) = Mn-1,n(p) si n>0

Sinon, le premier rouleau est plus petit que le deuxième. Il y a alors une probabilité p de se servir sur le deuxième et une probabilité q sur le premier :

Mm,n(p) = p.Mm,n-1(p) + q.Mm-1,n(p) si n>0

On peut ainsi calculer que M4(p) = 4-3p-2p2+p3+4p4-2p5.

Cette formulation récursive permet de visualiser l'ensemble des chemins possibles par le graphe suivant:

graphe_PQSi un chemin commence sur la diagonale en (n;n), il part en (n-1;n). Il a alors deux choix : aller en (n-1;n-1) ou en (n-2;n).

La valeur de Mm,n(k) peut être alors vue comme la somme, pour k∈[1..n], de k fois la somme du poids des chemins de (m;n) à (0;k), le poids d'un chemin étant le produit de ses arcs.

Notons ck le nombre de chemins allant de (n;n) à (n-k;n-k) qui ne passent pas par la diagonale. Un tel chemin a pour poids pk.qk-1
On note également dn,k le nombre de chemins allant de (n;n) à (1;k) sans passer par la diagonale. Ces chemins ont pour poids pn-k.qn-1.
Du coup, si un chemin part de (n;n), soit il repasse par la diagonale en (n-k;n-k), soit il n'y repasse pas. On traduit ceci par :

Mnp(où la deuxième somme vaut 1 si n=1)

On peut reconnaître dans les ck les nombres de Catalan, et dans les dn,k les nombres qui apparaissent dans le problème du scrutin de Bertrand ("ballot problem").

Catalan

Finalement ?
En considérant la série génératrice de Mn(p) devenue calculable grâce à l'apparition de termes biens connus, il est possible d'observer le comportement de Mn(p) pour n grand. Le cas p=q est une simple marche aléatoire 1D. (Je vous renvoie à l'article de Knuth pour les détails).

ResultatsFormule valable pour n aussi grand que p est proche de q.

Supposons qu'il y ait un grand nombre (n) de feuilles dans les deux rouleaux du départ. S'il y a deux fois plus de grands-choisisseurs que de petits-choisisseurs (p=2/3), il restera environ 2 feuilles quand l'un des rouleaux arrivera à son terme. Dans le cas contraire (p=1/3), il en restera environ n/2+1.

Finalement, les résultats sont conformes à l'intuition : si les grand-choisisseurs sont majoritaires (p>q), il ne restera que très peu de feuilles disponibles quand l'un des rouleaux sera à sec. Dans le cas contraire, le papier toilette restant sera proportionnel à la taille des rouleaux !

courbePQCourbe du nombre moyen de feuilles de papier toilette restant dans le cas critique où un rouleau est terminé en fonction de la probabilité p de tomber sur un grand choisisseur. (Cas n=16)


Sources : 
The toilet paper problem, par Donald Knuth

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : ,

Commentaires sur Papier toilette

    Bonne Fêtes à tous

    Au encore pour les chimistes : Bore - Oxygène - Azote - Néon - Fer - Tellure - Soufre - Astate - Oxygène - Uranium - Soufre !

    C'est intéressant de parler le jour de Noël de papier toilettes, on saura quoi t'offrir l'année prochaine ! Mais le contenu de l'article est loin d'être de la merde.

    Posté par RuBisCO, 24 décembre 2012 à 17:06 | | Répondre
  • Zut, il manque un atome de soufre, veuillez m'excuser !

    Posté par RuBisCO, 24 décembre 2012 à 17:09 | | Répondre
  • Q = 1 - P

    N'hésitez à compléter vos connaissances sur le sujet avec cet article : http://eljjdx.canalblog.com/archives/2011/11/20/22728545.html !

    Posté par véhache, 25 décembre 2012 à 13:56 | | Répondre
  • Trés instructif

    Me voilà, enfin documentée sur ce grave sujet, je finirai l'année satisfaite d'avoir obtenu la solution du problème, Mille mercis, bonne fin d'année

    Posté par Anne-Marie, 28 décembre 2012 à 16:37 | | Répondre
  • Et sociologiquement ?

    Ca mériterait un approfondissement sociologique de la question, grâce à un sondage auprès des dames pipi du monde entier: quelle est la valeur de p ? Comment varie p dans les pays du monde et en fonction du niveau socio-économique ? La crise a-t-elle un impact sur p ? Une étude expérimentale semble indispensable.

    Posté par J..., 31 décembre 2012 à 15:10 | | Répondre
  • bonjour,
    j’ai souvent rencontré des distributeurs de PQ asymétrique.
    J’utilise ce terme non parce que les deux rouleaux tourneraient dans le même sens, (bien qu’ils puissent tourner dans le même sens) mais parce qu’on peut mettre un grand rouleau et un petit mais pas deux grands.. Les deux rouleaux ont une épaisseur et un petit rayon identique.
    image : http://s399018734.siteweb-initial.fr/s/cc_images/cache_2412705771.jpg?t=1330894237
    J’ai souvent pensé que c’était pour inciter psychologiquement les utilisateurs à consommer plus l’un que l’autre, en changeant les probabilités p et q indiquées dans votre article.
    Finalement, j’ai supposé que l’intérêt est logistique et économique : ça permet aux agents de ménage de changer les grands rouleaux dès qu’ils sont plus petits que le diamètre du petit (charger un rouleau plein et récupérer une fin de rouleau). Ainsi lorsque l’agent passe ensuite à un distributeur dont le petit rouleau est vide, il peut prendre la fin de rouleau pour la mettre à la place du rouleau vide.
    Intérêt : organiser la gestion des fins de rouleaux pour ne pas gaspiller (en évitant bien sûr de risquer la pénurie).
    Mais selon votre calcul, le petit rouleau sera terminé systématique plus rapidement si p est proche de q (rythme plus rapide et capacité inférieure). Donc il n’y aura jamais de pénurie mais en permanence le petit rouleau à changer (donc trop souvent pour le nombre de fin de gros rouleaux qu’on réccupère).
    Voici ma participation à ce sujet intéressant.

    Benoît

    Posté par Benoît, 06 novembre 2013 à 23:43 | | Répondre
Nouveau commentaire
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.