Školjka

%V0 Za sustav novčanica $1 = n_1 < n_2, ... < n_k$ kažemo da je dobar ako "greedy" postupak vraćanja novca uvijek rezultira s najmanjim brojem isplaćenih novčanica. Dokažite da je sustav $1 < b < a$ dobar ako i samo ako postoji $k \in \mathbb{N}$ takav da je $\lceil\frac{a}{k}\rceil = b$. [i]Napomena: U greedy postupku u svakom koraku vraćamo najviše moguće najvećih mogućih novčanica. Nadalje, $\lceil x\rceil$ označava najmanji cijeli broj veći od (ili jednak) $x$.[/i]