New currency

Consider the quadruple $\{101,105,110,150\}$ of Brill notes. I claim all values $N \geq 1000$ are expressible using these. First note that we need to prove it for $1000$ to $1100$ , as all higher numbers can be achieved by adding some multiple of 101 to these numbers.

• $1000 = 3(150) + 5(110)$ & $1100 = 10(110)$

For numbers $N = 1000 + 10b + c$ , consider the following:

• If $b,c < 5$ , we can write it as $N = c(101) + b(110) + (10-b-c)100$ for $(10-b-c) = 3,6,7,9$ since $300 = 2(150), 600 = 4(150), 900 = 6(150), 700 = 150 + 5(110)$ .

• for $(10-b-c) = 2,4$ write $N = c(101) + b(110) + 200 = 4(105) + c(101) + 110(b-2)$ [note $b>2$ ] and $N = c(101) + b(110) + 400 = 2(150) + 2(105) + c(101) + 110(b-1)$ [note $b>1$ ] respectively.

• for $10 - b- c = 5 \rightarrow (b+c)=5$ or equivalently ${b,c} = \{1,4\},\{2,3\},\{3,2\},\{4,1\}$ and correspondingly, $1014 = 9(101) + 105 ; 1023 = 3(101) + 4(105) + 2(150)$ $; 1032 = 2(101) + 2(150) +110 + 4(105) ; 1041 = 101 + 2(150) + 2(110) + 4(105)$ .

• for $10 - b- c = 8 \rightarrow (b+c)=2$ or equivalently ${b,c} = \{2,0\},\{0,2\},\{1,1\}$ and correspondingly, $1020 = 4(105) + 4(150) ; 1002 = 2(101) + 150 + 4(110) + 2(105)$ $; 1011 = 101 + 5(110) +150 + 2(105)$ .

• If $b> 5, c<5$ , we can write $N = 150 + c(101) + (b-5)(110) + (14-b-c)100$ & then proceed as before to prove for all. If $b< 5, c>5$ , we can write $N = 105 + (c-5)(101) + b(110) + (14-b-c)100$ & proceed as before. If $b> 5, c>5$ , we can write $N = 150 + 105 + (c-5)(101) + (b-5)(110) + (18-b-c)100$ & proceed as before.

Thus we have shown the above quadruple satisfies the requirements. Now we are left to show $3$ Brill notes are not enough.

Consider not. Let the 3 Brill notes be $a < b < c$ . Consider the Brill values from $1000$ to $11a+1$ . Any number among them $n$ must be expressible as $n= Xa + Yb + Zc$ , for $0 \leq X,Y,Z$ and $X + Y + Z < 11$ & for smaller values, strictly $X + Y + Z < 10$ . Since $a < b < c$ , & since no Brill note among the three can be of arbitrarily large value(or else the other two can satisfy it's use), we conclude $X + Y + Z > 7$ . So for $\{X,Y,Z\}$ , we have ${10 \choose 2} + {11 \choose 2} = 100$ choices (though actually choices in the specified range are much less), which cannot make up for 101 values. Thus $\boxed{4}$ is the minimum possible.

The following notes work: $\$100, \$101, \$110, \$111$ . The encoding for $\$N$ is:

Let $a = N \mod 100$ and divide $a$ by $10$ : $a = 10q + r$ .

Then if $q+r \le 10$ , $N = q \times \$110 + r \times \$101 + (10-q-r) \times \$100$

Otherwise if $q \ge r$ . $N = (q-r) \times \$110 + r \times \$111 + (10-q) \times \$100$

Otherwise $N = q \times \$111 + (r-q) \times \$101 + (10-r) \times \$100$

To prove that there is no solution with 3 notes we can proceed in a similar vein. Let the note values be $X < X+A < X+B$ . Then it is necessary (but perhaps not sufficient) to be able to represent all values $\mod X$ as $mA + nB$ where $m+n \le 10$ , where the $10$ comes from the fact that $10X \ge 1000$ so we need to be able to generate all values in the window $[10X, 11X)$ .

However there are only ${}^{12}C_2$ possible values of $m,n$ such that $m+n \le 10$ . This is less than the minimum values of $X$ which is 100, therefore there is no 3-note solution.

First of all we need to obtain 1000 B. A Brill note of 100 B could do that. Now we need the possibility of changing the units, eg a note of 101 B. With these two tipes we can create any value >1000 with 0 in the tens place. With a note of 110 B we could change the tens digit, but it's not enough for values like 1099 cause we can't reach that value changing either the tens or the units. A new note of 111 will do the job.

So the solution is 4: 100, 101, 110, 111 is a possibility.