Découpage équitable de la pizza avec des olives

mais non papa, tu comprends jamais rien ! ok, c’est bien si on a autant de pizza tous les deux… mais on veut aussi avoir autant d’olives tous les deux ! et autant de morceaux d’ananas !”. Ouais, bon, on n’est pas couché là !

On va quand même essayer de la couper cette pizza (avant qu’elle ne refroidisse) !

  • Partage de la pizza et des olives

Commençons par supposer que seules les olives soient importantes. La première idée que j’aurais serait de faire une régression médiane, qui va découper le nuage de points (les olives) en deux…

Sous R (oui, j’ai installé R sur la table de la cuisine), c’est assez facile à mettre en œuvre… Pour des raisons de symétrie, je vais faire les régressions de l’abscisse sur l’ordonnée, et réciproquement…

> library(quantreg)
> lq=rq(y ~ x, tau = 0.5, data=D)
> abline(lq,lwd=5,col="red")
> sum(y0>predict(lq))
[1] 22
> sum(y0<=predict(lq))
[1] 22
>
> lq=rq(x ~ y, tau = 0.5, data=D)
> abline(b=1/lq$coefficients[2],
+ a=-lq$coefficients[1]/lq$coefficients[2],lwd=5,col="red")
> sum(x0>predict(lq))
[1] 22
> sum(x0<=predict(lq))
[1] 22

Le soucis est que si la régression n’est pas contrainte, il y a une répartition 50-50 des olives, mais les parts ne sont pas équitables,

> library(quantreg)
> lq=rq(y ~ 0+x, tau = 0.5, data=D)
> abline(lq,lwd=5,col="red")
> sum(y0>predict(lq))
[1] 20
> sum(y0<=predict(lq))
[1] 24
>
> lq=rq(x ~ 0+y, tau = 0.5, data=D)
> abline(b=1/lq$coefficients,a=0,lwd=5,col="red")
> sum(x0>predict(lq))
[1] 25
> sum(x0<=predict(lq))
[1] 19

et si je supprime la constante les parts sont équitables (la régression passe par le centre la pizza), mais le partage des olives n’est pas équilibré…

On peut aussi calculer pour tous les angles possibles ce que donnerait des partages de la pizza (qui passent par le centre). C’est ce que représente la courbe rouge ci-dessous: l’extérieur du disque le ratio des olives dépasse 1, à l’intérieur il est inférieur à 1. Les découpages optimaux correspondent au cas où le ratio vaut précisément 1… ce qui est possible si on coupe comme indiqué ci-dessous, à droite,

Je pense qu’on doit pouvoir montrer qu’il est toujours possible de couper la pizza en deux, de manière équitable, avec autant d’olives de part et d’autre (s’il y a un nombre pair d’olives).
oui mais papa… tu nous avais dit que tu savais pas couper en passant par le centre…”. Ah oui, c’est vrai ! Damned…. bon, utilisons la méthode décrite dans le billet précédant (ici), a priori ça doit être possible de trouver un sommet pour lequel le partage des olives est équitable. En fait, on pourrait aussi tirer au hasard des points dans la pizza, et compter les olives en faisant la répartition de manière alternée,

> sommet=matrix(NA,500000,3)
> for(s in 1:nrow(sommet)){
+ a0=runif(10)*2-1; b0=runif(10)*2-1
+ if(a0^2+b0^2)<=1){
+ slope1=(y0-b0)/(x0-a0)
+ I1=((slope1>0)&(slope1<1))|((slope1<(-1)))
+ sommet[s,]=c(sum(I1),a0,b0)
}}

On a alors en rouge l’ensemble des points à partir desquels on peut faire des découpages en 8, avec des pointes à 45° (en commençant par couper horizontalement)

Et ça semble marcher !

oui mais papa… tu as oublié les ananas…”.

  • Partage de la pizza et des olives et des ananas

En utilisant la méthode précédente, rien de plus simple ! En plus de compter la répartition des olives, on va compter la répartition des ananas…! Sur le dessin à gauche on a les olives et les ananas. A droite, les points rouges correspondent à des répartitions équitables des olives, et les bleus des répartitions équitables des ananas… Reste à trouver des points à la fois rouges et bleus,

ce sont finalement les points violets ci-dessous ! On a alors une méthode pour couper la pizza en deux parts de même taille, avec autant d’olives et autant d’ananas de part et d’autres !

Découpage équitable de la pizza

Bon, maintenant que l’année scolaire est passée, je vais arrêter un peu les billets sérieux pour revenir pour mes mésaventures à la maison. Par exemple, hier soir, c’était pizza. Et mes enfants aiment partager à deux une pizza (sur laquelle on a rajouté plein de choses qu’ils aiment, genre des olives, ou des morceaux d’ananas). Mais il faut un découpage équitable. Les enfants ne veulent pas un partage juste, mais un partage moitié-moitié.

Classiquement, je coupe la pizza en deux (cf figure ci-contre, avec un côté en bleu pour mon fils, et un en rouge pour ma fille, histoire de simplifier un peu). Mais comme me l’a fait noté mon fils, si mon couteau ne passe pas par le centre de la pizza (on va dire le centre du cercle parce qu’il va falloir faire des maths… pour les recettes de cuisine, il faut changer de site, genre ici).
Donc pour faire simple, la proba d’avoir deux parts rigoureusement égale est très très faible… car il faut couper suivant une droite qui passe exactement au centre (sinon, il y a quelqu’un qui est défavorisé, alors on tire au sort… a prioric’est juste juste, mais ex-post, il y en a toujours un ou une qui trouve le système injuste et qui veut qu’on retire au hasard…)
Fort heureusement, il existe une technique simple, et rigoureusement juste, permettant d’avoir des parts équitables…
L’idée est la suivante: on commence par couper horizontalement, n’importe où. Ensuite, on coupe verticalement (à angle droit, en prenant son équerre) de manière à récupérer 4 parts. Au point d’intersection,  on coupe à 45° direction nord-est, et 45° direction nord-ouest…. Une fois le découpage effectué, on réparti les parts, à tour de rôle, les parts bleues pour mon fils, et celles en rouges pour ma fille,

Car le truc génial est que le découpage – en plus d’être fort élégant – est parfaitement équitable ! Comme les enfants sont toujours sceptiques, il faut bien sûr leur prouver que oui, ils en auront exactement pareil. Pour ça on reprend le couteau…

Si on recoupe les parts suivant les traits-ci-dessus, chaque part bleue pourra être superposée à une part rouge (la preuve mathématique repose sur des simple notions de symétrie…). Génial non ? On a même le théorème du mardi soir, à savoir que “si on coupe une pizza en 8 parts, avec des pointes à 45° partir d’un point choisi arbitrairement dans la pizza, alors la somme alternée des parts sera égale” (cf ici). En 1967, Upton a posé ce problème,

Larry Carter et Stan Wagon affirmaient que ce résultat resterait vrai si on coupait en 12 ou 16 parts (avec des angles égaux pour les pointes), mais pas pour 6, 10, 14 ou 18 par exemple. Le blog du chou romanesco (ici et ) prétend que c’est vrai pour les découpages en un nombres pairs. En fait, Rick Mabry et Paul Deiermann ont un théorème assez général ( pour la version complète) et qui généralise aussi en dimension 3 (pour une calzone en quelque sorte). Mais je sens que ça n’intéresse plus trop les enfants, qui ont déjà fini la pizza….

Les plus curieux peuvent aussi consulter le court article ci-dessous,