Os algoritmos do bolo-rei

Todos conhecemos a melhor maneira de repartir um bolo entre duas pessoas, sem que nenhuma se possa queixar: uma parte e outra escolhe. O problema complica-se quando há mais de dois parceiros. Por muito trivial que pareça, os matemáticos têm tratado este problema, obtendo algoritmos de repartição eficazes.



Texto de Nuno Crato
«Quem parte e reparte, e não fica com a melhor parte, ou é tolo ou não tem arte», diz um ditado popular. É verdade: se a pessoa a fazer a divisão for também a que fizer a escolha, nada garante que um dos parceiros não fique prejudicado. Por isso, e para evitar que alguém se possa queixar do resultado da partilha, o melhor é proceder em duas etapas: um dos parceiros divide o bolo e o outro escolhe a sua fatia.
Desta forma, é do interesse do primeiro fazer a divisão da forma mais equitativa possível, pois se assim não acontecer, terá a certeza de ficar com o pior bocado. É uma sábia conjugação de situações, pois os dois parceiros, afinal ambos movidos pelo egoísmo, colaboram de forma a que nenhum fique prejudicado.
A história é muito conhecida e aplicada em várias situações do dia-a-dia, e não só na divisão de guloseimas entre crianças. O problema complica-se, contudo, se o bolo tiver de ser dividido entre mais do que dois parceiros. Como é que se há-de fazer se forem três, por exemplo? Ou se forem muito mais? E se tivermos um bolo-rei a dividir entre 20 pessoas igualmente gulosas?
O problema não é simples e os matemáticos têm vindo a desenvolver algoritmos para partilhas equitativas. Esses algoritmos, isto é, esses procedimentos sistemáticos de busca de uma solução, podem ter aplicações em áreas muito diversas, desde a partilha de heranças e divisão de obrigações pecuniárias até às negociações de desarmamento ou ao estabelecimento de fronteiras entre países.
O algoritmo «um parte, outro escolhe» pode aplicar-se a mais do que dois parceiros. Se tivermos quatro pretendentes a um bolo-rei, por exemplo, o algoritmo desdobra-se em duas etapas. Começam-se por agrupar os pretendentes ao bolo em dois grupos, com dois elementos em cada grupo. Um dos grupos divide o bolo em duas partes e o outro escolhe a sua metade. Na segunda etapa, cada par de gulosos divide a sua metade de bolo-rei ao meio, seguindo de novo o processo de um partir e o outro escolher.
É fácil ver que este método pode funcionar igualmente para oito pessoas ou, em geral, para potências de dois. Mas já não é tão simples encontrar uma solução no caso de haver três pessoas. Pensando bem, consegue-se arranjar um método que funcione nesse caso. Quer o leitor dar uma sugestão?
Os matemáticos, contudo, não gostam de soluções que apenas funcionam para casos particulares, pelo que têm procurado algoritmos mais gerais. O ideal seria encontrar um método que funcionasse com qualquer número de pessoas. Um desses métodos, proposto pelos matemáticos polacos Stefan Banach (1892-1945) e Bronislaw Knaster (1893-1980), resolve o problema com qualquer número de parceiros. É o chamado algoritmo da faca deslizante. Este caso é mais fácil de perceber com um bolo sobre o comprido, como um bolo inglês.
Os diversos pretendentes às fatias do bolo reúnem-se à sua volta enquanto uma pessoa, possivelmente um deles, pouco importa, começa a deslizar a faca sobre o bolo, a partir de um dos lados. Vai-se progredindo com a faca até que um dos parceiros diga «Pára!». Nesse momento, pára-se a faca e corta-se uma fatia, que é entregue a quem falou. O parceiro em causa fica assim com uma parte que considera ser, pelo menos, uma fracção justa do bolo - se pensasse que a faca não tinha ainda chegado a essa fracção justa, não a teria reclamado. Os outros, por seu lado, vêem o bolo ser diminuído do que consideram ser inferior ou igual a uma fracção justa - se algum deles achasse que a faca tinha já ultrapassado o momento certo, deveria ter reclamado a fatia correspondente.
Depois de o primeiro parceiro ter recolhido a sua fatia, este afasta-se do jogo, enquanto a faca continua a deslizar, até que um dos restantes parceiros diga «Pára» e recolha a sua fatia. O processo repete-se até restarem apenas dois parceiros. Nessa altura, o primeiro a falar é o que fica com a fatia reclamada e o último fica com o restante. O interessante neste processo é que, mesmo admitindo a falibilidade de cada uma das pessoas, nenhuma delas pode reclamar que está a ser prejudicada. Se o está, é por sua culpa, pois não terá falado a tempo, ou terá falado cedo demais, sem a isso ninguém a ter obrigado.
Este método parece perfeito, mas deixa de fora alguns casos interessantes. Funciona para um bolo homogéneo, mas funcionará para um bolo com constituintes diversos e irregularmente distribuídos, como é o caso do bolo-rei? Será possível arranjar um algoritmo em que todos fiquem com igual quantidade de abóbora cristalizada, de pinhões, de passas e de massa? A resposta a esta questão foi dada por um teorema que o matemático polaco Hugo Steinhaus (1887-1972) demonstrou nos anos 40 e que veio a ser conhecido pelo curioso nome de Teorema da Sanduíche de Fiambre. Considere-se um objecto tridimensional com três componentes, por exemplo, uma sanduíche com pão, queijo e fiambre - pouco importa que esses componentes estejam bem ou mal distribuídos, que se concentrem em lados diferentes ou que estejam uniformemente espalhados. O que esse resultado prova é que há sempre um plano que divide o objecto em duas partes, de tal maneira que cada uma delas contenha igual quantidade dos três componentes. Ou seja, mesmo que o fiambre e o queijo estejam mal espalhados, há sempre uma maneira de cortar a sanduíche em dois bocados rigorosamente iguais.
Quando se considera um objecto bidimensional, já a partição equitativa apenas funciona com dois componentes. Suponha-se que se espalha sal e pimenta numa mesa, por exemplo. O teorema de Steinhaus mostra que há sempre uma recta que divide a superfície da mesa em duas partes que têm iguais quantidades de sal e de pimenta. Se houver três ingredientes, suponhamos sal, pimenta e açúcar, é fácil de imaginar uma concentração em três locais diferentes de tal forma que não haja linha recta que faça a partição de forma equitativa. De forma geral, o teorema diz que em «n» dimensões há sempre um hiperplano que divide simultaneamente ao meio «n» componentes. Como parece que vivemos a três dimensões e o bolo-rei tem muito mais que três constituintes, ficamos a saber: não há faca que os reparta todos equitativamente.