2
$\begingroup$

Suppose we have a bunch of objects with value, all of which are a power of $2$.
So $1, 2, 4, 8, 16, ...$
We are given some value $x \ge 1$ and we want to find the minimum amount of objects we can use that add up to this $x$.
I want to show that to obtain the minimum amount of objects, I have to pick the biggest possible object each time. This would be equal to
$k = 2^{\lfloor log_2(x)\rfloor}$

I have shown that if we pick the largest possible object each time, then we use at most 1 of each object. Now I'm not sure how to proceed. I could try to show that we require at least a certain amount of objects for each $x$, but this does not seem to be the way to go. I next thought to show that if we don't pick the biggest object, we run into problems. I was stuck however. It seems obvious for a concrete case but hard to show for an arbitrary one. On my current attempt this is where I'm stuck:

Let $x$ be any integer $\ge0$.
Suppose that $y_k$ is the greatest object we can choose. Suppose that $z_k$ is any other object we can choose.
Then $y_k = 2^jz_k$ for some $j\in\mathbb{N}$
Therefore if we choose $z_k$ rather than $y_k$, we also need to pick some ... but at this point my statement is wrong. I don't see what I can say, given that we could pick a smaller $z_k$ but still come out with the same thing.

I am still trying to think of other ways to approach this. Any hints would be appreciated. Thanks!

Edit: Just thought also, we could represent it like :
$x = y_0 + 2y_1 + 4y_2 + ... + 2^{n-1}y_{n-1}$ for $n = \lfloor log_2(x)\rfloor$

And possibly use calculus or sequences somehow?

  • 1
    Hint: use that 1 + 2 + \dots + 2^k < 2^{k+1}2011-03-28

1 Answers 1

5

Let us assume that we have coins of each type 1, 2, 4, and so on (the wording of the question does not make that clear). There is a way (and conceivably more than one way) to represent $x$ using a minimal number of coins. In any such minimal representation, there can be at most 1 coin of each type, for if there are two or more of type $2^k$, two of these coins can be replaced by a single $2^{k+1}$ coin, giving a cheaper representation.

Now suppose that $2^n \le x <2^{n+1}$. We will show that in a minimal representation of $x$, we need a coin of type $2^n$. As observed above, a minimal representation uses at most 1 coin of each type. However, $1+2+4+\cdots+2^{n-1} =2^n-1 < x$, so a minimal representation of $x$ must use a coin of type $2^n$.

The argument can be adapted to give a similar result if some types of coin are missing, though of course in that case one may need more than 1 coin of some types.