Question

How can you give someone $83 using exactly 7 bills, without using any one dollar bills?

Answer 1

Aside from $ 1 bills, there are bills of the following denominations less than 100 : 2 , 5 , 10 , 20 , 50 . So we wish to solve the equation

 

50x1+20x2+10x3+5x4+2x5=83…(1) 

 

subject to

 

x1+x2+x3+x4+x5=7 , xi≥0 , 1≤i≤5 .

 

From eqn, (1) , we have 2x5≡−2(mod5) , so that x5≡4(mod5) . The constraints on the xi ’s imply xi≤7 for 1≤i≤5 . Thus, x5=4 , and we are left with the reduced equation

 

10x1+4x2+2x3+x4=15…(2) 

 

subject to

 

x1+x2+x3+x4=3 , xi≥0 , 1≤i≤4 .

 

From eqn, (2) , we have x4≡1(mod2) . The constraints on the xi ’s imply xi≤3 for 1≤i≤4 . Thus, x4∈{1,3} , and we can eliminate x4=3 since that would imply x1=x2=x3=0 . Hence x4=1 , and we are left with the reduced equation

 

5x1+2x2+x3=7…(3) 

 

subject to

 

x1+x2+x3=2 , xi≥0 , 1≤i≤3 .

 

It is now easy to see that x1=1 , x2=1 , x3=0 is a solution. Putting it all together, we have one $ 50 , one $ 20 , one $ 5 , and four $ 2 bills. 

 

 

see above solution