Um problema de um manual de Matemática do 12º ano

Não sei qual é o manual, não sei quem são os autores, só sei o que nos diz hoje o José Paulo Viana na solução do desafio do Público da semana passada: "O Martim tem uma antiga balança de pratos mas só lhe restam cinco pesos: 2g, 5g, 10g, 20g e 50g. Com estes pesos quantas pesagens diferentes se conseguem fazer?"
O manual indica 31 como resposta, o que está obviamente errado, como o JPV nos explica. Aliás, bastava os autores alguma vez terem visto alguém num mercado qualquer manusear uma dessas balanças, como tantas vezes vi no Mercado do Bolhão e em tantos outros sítios, para perceberem que uma boa parte da técnica de utilização destas balanças reside na possibilidade de se colocarem pesos nos dois pratos e numa destreza mental de respeito.
Os autores do manual lá terão pensado que "aqui havia Informática", partiram do princípio de que cada peso só pode ser utilizado num dos pratos, e limitaram-se a contar quantos números binários de 5 dígitos diferentes de 0 existem, sendo que em cada posição o dígito 0 significaria que o peso respectivo não é utilizado e o dígito 1 significaria que é:

50g	20g	10g	5g	2g
0/1	0/1	0/1	0/1	0/1

Muito habilidoso, mas pouco instrutivo, até porque a suposta ideia do contador binário só funciona se os pesos, colocados por ordem decrescente, pesarem cada um no máximo metade do anterior. Imagine-se, por momentos, que os pesos eram de 2g, 5g, 10g, 20g e 30g, por exemplo. Então, como 30g poderia ser pesados de duas maneiras diferentes, já não haveria as tais 31 pesagens diferentes!
Para contar todas as hipóteses, de um peso estar num prato, no outro, ou não estar em nenhum, seria necessário utilizar um contador ternário, em que o dígito -1 significaria que o peso está colocado no mesmo prato do objecto:

50g	20g	10g	5g	2g
-1/0/1	-1/0/1	-1/0/1	-1/0/1	-1/0/1

Neste caso, há 3 à 5ª contagens diferentes, das quais uma conduz ao peso 0, e metade das restantes correspondem a pesos negativos. As restantes 121 correspondem a pesos positivos.
O problema agora está nas repetições...
A maneira mais simples será analisar todas as possibilidades numa folha de cálculo, e verificar que há mesmo só 52 possibilidades.

Fibonacci

Este desenho representa um dos estudos mais interessantes da matemática e da arte, e que começou eventualmente com Euclides e as suas aproximações ao desenho de espirais por justaposição de quartos de círculo.

Começando com um quadrado de lado 1, ele acrescentava um segundo quadrado também de lado 1, depois um de lado 2 (1 + 1), um de lado 3 (2 + 1), um de lado 5 (3 + 2), um de lado 8 (5 + 3). um de lado 13 (8 + 5), e assim sucessivamente.
Esta sequência de lados dos quadrados - 1, 1, 2, 3, 5, 8, 13, ... - é a sequência de Fibonacci, que tantas vezes nos surpreende. Define-se recursivamente:

F(n) = F(n -1) + F(n - 2)
F(1) = 1
F(0) = 1

A figura anterior é um rectângulo, e a relação entre a sua largura e a sua altura é considerada artisticamente proporcionada, sendo conhecido pelo rectângulo dourado. À medida que novos quadrados são acrescentados, a proporção converge para um valor determinado:

Um dos problemas destas sucessões definidas recursivamente é a dificuldade em obter um termo geral, que permita calcular qualquer dos seus termos sem ser necessário retroceder até F(0).
Pode-se?
Os mais familiarizados com a transformada Z reconhecem imediatamente aqui uma aplicação, e com alguns cálculos simples até chegam ao valor exacto de F(n)/F(n - 1) quando n tende para infinito: (1 + Ö5)/2 = 1.6180339887... Número mágico, presente na pintura, na arquitectura, na música, na economia, e em muitos outros domínios.

Recursividade

Recursividade, o que é?
Eis um assunto que tem de ser visto com todo o cuidado, para não restarem dúvidas.
Uma função recursiva será uma função em cuja definição se recorre à própria função. Um exemplo muito usado é o do cálculo de n! (factorial de n): se soubermos (n-1)!, então calcular n! é facílimo, basta multiplicar n por (n-1)!:

int factorial (int n)
{
   return n * factorial (n-1);
}

E isso basta? Não! Não basta. Assim, nunca mais pára! Se quiséssemos calcular 5!, por exemplo, iríamos obter sucessivamente


5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 0!
5 * 4 * 3 * 2 * 1 * 0 * (-1)!
...

Precisamos claramente de uma instrução que indique que não é necessário continuar o processo, uma vez que chegamos a um valor conhecido da função, e podemos retroceder. Por exemplo

int factorial (int n)
{
   if (n == 0) return 1;
      else return n * factorial (n-1);
}

que permite que agora tudo corra bem:

5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1 * 1
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

e obtenhamos o resultado correcto.
Temos de voltar a isto, mas acompanhados de Fibonacci.

NetLogo at work

O NetLogo permite simular o problema do lançamento do dado de uma maneira muito simples.
Considerei um agente para cada comprimento de uma série de lançamentos, e o agente na posição N avançava um passo sempre que ocorria uma série de comprimento N.

Neste experiência, simularam-se 5622995 lançamentos, e o número médio de lançamentos necessário para conseguir uma série de seis resultados diferentes foi de 14.70195.

Um problema com um dado

Queremos saber quantas vezes temos, em média, de lançar um dado até obter as seis faces diferentes, por uma ordem qualquer?
Aqui está um problema interessante, que obriga a pensar.
O número mínimo de lançamentos é obviamente 6

mas pode haver repetições até sair a sexta face.
O primeiro lançamento dá-nos obrigatoriamente a primeira face!
E a partir daqui quantos lançamentos serão necessários, em média, para obter uma segunda face diferente desta? São 5 faces favoráveis sobre seis possíveis, o que quer dizer que a probabilidade de sair uma das faces que nos interesse é de 5/6 e o número médio de lançamentos que é necessário realizar para nos sair essa face é de 6/5.
Para obtermos uma terceira face, em que há quatro faces favoráveis sobre seis possíveis, a probabilidade de sair uma face que nos interesse é de 4/6 e o número médio de lançamentos que é necessário realizar para nos sair essa face é de 6/4. Etc.
No total, para obtermos as seis faces diferentes, necessitamos em média de 1+6/5+6/4+6/3+6/2+6/1=14.7 lançamentos!
Fácil! Verdade? Como verificar?