<p>I am not sure how to prove or disprove for $A_n = \{k^{n-1}, k^{n-2}, \ldots, k^0\}$ for some $k &gt; 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.</p>

CC BY-SA 2.5
2011-03-01T05:23:32.797Z
This sounds like a homework question.
Joshua Brody
CC BY-SA 2.5
2011-03-01T05:25:50.200Z
This site is for research-level questions in theoretical computer science, not questions at the level of homework problems.
Suresh Venkat
<ds.algorithms><greedy-algorithms>
How to prove $k^{n-1}, k^{n-2}, \ldots, k^0$ will result with minimum number of coins?
Raptrex
# How to prove $k^{n-1}, k^{n-2}, \ldots, k^0$ will result with minimum number of coins?

(Asked by: username_0 on 2011-03-01)

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.

**Tags:** ds.algorithms, greedy-algorithms

> **Comments:**
> **username_1**: This sounds like a homework question.  
> **username_2**: This site is for research-level questions in theoretical computer science, not questions at the level of homework problems.  

---

## 0 answers

