Navegar

Como dividir um bolo entre 'n' pessoas de forma justa?

 

A hora de cortar um bolo ou uma pizza pode ser tensa, em especial se você está dividindo essas delícias com seus irmãos ou amigos. A técnica tradicional é o famoso “você corta, eu escolho”, que permite neutralizar qualquer maldade de quem corta ou a dor de quem poderia ficar com o menor pedaço. Mas por que não usar a matemática para ajudar nesse processo? Afinal, ninguém quer ficar com menos bolo que o outro. Talvez somente em casos de dieta.

Dois cientistas da computação, Hariz Aziz e Simon Mackenzie, pesquisadores da Universidade de Nova Gales do Sul, Austrália, desenvolveram recentemente um algoritmo em 2016 que pode ajudar a entender os meandros de uma divisão justa. De forma resumida, a dupla descreveu um meio de dividir um bolo entre n pessoas, sendo “n” uma variável que pode representar qualquer número.

Pode parecer estranho, mas esse é um problema importante porque serve de analogia para inúmeros problemas não tão banais de alocação de recursos, tais como divisão fundiária, penhora de bens, dados de rede, entre outros. Muitos até acreditavam que criar tal fórmula seria provavelmente impossível.

Um dos últimos avanços nesse problema foi feito na década de 60, quando um algoritmo foi desenvolvido para a divisão entre três agentes. Décadas depois, outros matemáticos conseguiram adicionar mais um agente à fórmula. Contudo o algoritmo era irrestrito em sua formulação, o que fazia com que uma divisão tivesse desde 100 até um bilhão de passos.

O trabalho de Aziz e Mackenzie na área iniciou onde seus anteriores pararam, criando uma divisão entre quatro agentes em 2015. A diferença é que o protocolo deles levava apenas entre 3 e 203 cortes. Ainda bastante, mas bem mais restrita que a versão anterior. O seu artigo mais recente, porém, foi mais além, delimitando um algoritmo que serve para qualquer número de pessoas.

O problema é que, por ser extremamente complexo, dividir um bolo entre N pessoas usando esse método pode requerer n^n^n^n^n^n passos. Isso significa que se 5 pessoas quiserem dividir um bolo de forma justa, o número máximo de cortes será 5 elevado a 5, elevado a 5, elevado a 5, elevado a 5 elevado a 5. Um número astronômico, em resumo.  Sendo assim, este é um algoritmo pouco prático no dia a dia, mas que abrirá portas para novas descobertas na área.

Uma divertida introdução ao problema da divisão de bolos pode ser vista nesse vídeo da professora de matemática Eugenia Cheng, da Universidade de Sheffield, na Inglaterra

Para saber mais
for Any Number of Agents
for Four Agents