[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
=========================================================================