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.

2017-02-15

Quero, posso e faço!

Isto vem um pouco na veia de um sentimento que o Pedro exprimiu aqui há uns posts atrás...

Quando éramos pequeninos, havia uma série de coisas que só podíamos fazer "quando fôssemos grandes": beber álcool, ficar acordado até tarde, ver filmes para crescidos, etc..

Depois crescemos (um bocado), e passou a haver coisas que só podíamos fazer quando certa condição se verificasse: podíamos sair à noite, mas só quando tivéssemos dinheiro; podíamos fazer uma lanzada, mas só quando não tivéssemos exames ou trabalhos iminentes; podíamos ir de férias para onde bem nos aprouvesse, à hora que quiséssemos, mas só quando já tivéssemos carro próprio.

Depois crescemos outro bocado e o "quando" começou a ficar menos nítido: quando tiver tempo; quando tiver paciência, quando receber, quando vencer o depósito a prazo, quando tiver acabado de pagar a hipoteca.

Finalmente, surge o "quando" mais malvado de todos: o "um dia destes".

Concretamente: desde que vim morar para S. João, continuando a ir frequentemente a Viseu, sempre que faço a viagem de volta, dá-me sempre ganas de ir a Aveiro. Primeiro na saída para o IC2 em direcção ao Porto e Albergaria-a-Velha (fico sempre com vontade de sair, só para ver se a meretriz que todas as semanas via junto da última estação de combustível antes de voltar para a A25 ainda lá está...), e depois logo antes da saída para a A1, que é onde deixo a A25 (e, a propósito de nada, deixo ficar que, saíndo onde costumo sair, percorro quase 10 Km na A1, pelo que pago €0.85, mas, se andar apenas mais 2 Km, passo logo a pagar €2.05 - justo...).

Pois este domingo deu-me o "vaipe" e fui mesmo até Aveiro. Fui tomar café à Doce Aveiro, onde ainda fui reconhecido (apesar de já lá não ir há 7 anos), passeei no Glicínias (que está largamente na mesma), passei diante de onde ainda me lembrava que colegas e amigos tivessem morado e, claro está, calcorreei o Campus de Santiago, desde o Complexo Pedagógico até à nova Reitoria, depois passei no glorioso Departamento de Electrónica, Telecomunicações e Informática, diante do bar do Departamento de Biologia, seguindo em direcção ao Departamento de Línguas e Culturas e à Velha Reitoria.

Sabeis que mais? Foi giro. Recomendo. Mas, sobretudo, recomendo abolir o "um dia destes". Vão já!

Pax vobiscum atque vale.

2017-02-09

Bitcoins do pé para a mão

Precisava de 0.033 bitcoins... alguém me sabe dizer como é que as adquiro (a troco de alguma coisa como €36.00) sem ter que andar a revelar mais que o que me apetece a um site qualquer?