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.

  • 2
    $\begingroup$ This sounds like a homework question. $\endgroup$ 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$ Mar 1, 2011 at 5:25


Browse other questions tagged or ask your own question.