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?

hexomino · Answer

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

And (b) would then be

See the answer of WhatsUp for a proof of optimality

WhatsUp · Answer

Here is a proof of optimality.
For general $N$, we need

notes, which can be chosen as

These can, in an obvious way, be used for any number between $1$ and $N$.
To prove that this is optimal:

Paying bills in Alphagonia

2 Answers

Add your own answers!

Ask a Question