[obm-l] Re: [obm-l] Indu��o Finita

["David Ricardo" <davidrvp@xxxxxxxxxxxx>]

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