Exchange € 100

Find out how many ways you can exchange € 100 if you have an unlimited number of 50, 20, 10, and 5 euro banknotes. Use a method other than listing all options systematically.

Correct answer:

n = 49

Step-by-step explanation:

100=50a+20b+10c+5d

a1=0, b1=0, c1=0, d1=20
a2=0, b2=0, c2=1, d2=18
a3=0, b3=0, c3=2, d3=16
a4=0, b4=0, c4=3, d4=14
a5=0, b5=0, c5=4, d5=12
a6=0, b6=0, c6=5, d6=10
a7=0, b7=0, c7=6, d7=8
a8=0, b8=0, c8=7, d8=6
a9=0, b9=0, c9=8, d9=4
a10=0, b10=0, c10=9, d10=2
a11=0, b11=0, c11=10, d11=0
a12=0, b12=1, c12=0, d12=16
a13=0, b13=1, c13=1, d13=14
a14=0, b14=1, c14=2, d14=12
a15=0, b15=1, c15=3, d15=10
a16=0, b16=1, c16=4, d16=8
a17=0, b17=1, c17=5, d17=6
a18=0, b18=1, c18=6, d18=4
a19=0, b19=1, c19=7, d19=2
a20=0, b20=1, c20=8, d20=0
a21=0, b21=2, c21=0, d21=12
a22=0, b22=2, c22=1, d22=10
a23=0, b23=2, c23=2, d23=8
a24=0, b24=2, c24=3, d24=6
a25=0, b25=2, c25=4, d25=4
a26=0, b26=2, c26=5, d26=2
a27=0, b27=2, c27=6, d27=0
a28=0, b28=3, c28=0, d28=8
a29=0, b29=3, c29=1, d29=6
a30=0, b30=3, c30=2, d30=4
a31=0, b31=3, c31=3, d31=2
a32=0, b32=3, c32=4, d32=0
a33=0, b33=4, c33=0, d33=4
a34=0, b34=4, c34=1, d34=2
a35=0, b35=4, c35=2, d35=0
a36=0, b36=5, c36=0, d36=0
a37=1, b37=0, c37=0, d37=10
a38=1, b38=0, c38=1, d38=8
a39=1, b39=0, c39=2, d39=6
a40=1, b40=0, c40=3, d40=4
a41=1, b41=0, c41=4, d41=2
a42=1, b42=0, c42=5, d42=0
a43=1, b43=1, c43=0, d43=6
a44=1, b44=1, c44=1, d44=4
a45=1, b45=1, c45=2, d45=2
a46=1, b46=1, c46=3, d46=0
a47=1, b47=2, c47=0, d47=2
a48=1, b48=2, c48=1, d48=0
a49=2, b49=0, c49=0, d49=0