2017-02-26

Parte I - Em prol da diversidade e do multiculturalismo...

... quero hoje falar de uma questão, digamos, escandinava, ou, mais exactamente, sueca.

Estive ontem numa soirée (então; também posso ser todo finaço, de vez em quando, ou, pelo menos, ter veleidades disso) que, a páginas tantas, como me lembro de ser costume nas soirées que os meus avós ocasionalmente davam (e às quais ocasionalmente iam comigo à pendura), deu numas jogadas de Sueca. Às páginas tantas, dois jogos consecutivos acabaram em empate. Inevitavelmente, surgiu a questão: "Qual é a probabilidade de isto acontecer?"

Eu acho que é uma boa pergunta, mas não sei se serei capaz de responder. Portanto, vamos pensar todos juntos a ver se conseguimos (primeiro) destilar o raciocínio certo para descobrir a resposta ao problema, (depois) descobrir a maneira mais fácil de fazer os cálculos e (finalmente) fazer as contas. Afinal, a maior parte de nós somos engenheiros (e é engenheiros a sério; não é "engenheiro" como certos e determinados engenheiros cujo grau lhes foi atribuído a um Domingo, por exemplo); devíamos ser capazes de resolver isto!

Comecemos por calcular a probabilidade de um único jogo empatar. Ora, qualquer pontuação é função da distribuição das cartas auferidas nas 10 vazas de cada jogo pelas duas equipas. Uma vez que as cartas só podem ser auferidas no contexto das vazas, e que cada vaza tem exactamente 4 cartas, muitas distribuições são imediatamente eliminadas, nomeadamente, todas as distribuições que não atribuam um múltiplo de quatro cartas a cada equipa. Dado que a soma das cartas arrecadadas pelas duas equipas é sempre igual a 40, há um número finito de distribuições possíveis:

(pensemos primeiro em termos de vazas, para facilitar)

 - Pode uma equipa auferir todas as vazas, caso em que a distribuição é (em vazas) 10 - 0.
 - Pode a mesma equipa auferir nenhuma vaza, caso em que a distribuição é 0 - 10.
 - E, naturalmente, há todos os casos possíveis pelo meio, ou seja, todos os "passos" que o 10 - 0 tem que dar para se "transformar" no 0 - 10, que são, evidentemente, 9.

Há, portanto, 11 distribuições possíveis das vazas. Resta saber a quantas distribuições possíveis das cartas isto corresponde (é aqui, julgo eu, que as coisas começam a complicar-se). Só de uma maneira é que é possível distribuir cada um dos os casos extremos - essa é a parte fácil. O caso em que uma equipa arrecada uma única vaza corresponde a "combinações de 40 tomados 4 a 4" (digam lá que não já tinham saudades disto...!) maneiras de distribuir as cartas. O mesmo número traduz o caso em que a mesma equipa ganha todas excepto uma das vazas. É aqui que surge uma certa semelhança com a quadragésima primeira linha do triângulo de Pascal, mas com uns quantos elementos removidos (nomeadamente, todas a combinações de 40 tomados k a k tais que k não seja um múltiplo de 4).

Antes de começar a fazer contas à maluca para descobrir quantas maneiras existem de distribuir as cartas pelas equipas, surge-me a questão: haverá vazas impossíveis? E combinações de vazas que, não implicando repetição de cartas, não podem, de acordo com as regras, suceder? Como não sou suficientemente versado em Sueca para responder, é uma (a primeira) questão que vos convido a responder (e, como veteranos do ensino superior que somos, já sabemos que este convite pede a demonstração do raciocínio por detrás da nossa resposta).

