Paying bills in Alphagonia

Question

In the Kingdom of Alphagonia, where the national currency is the Alpha, banknotes are available in all whole-number denominations of alphas: 1, 2, 3,...

a) What is the least number of such notes a citizen of Alphagonia needs top carry in her wallet if she wishes to be certain that she will be able to pay any amount between 1 and 100 alphas without requiring any change?

For example, if she carries 19 notes (nine 1-alpha notes, one 10-alpha notes, and nine 11-alpha notes) she can pay any amount in that range, but is this best possible?

b) What is the least number of notes she will require if she wishes to pay any amount in the range 1 to N, N any positive integer?

Answer 1

Here is a proof of optimality.

For general $N$, we need

$\lceil\log_2(N + 1)\rceil$

notes, which can be chosen as

notes of values $2^0, 2^1, \dots, 2^{k - 1}$ where $k = \lceil\log_2(N + 1)\rceil$.

These can, in an obvious way, be used for any number between $1$ and $N$.

To prove that this is optimal:

with $m$ notes, there can be at most $2^m$ different representable numbers, as this is the number of subsets of the notes.
And of course the empty set has a value of $0$, so together with $1, \dots, N$, we get the inequality: $ N + 1 \leq 2^m$, which translates to $m \geq \lceil\log_2(N + 1)\rceil$.

Note: it's the same as the answer of @hexomino: $N + 1\leq 2^m \iff N \leq 2^m - 1 \iff N < 2^m$, hence the smallest $m$ such that $2^m \geq N + 1$ is one plus the largest $m$ such that $2^m \leq N$.

Answer 2

I may be missing something but I think the answer to (a) is

7 notes
which can be achieved by carrying around 1 note of each of the powers of 2 less than 100 - 1, 2, 4, 8, 16, 32, 64. For a given amount she would then just need its binary representation and select one of each of the notes represented by a 1.

And (b) would then be

Generalising this approach she would only need $$\lfloor \log_2 N \rfloor +1 $$ notes to achieve any amount between 1 and N.

See the answer of WhatsUp for a proof of optimality