Oops! No dollar bills!

To minimize the amount of change, consider maximizing low-costing coins first. If the number of pennies is greater than or equal to 5, 5 of them can be replaced with a nickel. Therefore, the maximum number of pennies can be 4.

Now the coins to consider are nickels, dimes, and quarters. If the number of nickels is greater than or equal to 2, 2 of them can be replaced with a dime. Therefore, the maximum number of nickels can be 1.

When considering dimes, we need to be a bit more careful. It seems that it is possible to have 2 dimes, but if there is 1 nickel, then these can be replaced with a quarter. Without the nickel, the maximum number of dimes is 2 (3 dimes can be replaced with a nickel and a quarter). The first option minimizes the cost: 1 nickel and 1 dime are better than 2 dimes. Clearly, the remaining coins must be quarters.

So the first 6 coins are 4 pennies, a nickel, and a dime, which is 19 cents. The rest are quarters. A general formula for $c$ coins where $c \ge 6$ would be $(c-6)*25+19$ . Plugging in 20, we get our answer of $369$ cents or $\$3.69.$

Let $p$ , $n$ , $d$ , $q$ be the numbers of pennies, nickels, dimes, and quarters; and $N = p + n + d + q$ the total number of coins.

As long as $p \geq 5$ , we can replace five pennies by one nickel, reducing $N$ by four. Therefore in a minimum number of coins situation, $p \leq 4.$ As long as $n \geq 2$ , we can replace two nickels by one dime, reducing $N$ by one. Thus $n \leq 1.$ As long as $d \geq 3$ , we can replace three dimes by a quarter and a nickel, reducing $N$ by one. Thus $d \leq 2.$ Finally, if after all this $n + d = 3$ (that is, $n = 1$ and $d = 2$ ), two dimes and a nickel may be exchanged for a quarter, reducing $N$ by two. Therefore $n + d \leq 2.$

Within these constraints we want to maximize $p$ , then $n$ , then $d$ . Thus we choose $p = 4, n = 1, d = 1, q = N - 6,$ and the amount in cents is $4\cdot 1 + 1\cdot 5 + 1\cdot 10 + (N-6)\cdot 25 = 25(N-6) + 19.$ In the case of $N = 20$ this results in $25\cdot 14 + 19 = \boxed{369}.$

It should be clear that the goal is to have the most number of small coins as possible.

4 pennies is the most amount of pennies you can have, since 5 pennies would turn into 1 nickel. 1 nickel is the most amount of nickels you can have, since 2 nickels is a dime. 2 dimes is the most amount of dimes you can have. Having more than two will either have a same number or less coins when replacing dimes and/or nickels with quarters. You cannot simultaneously have two dimes and one nickle, otherwise you'll have a quarter.

So you can have 4 pennies, 1 nickel, 1 dime. All other coins must be quarters.

If there are 20 coins, then 14 must be quarters, 1 nickel, 1 dime, and 4 pennies. This leaves $3.69 as the minimum that can be provided with 20 coins.

It's also clear from this that for any number of coins greater than six, you must only use quarters. So the general formula for N coins is (N - 6) quarters, 4 pennies, 1 nickel, and 1 dime.

python bruteforce solution :)

although it is clear that we need to maximize the no. small value coins up to the point before they reach the next coin class to have the minimum value of coins overall

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

