5
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Isn't this pretty obviously about $\log_2 N$? Original can be done in 7 notes: 1,2,4,8,16,32,64 $\endgroup$ Nov 7, 2020 at 14:41
  • $\begingroup$ @JeremyDover rot13(V gubhtug gurer zvtug or fbzr erqhaqnapl orpnhfr guvf tvirf hc gb bar gjb frira, ohg gur zbfg inyhrf gung pna or pbirerq jvgu fvk abgrf vf fvkgl guerr. Ubjrire gurer ner inevbhf inyhrf sbe gur hccre guerr abgrf gung jbex). $\endgroup$ Nov 7, 2020 at 16:43

2 Answers 2

8
$\begingroup$

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$.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nice! You could add a proof of optimality. $\endgroup$
    – Magma
    Nov 7, 2020 at 16:45
  • $\begingroup$ @Magma Sorry I went away for a bit. WhatsUp seems to have it covered now. $\endgroup$
    – hexomino
    Nov 7, 2020 at 17:16
  • $\begingroup$ I was actually typing that answer when @Magma made this comment (: $\endgroup$
    – WhatsUp
    Nov 7, 2020 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.