I just noticed that audiobottle’s solution also uses only 11 bills.
Anyway, I’ve come up with a solution that’s good enough for a physicist. : )
Take the equations I found above, but with i, j, and k defined to be positive (I leave working out all the signs as an exercise for the reader):
d= 2 + 5 i
c = 1 - i + 2 j
b = 2 k - j
a = 8 - k
Plug these in to the equation a + b + c + d = 30 to get
4 i + j + k = 19
From this, we can derive an extra constraint from the requirement that i, j , and k be positive integers, using the same method as above:
i = (19 - j - k ) / 4
i = (16 + 3 - j - k) /4
i = 4 + (3 - j - k ) / 4
Since (3 - j - k) mod 4 must be zero, this gives us i <= 4. Notice also that the equation a = 8 - k gives us k <= 8.
Now, substitute j = 19 - 4 i - k in the equations above:
a = 8 - k
b = 3 k + 4 i -19
c = 39 - 9 i - 2 k
d = 2 + 5 i
Now we have just two variables: i & k , and we know the possible ranges for these, so I just wrote a little computer program to step through the values for i and k, and reject anything that yeilds a negative number for a, b, c, or d. (This is IDL, but the code is quite simple).
for i=0,4 do begin
for k=0,8 do begin
a=8-k
b=3k-19+4i
c=39 - 9i -2k
d=2+5*i
if ((a ge 0) and (b ge 0) and (c ge 0) and (d ge 0)) then print, a," Twenties, ", b, " Tens, ", c, " Fives, ",d, " Ones "
endfor
endfor
Here are the results:
1 Twenties, 2 Tens, 25 Fives, 2 Ones
0 Twenties, 5 Tens, 23 Fives, 2 Ones
3 Twenties, 0 Tens, 20 Fives, 7 Ones
2 Twenties, 3 Tens, 18 Fives, 7 Ones
1 Twenties, 6 Tens, 16 Fives, 7 Ones
0 Twenties, 9 Tens, 14 Fives, 7 Ones
4 Twenties, 1 Tens, 13 Fives, 12 Ones
3 Twenties, 4 Tens, 11 Fives, 12 Ones
2 Twenties, 7 Tens, 9 Fives, 12 Ones
1 Twenties, 10 Tens, 7 Fives, 12 Ones
0 Twenties, 13 Tens, 5 Fives, 12 Ones
5 Twenties, 2 Tens, 6 Fives, 17 Ones
4 Twenties, 5 Tens, 4 Fives, 17 Ones
3 Twenties, 8 Tens, 2 Fives, 17 Ones
2 Twenties, 11 Tens, 0 Fives, 17 Ones
7 Twenties, 0 Tens, 1 Fives, 22 Ones
Let me know if I’ve missed any.