coin_v = [25,10,5,1]
coin_c = [0,0,0,0]
for i in range(1000):
    tsum=i
    csum=0
    for idx,coin in enumerate(coin_v):
        if tsum//coin>0:
            coin_c[idx]=tsum//coin
            csum+=coin_c[idx]
            tsum-=(tsum//coin)*coin
    if csum==20:
        print(i)
        print ( list( zip(coin_c,coin_v) ) )
        break

What if you had $4$ pennies, no nickels, $4$ dimes, and $12$ quarters? It never said you couldn’t have no nickels. This would make $4+40+300=344$ . This is better than $369$ .

Just for fun! This works for any denominations and any n. The for loop can be simplified but I have a weak spot for zip 😇

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def min_change(n, denoms=[1,5,10,25]):
  change = 0

  # d1, d2 <- ((1,5), (5,10), (10,25))
  for d1, d2 in zip(denoms, denoms[1:]):
    coins = min(n, (d2-change-1)//d1)
    change += d1*coins
    n -= coins

return change + n*denoms[-1]

A program in python 3 to solve this as follows:

valQuarters = 25

valDimes = 10

valNickels = 5

valPennies = 1

numCoins = 20

change=100 # start with a minimal initial guess

notFinish=True

while(notFinish):

q = change // valQuarters

d = (change - valQuarters * q) // valDimes

n = (change - valQuarters * q - valDimes * d) // valNickels

p = (change - valQuarters * q - valDimes * d - valNickels * n)

change+=1

if q + d + n + p == numCoins:

    print("q =",q,"d =",d,"n =",n,"p =",p)

    print("minimum possible value =",q * valQuarters + d * valDimes + n * valNickels + p * valPennies )

    notFinish=False

A bashy approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

denominations = sorted([25,10,5,1], reverse = True)

def min_change(n):
    s = 0
    while n > 0:
        for coin in denominations:
            if n > 0:
                s += int(n/coin)
                n -= coin*int(n/coin)
    return s

found = False
n = 1
while found == False:
    if min_change(n) == 20:
        print(n)
        found = True
    else:
        n += 1

Python 3 solution below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

amt_const = int(0.01 * 100)
 #amount in Dollars to start with
amt = amt_const
coins_25 = 0
coins_10 = 0
coins_5  = 0
coins_1  = 0
coin_count = 20      
 # total coins disbursed
coins = 0

while(True):

    print("-----------------------------------------------------------")
    if(amt >= 25):
        coins_25 += int(amt / 25)
        amt -= coins_25 * 25
        coins += coins_25
        print("Coins(25): {:d} & Amount: {:d}" .format(coins_25, amt))

    if(amt >= 10 and amt < 25):
        coins_10 += int(amt / 10)
        amt -= coins_10 * 10
        coins += coins_10
        print("Coins(10): {:d} & Amount: {:d}" .format(coins_10, amt))

    if(amt >= 5 and amt < 10):
        coins_5 += int(amt / 5)
        amt -= coins_5 * 5
        coins += coins_5
        print("Coins(5): {:d} & Amount: {:d}" .format(coins_5, amt))

    if(amt >= 1 and amt < 5):
        coins_1 += int(amt / 1)
        amt -= coins_1 * 1
        coins += coins_1
        print("Coins(1): {:d} & Amount: {:d}" .format(coins_1, amt))

    if(coins == coin_count):
        print("The Amount is: {:d}" .format(amt_const))
        coins = coins_25 + coins_10 + coins_5 + coins_1
        print("Total coins: {:d}" .format(coins))
        break

    if(amt == 0 and coins <= 20):
        print("Did not find 20 coins with amount: {:d}" .format(amt_const))
        coins = coins_25 + coins_10 + coins_5 + coins_1
        print("Total coins: {:d}" .format(coins))
        amt = amt_const + 1
        amt_const = amt
        coins_25 = 0
        coins_10 = 0
        coins_5  = 0
        coins_1  = 0
        coins    = 0
    print("-----------------------------------------------------------") 

Let $x_0$ , $x_1$ , $x_2$ , and $x_3$ be the number of coins for $25$ cents, $10$ cents, $5$ cents and $1$ cent respectively. First, I initialize that the value is equal to the total number of coins. So, in this case, the inilization value is $20$ . Define $v_0=20$ , and

1. $x_0=\lfloor\frac{v_0}{25}\rfloor, v_1=v_0\bmod25$
2. $x_1=\lfloor\frac{v_1}{10}\rfloor, v_2=v_1\bmod10$
3. $x_2=\lfloor\frac{v_2}{5}\rfloor, v_3=v_2\bmod5$
4. $x_3=\lfloor\frac{v_3}{1}\rfloor$

If $\displaystyle\sum_{i=0}^3x_i \neq 20$ , then add one to $v_0$ and repeat from the $1^{st}$ step. Otherwise, that is $\displaystyle\sum_{i=0}^3x_i = 20$ , we get $v_0$ which is the minimum value of $20$ coins.

Here is my code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

coins=20
cent=[25,10,5,1]
value=coins
x=[0,0,0,0]
while True:
    i=0
    v=value
    for c in cent:
        x[i]=v//c
        v=v%c
        i=i+1
    if sum(x)==coins
        print(value)
        break
    value=value+1

for num in range(1000): n = num x = 0 while n >= 25: n = n - 25 x = x + 1 else: while n >= 10: n = n - 10 x = x + 1 else: while n >= 5: n = n - 5 x = x + 1 else: while n >= 1: n = n - 1 x = x + 1 else: if x == 20: print (num)

So if anyone would like to use code to solve this problem, I found this page on how to use dynamic programming to find the minimum coins needed for a given amount of change on interactivepython.org, which helped me find the minimum number of coins for a given amount of change. I simply added a while loop to get the first instance of change requiring a minimum of 20 coins.

If you're at all interested in learning about dynamic programming, I'd recommend checking that page out.

I realize now that this would've been much easier to solve by thinking about it rather than coding, but finding a code solution was still fun.

Here's my code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#!/usr/bin/env python3

def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
   for cents in range(change+1):
      coinCount = cents
      newCoin = 1
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
               newCoin = j
      minCoins[cents] = coinCount
      coinsUsed[cents] = newCoin
   return minCoins[change]

def printCoins(coinsUsed,change):
   coin = change
   while coin > 0:
      thisCoin = coinsUsed[coin]
      print(thisCoin)
      coin = coin - thisCoin

def main():
    coins = 0
    amnt = 0
    while coins < 20:
        amnt += 1
        clist = [1,5,10,25]
        coinsUsed = [0]*(amnt+1)
        coinCount = [0]*(amnt+1)

        print("Making change for",amnt,"requires")
        coins = dpMakeChange(clist,amnt,coinCount,coinsUsed)
        print(coins,"coins")

main()

If number is less 25, we can use no more than 6 coins for 19 and 24. If more than 25, use 25 cent coins until it is less. So 14 25-cents and 19 cents with 10,5,1,1,1,1.

I was under the assumption that you wanted to write a program to find the solution to the above problem, so I wrote a program in Free Pascal since it's what I had available.

I wrote a program for the general case. I.E; I wrote a program given $n$ denominations of coins $c_{1}, c_{2}, ..., c_{n}$ each having a value $v_{n}$ . The program outputs the minimum possible value of the change in cents.

program demonstration;

type arraytype = array[0 .. 100] of longint;

var coin,value,m:arraytype;

numcoins,total:longint;

procedure getinput; {general case}

var j:longint;

begin

writeln('Enter number of denominations');

readln(numcoins);

writeln('Enter total number of coins to be given as change');

readln(total);

writeln('Enter the value of each coin in decreasing order');

for j:= 1 to numcoins do

begin

read(value[j]);

end;

end;

procedure switch(var x,y:longint);

var temp:longint;

begin

temp:= x;

x:= y;

y:= temp;

end;

procedure arrange;

{In case input was not entered in decreasing order.}

var j,k:longint;

begin

for j:= 1 to (numcoins - 1) do

begin

for k:= j to numcoins do

begin

if value[j] < value[k] then

switch(value[j],value[k]);

end;

end;

end;

procedure general_amount;

var s,sum,j:longint;

begin

s:= 0;

repeat

s:= s + 1;

m[0]:= s;

for j:= 1 to numcoins do

begin

coin[j]:= m[j - 1] div value[j];

m[j]:= m[j - 1] - value[j] * coin[j];

end;

sum:= 0;

for j:= 1 to numcoins do

begin

sum:= sum + coin[j];

end;

until(sum = total);

writeln(s);

end;

begin

getinput;

writeln;

arrange;

general_amount;

readln;

end.

Running the above program we obtain $\boxed{369}$ .

We only need to analyze the 25 cases in the table--from 15 cents to 39 cents--because the next 25 cases (40~64 cents) are each only 1 quarter more than what's in the table, the next 25 cases (65~89 cents) are each 2 quarters more, and so on.

In the "Total # of coins" column of the table, we see a clear pattern: $2 3 4 5 6 \hspace{0.5cm} 2 3 4 5 6 \hspace{0.5cm} 1 2 3 4 5 \hspace{0.5cm} 2 3 4 5 6 \hspace{0.5cm} 2 3 4 5 6,$ where the hightest number 6 appears four times and the first 6 corresponds to a change of 19 cents. Also, note that the smallest number, 1, $($ which is $\bf\color{#3D99F6}5$ less than the greatest number $)$ corresponds to a change of 25 cents $($ which is $\bf\color{#20A900}6$ cents more than the 19 cents $).$ Therefore, as indicated above, the $14^\text{th}$ from this pattern would be a pattern with only 14 more on each number: $16\ 17\ 18\ 19\ 20 \hspace{0.5cm}16\ 17\ 18\ 19\ 20 \hspace{0.5cm} 15\ 16\ 17\ 18\ 19 \hspace{0.5cm} 16\ 17\ 18\ 19\ 20 \hspace{0.5cm} 16\ 17\ 18\ 19\ 20.$ Since the smallest number, 15, corresponds to $15\times 25=375$ cents, the smallest change corresponding to 20 coins is $375-6=369$ cents.

In general, given $n\,(\ge 6)$ coins, the formula for the minimum possible value of the change in cents is $(n-{\bf\color{#3D99F6}5}) \times 25 -{\bf\color{#20A900}6}.\ _\square$