Best way to find possible arrangements of N values given N and average value?

Question

For example, say I have a pile of X checks, which can have one of a known set of costs. The average value of the checks in the pile is Y. How can I find the possible arrangements (number of checks with each known cost where a total of X checks would average Y)?

This is similar to the problem of "You have $1.34 in change and 8 coins, what coins do you have". What's the best way to solve this? (I have large X and Y.)

Answer 1

To me this sounds like a diophantine equation.

Let the set of "costs" be {x1,x2,...xn}

Let the quantity of the "checks" with that "cost" take on a variable value, say y's

then we have (y1x1+y2x2+...+ynxn)/n = average

to be precise,

y1*1+y2*5+y3*10+y4*25=134

y1+y2+y3+y4=8

things like this are tough to solve because you only have integers to deal with and not all numbers, also you only have two equations with 4 variables. Go to wikipedia or mathworld and check out diophantine equations

Answer 2

http://www.youtube.com/watch?v=yJEe3hlRSE4

Sheep?