Rješenja zadatka "Državno natjecanje 2000 SŠ1 4" korisnika "ivl"

Točno

3. prosinca 2013. 22:30 (10 godine, 11 mjeseci)

Korisnik: ivl
Zadatak: Državno natjecanje 2000 SŠ1 4 (Sakrij tekst zadatka)

Na raspolaganju su kovanice od $1$ , $2$ , $5$ , $10$ , $20$ , $50$ lipa i od $1$ kune. Dokažite da ako se iznos od $M$ lipa može isplatiti pomoću $N$ kovanica, onda se iznos od $N$ kuna može isplatiti pomoću $M$ kovanica.

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Reformulacija: ako mozemo za $(M, N)$ , mozemo i za $(100N, M)$
Ako vrijedi za $(a,b)$ i za $(c,d)$ , onda vrijedi i za $(a+b,c+d)$

Indukcija
Baza: $M=0$ , $N=0$
Pretpostavka: $(M, N)$ i $(100N, M)$ mozemo
Korak:
Neka je $a$ kovanica.
$(M+a, N+1)$ mozemo
$(100, a)$ mozemo jer je $100/a$ isto kovanica
$\Rightarrow (100N+100, M+a)$ mozemo

Ocjene: (1)