Točno
3. prosinca 2013. 22:30 (10 godine, 6 mjeseci)
Na raspolaganju su kovanice od
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
,
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
,
![5](/media/m/e/a/3/ea36c795dac330f34d395d8364d379b6.png)
,
![10](/media/m/5/b/e/5beb46430dbe2d22c0f8289c36a92c84.png)
,
![20](/media/m/1/1/e/11e1c5de3460c5571469b3ff0f222b7e.png)
,
![50](/media/m/2/f/c/2fceaac52c4bae9bf67827f9dc8c6130.png)
lipa i od
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
kune. Dokažite da ako se iznos od
![M](/media/m/f/7/f/f7f312cf6ba459a332de8db3b8f906c4.png)
lipa može isplatiti pomoću
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
kovanica, onda se iznos od
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
kuna može isplatiti pomoću
![M](/media/m/f/7/f/f7f312cf6ba459a332de8db3b8f906c4.png)
kovanica.
%V0
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)](/media/m/a/d/6/ad607af369ea5c4e4fe5dcb60d6e8686.png)
, mozemo i za
![(100N, M)](/media/m/d/9/6/d96c7bc8f299c766b81b51f58161510e.png)
Ako vrijedi za
![(a,b)](/media/m/e/2/6/e263229694cdbeb908488db2d0351f0a.png)
i za
![(c,d)](/media/m/c/0/a/c0af6a1a63c6fabfd70329ed34bb7312.png)
, onda vrijedi i za
![(a+b,c+d)](/media/m/a/0/d/a0dc9c387f6db754a2bbe99687d8e56d.png)
Indukcija
Baza:
![M=0](/media/m/6/0/b/60b018002c86b013d89cbca6a3c9711c.png)
,
![N=0](/media/m/0/6/1/0613db42cf1e0ab25e6e95348ed9bf1c.png)
Pretpostavka:
![(M, N)](/media/m/a/d/6/ad607af369ea5c4e4fe5dcb60d6e8686.png)
i
![(100N, M)](/media/m/d/9/6/d96c7bc8f299c766b81b51f58161510e.png)
mozemo
Korak:
Neka je
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
kovanica.
![(M+a, N+1)](/media/m/f/b/e/fbe1cb261ddaac96206ddc8579de11aa.png)
mozemo
![(100, a)](/media/m/2/9/7/297128a262e547d8c2a2b696b2132036.png)
mozemo jer je
![100/a](/media/m/5/6/e/56e3c20380449110a5b99de26b7800cf.png)
isto kovanica
![\Rightarrow (100N+100, M+a)](/media/m/e/d/e/ede6efe1594f286b1149b5c08af94253.png)
mozemo
%V0
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
5. prosinca 2013. 18:01 | ikicic | Točno |