0
$\begingroup$

What it says in the title.

Just kidding, the title is very poorly explained, sorry about that. Here is a more descriptive question.

How can I prove the following.

Suppose we have some set of coins $C$, each with a value of the form $b^a$ where $a<k$, the base $b$ is constant and the exponent $a$ varies from coin to coin.

Suppose as well that the sum of all the coins in $C$ is greater than or equal to $b^k$. i.e.

$$\sum_{c \in C}\text{value}(c) \geq b^k$$

Then we must show that there exists $D \subseteq C$ such that all the coins in $D$ sum up exactly to $b^k$. i.e.

$$\sum_{d \in D}\text{value}(d) = b^k$$

I am trying to use this as a lemma in a longer proof, and it is the last link I need to complete the proof. I would appreciate any help I can get to point me in the right direction. Thank you.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider the collection, $\mathscr{C}$, of all subsets of $C$ which sum to $≥b^k$. We know that $\mathscr{C}$ is not empty (since it at least contains $C$). Let $C_0$ be a subset with minimal sum in $\mathscr C$. We claim that the sum of the coins in $C_0$ is exactly $b^k$, which will clearly conclude the proof. So, suppose otherwise. Suppose $$N=\sum_{c\in C_0}\text {value}(c)>b^k$$

As a special case, to illustrate the idea here, first note that $C_0$ does not contain a coin with value $1$, else we could remove it, contradicting the minimality of $C_0$.

We can easily generalize this argument. Let $b^{a_1}$ be the minimal value of a coin in $C_0$. Then $b^{a_1}\,|\,N$ so $b^{a_1}\,|\,(N-b^k)$. But then $N≥b^k+b^{a_1}$ so we can remove a coin of value $b^{a_1}$ and get a subset in $\mathscr{C}$ with smaller sum than $C_0$, contradicting the minimality of $C_0$, so we are done.

$\endgroup$
4
  • $\begingroup$ Isn't the step where we show that C_0 doesn't contain a value of 1 unnecessary? since the next step also works for b^{a_i} >= 1? $\endgroup$ Commented Nov 8, 2020 at 15:45
  • 1
    $\begingroup$ Yes, it is unnecessary. I just thought that it was a useful illustration of the principle, and I felt that writing things like $1\,|\,(N-b^k)$ looked odd. But, as you note, my argument using $a_1$ works just fine if $a_1=0$. I'll edit to clarify. $\endgroup$ Commented Nov 8, 2020 at 16:07
  • $\begingroup$ Thank you, this was very helpful. I have just finished composing my overarching proof. Much appreciated $\endgroup$ Commented Nov 8, 2020 at 16:08
  • $\begingroup$ Glad to have helped. $\endgroup$ Commented Nov 8, 2020 at 16:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.