quinta-feira, 24 de abril de 2008

As fatias do bolo-rei

Do novo livro de Nuno Crato, "A Matemática das Coisas" (Gradiva), que saiu ontem, no Dia Mundial do Livro, transcrevemos um dos capítulos. Esperamos que abra o apetite para o resto!

«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 que nenhum fique prejudicado.

A história é muito conhecida e aplicada em muitas 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 de dois parceiros. Como se há-de fazer se forem três, por exemplo? Ou se forem muitos mais? E se tivermos um bolo a dividir entre vinte pessoas igualmente gulosas? O problema não é simples e os matemáticos têm vindo a desenvolver algoritmos para partilhas equitativas. Esses algoritmos podem ter aplicações em áreas muito diversas, desde a partilha de heranças e a 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 de dois parceiros. Se tivermos quatro pretendentes a um bolo, por exemplo, o algoritmo desdobra-se em duas etapas. Começa-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 ao meio, seguindo de novo o processo de um partir e o outro escolher.

É fácil ver que este método iterativo 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. Mas pensando bem, consegue arranjar-se 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 um número qualquer 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 fazer deslizar a faca sobre o bolo, a partir de um dos lados. Vai progredindo com a faca até que um dos parceiros diga «Pára!». Nesse momento pára a faca e corta 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 ser retirada ao bolo uma quantidade 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.
-----------------------------------------------------------------------------------------------

Como dividir um bolo rei?

Para dividir equitativamente um bolo homogéneo por um número arbitrário de pessoas pode utilizar-se o algoritmo da faca deslizante. Uma pessoa desloca uma faca sobre o bolo até que um dos parceiros diga «Pára!» e reclame a fatia de bolo correspondente. O processo prossegue até que novo parceiro reclame nova fatia, e assim sucessivamente, até que o bolo esteja dividido por todos.
----------------------------------------------------------------------------------------------

Depois de ter recolhido a sua fatia, o primeiro parceiro 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 todas as 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 de mais, sem ninguém a ter obrigado a isso.

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 que garanta 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, se concentrem em lados diferentes ou estejam uniformemente espalhados. O que esse teorema 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 imaginar uma concentração em três locais diferentes de tal forma que não haja linha recta que os divida 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 de três constituintes, ficamos a saber que não há faca que os reparta todos equitativamente.

2 comentários:

  1. gosto destas coisas, onde a matemática funciona como ferramenta ao serviço de soluções compreensiveis dos problemas.

    gosto quando a matemática nos permite resolver problemas através de equações que verificamos que funcionam mas não compreendemos o porquê.

    só não gosto mesmo é quando me dizem que compreender não é preciso ... cala-te e calcula...

    ResponderEliminar
  2. Transcrevo aqui o comentário que fiz no meu blogue a este post porque faço lá uma pergunta e lanço um desafio a que gostava que os leitores do De Rerum Natura respondessem:

    --

    No sempre interessante De Rerum Natura, leio hoje uma transcrição dum capítulo do novo livro de Nuno Crato, "A Matemática das coisas" (Gradiva), intitulado As fatias do bolo-rei, que trata do problema de dividir um bolo por várias pessoas sem que no final alguém possa alegar ter sido injustiçado. Um problema interessante, sem dúvida. (Vá ler o texto, bem curto, antes de ler o seguinte:)

    Esse problema foi tratado num episódio duma série infantil dedicada a esse género de problemas chamada "Aqui há gato". Via-o regularmente em criança, acho que na RTP 2. Não tenho a certeza, mas acho que era apresentado pelo Pedro Ribeiro.

    Primeiro deram a solução para duas pessoas. A partir do dia em que o vi, usei sempre que podia o método quando o problema surgia no mundo real. Depois deram a solução para 3 pessoas, cujos pormenores infelizmente esqueci. Mas lembro-me de que não era usado o "método da faca deslizante", descrito no livro. Usava-se uma moeda para escolher a ordem de decisões, mas sem introduzir injustiça, claro. (Por exemplo, podemos usar uma moeda para o caso de duas pessoas sem injustiçar ninguém.) Mas o mais importante é que havia uma iteração em que se desenhava um corte, sem haver propriamente um corte duma fatia. Um dos participantes escolhia uma das partes virtuais. Numa iteração posterior, esse corte era redesenhado por outro participante.

    Não me lembro do método. Se alguém o conhecer, era interessante que o expusesse aqui na caixa de comentários.

    Nessa série lembro-me também de ver um daqueles problemas de obter uma medida dum líquido a partir de dois recipientes de medida conhecida mas sem graduação. E muitos outros problemas matemáticos divertidos.

    Mas um problema que me fascinou e que nunca mais esqueci foi este:

    Três pessoas tomam chá. Outra pessoa colou três cartões coloridos debaixo de cada chávena. Os jogadores sabem que há disponíveis cinco cartões: 3 vermelhos e 2 pretos, mas desconhecem as cores escolhidas pelo jogador exterior. Os jogadores ao beberem vêem os cartões por debaixo das chávenas dos outros, mas não vêem o seu próprio cartão. Ganha quem acertar primeiro na cor da sua chávena. Ora nesse episódio é mostrada a perspectiva dum dos jogadores, que vê que os amigos têm ambos um cartão vermelho. Nenhum deles arrisca uma resposta. Tendo em conta que os amigos são ambos inteligentes, o jogador da nossa perspectiva descobre a solução. Deixo aqui o desafio aos meus leitores de descobrirem qual a cor desse jogador e que raciocínio seguiu que lhe permitiu chegar à conclusão. É uma espécie de problema lógico-psicológico.

    Ah, fiquei com vontade de comprar o livro. Do Nuno Crato só li o livro "O 'eduquês' em discurso directo" (Gradiva), que é muito bom e cuja leitura aconselho veementemente.

    --

    http://departeincerta.blogspot.com/2008/04/um-problema-lgico-psicolgico.html

    Obrigado.
    Pedro

    ResponderEliminar

1) Identifique-se com o seu verdadeiro nome.
2) Seja respeitoso e cordial, ainda que crítico. Argumente e pense com profundidade e seriedade e não como quem "manda bocas".
3) São bem-vindas objecções, correcções factuais, contra-exemplos e discordâncias.