In how many ways can change be made for
$210 using any combination of $5, $10,
and $20 bills? You do not have to use each
of the three types of bills simultaneously.

Question

In how many ways can change be made for
$210 using any combination of $5, $10,
and $20 bills? You do not have to use each
of the three types of bills simultaneously.

perl · Answer

Let
x = # 5 dollar bills
y = # 10 dollar bills
z = # 20 dollar bills

You want to find integer (nonnegative) solutions to 

5x + 10y + 20z = 210

anonymous · Answer

how do i find the integer?

perl · Answer

there might be a trick, but it looks like trial and error, here are some solutions on wolfram http://www.wolframalpha.com/input/?i=solve+5x+%2B+10y+%2B+20z+%3D+210%2C+x%3E%3D0%2C+y%3E%3D0%2C+z%3E%3D0%2C+over+the+integers

anonymous · Answer

i got  x=-2y-4z+42 i dont think thats right

perl · Answer

that is solving for x.

mathstudent55 · Answer

Use a spreadsheet, and do trial and error.

perl · Answer

you can write a program that finds the number of solutions

perl · Answer

@ganeshie8  do you want to take a look at this, if theres some trick we can use

ganeshie8 · Answer

$5x + 10y + 20z = 210 $

dividing 5 through out we get
$x + 2y + 4z = 42$
sending 4z to the other side :
$$x + 2y = 42-4z\tag{1}$$

Notice that $(-1, 1)$ is a solution to  $x+2y = 1$
so the equation $(1)$ parameterizes  to :
$$(x,y,z) = (2t+4z-42,~ -t-4z+42,~z)$$
where $t$ is any integer

ganeshie8 · Answer

$x\ge 0 , y\ge 0  \implies $    $$  21-2z\le t \le 2(21-2z)$$

Clearly solutions exist only when $0\le z\le 10$ : 

$$
z = 0 :  21\le t\le 42 \implies \text{22 solutions} \
z = 1 :  19 \le t\le 38 \implies \text{20 solutions} \
z = 2 :  17 \le t\le 34 \implies \text{18 solutions} \~\~\
\ldots \~\~\
z = 10 :  1 \le t\le 2 \implies \text{2 solutions} \

$$

ganeshie8 · Answer

Add up all the solutions : 
$2 + 4 + 6 + \cdots + 22 = \sum\limits_{n=1}^{11}2n =  132$

ganeshie8 · Answer

another way to work it is by fixing a z value and simply counting the non negative integer solutions to the equation : `x + 2y = 42-4z`

perl · Answer

ok so your first method is solving a three variable linear diophantine equation http://math.stackexchange.com/questions/20906/how-to-find-an-integer-solution-for-general-diophantine-equation-ax-by-cz

ganeshie8 · Answer

Exactly!

perl · Answer

the second method is brute force.

ganeshie8 · Answer

kindof but we can make it less brute force by figuring out a formula for number of nonnegative integer solutions to equaiton : 
$$x + 2y = k$$

ganeshie8 · Answer

$$x=k-2y $$
that means $0 \le y \le \lfloor\frac{k}{2}\rfloor $
so total number of integer solutions is   $\lfloor\frac{k}{2}\rfloor + 1$

ganeshie8 · Answer

so the toal number of nonnegative integer solutions to $x+2y = 42-4z$ is given by
$$\sum\limits_{z=0}^{10} \lfloor \frac{42-4z}{2} \rfloor + 1 = \sum\limits_{z=0}^{10} 22-2z  $$

ganeshie8 · Answer

http://www.wolframalpha.com/input/?i=+%5Csum%5Climits_%7Bz%3D0%7D%5E%7B10%7D+%2822-2z%29 im beginning to like the second method more xD

perl · Answer

i will try to write a program for this, just for fun :)

mathstudent55 · Answer

I wrote a program. There are 132 combinations.

mathstudent55 · Answer

5 counter = 0
10 for i = 0 to 42
20    for j = 0 to 21
30       for k = 0 to 11
40           sum = 5*i + 10*j + 20*k
50           if sum = 210 then counter = counter + 1                 
60       next k
70    next j
80 next i
90 print counter

anonymous · Answer

well its a little too late now XD i turned it in but thanks for the reply