SOLUÇÂO DE PROBLEMA DAS MOEDAS

Se ao desenhar o triângulo de Pascal for arrastando uma linha e uma coluna uma posição para a frente, ter-se-á então um arranjo claro, que mostra os números de Fibonacci, como se pode ver pelo seguinte esquema;

	0	1	2	3	4	5	6	7	8	9
0	1	.	.	.	.	.	.	.	.	.
1	.	1	1	.	.	.	.	.	.	.
2	.	.	1	2	1	.	.	.	.	.
3	.	.	.	1	3	3	1	.	.	.
4	.	.	.	.	1	4	6	4	1	.
5	.	.	.	.	.	1	5	10	10	5
6	.	.	.	.	.	.	1	6	15	20
7	.	.	.	.	.	.	.	1	7	21
8	.	.	.	.	.	.	.	.	1	8
9	.	.	.	.	.	.	.	.	.	1
	1	1	2	3	5	8	13	21	34	55

Este esquema pode ser explicado através do problema   que se referiu anteriormente.

A pergunta relacionada com este problema é:

De quantas maneiras se pode pagar n pence, usando apenas moedas de 1 pence e de 2 pence? A ordem das moedas vai ser importante para resolver este problema. Ou seja, 1p+2p paga a verba de 3p tal como 2p+1p, mas, esta irá ser considerada como uma resposta diferente da outra.

Aqui estão as respostas para um pagamento de 5p, usando apenas moedas de 1p e 2p:

1p	2p	3p	4p	5p
1p	2p 1p+1p	1p+2p 2p+1p 1p+1p+1p	2p+2p 1p+1p+2p 1p+2p+1p 2p+1p+1p 1p+1p+1p+1p	1p+2p+2p 2p+1p+2p 2p+2p+1p 1p+1p+1p+2p 1p+1p+2p+1p 1p+2p+1p+1p 2p+1p+1p+1p 1p+1p+1p+1p+1p
1 maneira	2 maneiras	3 maneiras	5 maneiras	8 maneiras

Analise-se de outra forma o quadro anterior- arranjando as respostas de acordo com o número de 1p e 2p que foram as moedas que se usaram. No esquema seguinte, as colunas representam todas as maneiras de pagar a quantia mencionada no topo de cada coluna, como se tinha na tabela anterior, mas agora as linhas representam o número de moedas usadas na solução.

Quantia	1p	2p	3p	4p	5p
1 moeda	1p	1p
2 moedas		1p+1p	1p+2p 2p+1p	2p+2p
3 moedas			1p+1p+1p	1p+1p+2p 1p+2p+1p 2p+1p+1p	1p+2p+2p 2p+1p+2p 2p+2p+1p
4 moedas				1p+1p+1p+1p	2p+1p+1p+1p 1p+1p+1p+2p 1p+1p+2p+1p 1p+2p+1p+1p
5 moedas					1p+1p+1p+1p+1p

Contando o número de soluções de cada quadrado, obtém-se exactamente a forma do triângulo de Pascal que se mostrou anteriormente.