"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 symmé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 !