1
$\begingroup$

I am not sure how to prove or disprove for $A_n = \{k^{n-1}, k^{n-2}, \ldots, k^0\}$ for some $k > 1$, the greedy method will yield solutions with minimum number of coins. I know that each number is a subset of $k$ and that they are exponential but I dont know how I would prove or disprove this.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This sounds like a homework question. $\endgroup$
    – Joshua Brody
    Mar 1, 2011 at 5:23
  • 2
    $\begingroup$ This site is for research-level questions in theoretical computer science, not questions at the level of homework problems. $\endgroup$
    – Suresh Venkat
    Mar 1, 2011 at 5:25

0

Reset to default

Browse other questions tagged or ask your own question.