[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] Indução Finita



3) Mostre que é possível pagar, sem receber troco, qualquer quantia inteira
de reais, maior do que 7, com notas de 3 reais e 5 reais.

Defina o predicado P(k) como sendo 'é possível pagar uma quantia k com notas
de 3 e 5 reais'.

Mostre que P(8) é verdadeiro (3 + 5 = 8). Assuma que P(k) é verdadeiro e
tente provar que se P(k) é verdadeiro, P(k+1) também é para os inteiros
maiores que 7.

Para provar isso, veja os seguintes casos:

1) Se existe uma nota de 5 reais fazendo parte da quantia k, troque os 5
reais por duas notas de três reais para obter a quantia k+1.
2) Se não tiver nenhuma nota de 5 reais, deve haver pelo menos 3 notas de
três reais na quantia k (para satisfazer a condição k > 7).  Troque essas
três notas de três reais por duas notas de 5 reais para obter a quantia k+1.

Então é possível a partir de uma quantidade k se chegar a uma quantidade k+1
com notas de 3 e 5 reais para k > 7, portanto o predicado é verdadeiro pra
todo k inteiro maior que 7.

Não sei se é a melhor solução para o problema, mas eu acho que tá certo.

[]s
David

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================