Solution of task "Državno natjecanje 2000 SŠ1 4" by user "ivl"

Točno

Dec. 3, 2013, 10:30 p.m. (12 years, 8 months)

User: ivl
Task: Državno natjecanje 2000 SŠ1 4 (Hide problem text)

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.

Warning: You haven't solved this problem yet.
Click here to display the solution.

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

Ratings: (1)