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

[Fábio Dias Moreira <fabio.dias.moreira@xxxxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sunday 27 April 2003 10:53, André Luíz wrote:
> [...]
> 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.
> [...]

Lema: Se é possível pagar a quantia n (n >= 8) com b notas de 5 (e algumas 
notas de 3) então é possível pagar até a quantia n+b com notas de 3 e 5.

Prova: Se n = a*3 + b*5, então:

n+1 = (a+2)*3 + (b-1)*5
n+2 = (a+4)*3 + (b-2)*5
...
n+b = (a+2*b)*3 + 0*5

Mas:

8 se paga como 3+5 (também se paga até o 9)
10 se paga como 5+5 (também se paga até o 12)
13 se paga como 5+5+3 (também se paga até o 15)
16 se paga como 5+5+3+3 (também se paga até o 18)
19 se paga como 5+5+3+3+3
5*k (k >= 4) se paga como 5+5+5+...+5, onde há k cincos (também se paga até o 
5*k + k >= 5*k + 4)

Com o último caso é possível cobrir todos os inteiros maiores ou iguais a 20.

[]s,

- -- 
Fábio "ctg \pi" Dias Moreira
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE+rAqhalOQFrvzGQoRAofrAKDhkNOVQLZE+fJ7MPAf+4pMF9gjawCffNRW
yyrxJVoma7JPiKuaPuEAgqw=
=ZPcY
-----END PGP SIGNATURE-----

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