Seguidamente, é preciso saber de quantas maneiras é que é possível fazer 60 pontos. Lembro-me, na nossa louca juventude, de, durante a cadeira de Desenvolvimento e Análise de Algoritmos (era de opção no 5º ano de ECT, e mudou de nome aquando do processo de Bolonha, mas não me lembro para o quê, e sim, nós chamávamos a disciplina de "duh!") de falarmos de problemas semelhantes, chamados de "Binary Knapsack Problem" ou "0-1 Knapsack (ou Rucksack) Problem". Dito em linhas gerais, sabendo que cada um de n itens tem determinado peso e determinado valor, de que maneira devemos incluir (na metafórica mochila) 0 ou 1 cópia de cada item de maneira a carregar o maior valor possível sem exceder determinado peso total (a propósito, isso é exactamente o tipo de perícia que facilmente se pode desenvolver quase inconscientemente com dedicação suficiente aos jogos da Bethesda, pelo menos do Oblivion para cá, em que a frase "You are over-encumbered and cannot move" se torna uma irritação frequente)? O nosso problema é semelhante, na medida em que existe, no máximo, uma cópia de cada carta que uma equipa pode auferir, cada carta tem um peso (1) e um valor (0, 2, 3, 4, 10 ou 11, consoante se trate de um 2 - 6, uma Dama, um Valete, um Rei, uma Manilha (/Bisca/Sete/Seta e mais todas as maneiras de que a malta se refere ao 7) ou um Às) conhecidos à partida. É, igualmente, diferente na medida em que, ao invés de maximizar o valor total da escolha, pretendemos arrecadar exactamente 60 pontos. Convido-vos (segunda vez) a adaptar a solução do Knapsack Problem para o nosso caso particular.

Falhando isso, resolva-se o problema extensionalmente: não é difícil imaginar um grupo de cartas que some 60 pontos (quatro Ases, uma Manilha, um Rei e uma Dama, por exemplo). Podendo acertar os números com "palha", todas as maneiras de fazer 60 pontos devem ser viáveis (excepção eventual feita às que coincidam com distribuições que, em resposta à primeira pergunta que vos propus, sejam impossíveis, caso as haja). Ora, dada a reduzida dimensão do nosso problema, não é difícil, por exemplo, escrever um pequeno programa que descobre todas as distribuições possíveis das cartas de maneira a que o jogo resulte empatado, mas preferia não partir para a solução da força bruta até ter a certeza de que não existe uma solução analítica mais elegante (porque a questão é essencialmente académica; no lugar de trabalho, dada a dimensão do problema, em menos tempo que já gastei a escrever esta muralha de texto, tinha feito e corrido o malvado programa).

Dado que temos, depois de somar 11 combinações de 40 tomados k a k, com k pertencente a [0, 40], sabendo que k é um múltiplo de 4, o número de casos possíveis, e, depois de (no melhor caso) usarmos a nossa brilhante adaptação do problema da mochila ou (no pior caso, mas, desta vez, dito com a voz nasalada do Professor Madeira, para quem aproveito para mandar um grande abraço) de contarmos as linhas que o nosso programa de força bruta imprimir no écran, teremos o número de casos favoráveis, e sabemos que a probabilidade de empatar é a razão entre os dois.

Uma vez que o resultado de cada jogo é um acontecimento independente do resultado dos jogos que o precedem ou que o sucedem, a probabilidade de empatar dois jogos consecutivos é o produto da probabilidade de empatar um único jogo consigo mesma, ou seja, coloquialmente, "ao quadrado".

Espero ter despertado em vós saudades suficientes das nossas aulas de matemática, combinatória, probabilidade e estatística (disse ele, de cara séria, acreditando piamente que tendes saudades desses tempos) o suficiente para me quererdes ajudar. Vamos meter números nestas ideias! Até lá...

... Pax vobiscum atque vale.

3 comments:

Pedro Francisco said...

Vou tentar ler este post com o cérebro acordado amanhã!

P.S.: Tens saudades de MPE, claramente!

Sintra said...

Acho que te esqueceste de um factor muito importante: o humano jogador. Aquele que comete erros, que faz uma renuncia, e que joga emotivamente em vez de racionalmente. Acho que nao ha probabilidade para isso...

ArabianShark said...

@Pedro Francisco Um bocadinho, de vez em quando, sim... sou um tolo saudosista!

@Sintra Claramente, e é isso que diferencia uma probabilidade de uma certeza estatística (se não for isso um contra-senso). Mas eu só estou intressado na parte das contas.