# A fun little problem

Let's say I have a set of non-negative integers $a_1,..,a_n$ and a number $C$ which is a non-negative constant (an integer).

Consider an equation

$x_1\cdot a_1 + x_2\cdot a_2 + ... + x_n\cdot a_n - C = 0$

where $x_1,...,x_n$ are unknown non-negative integers. I have to say whether a solution to this equation exists, and when does it exist and when does it not exist.

I'd really appreciate anyone's help I've been struggling with this one for quite a while.

EDIT
Well so far i haven't made a good progress, i'm going to sleep and see you all in the morning.So far i got two conclusion. 1.) if the number C is not divisible by the gcd of the set than there certainly is no solution 2.)If C is divisble by gcd, If we divide all the numbers by the gcd than it becomes Frobenius coin problem.I'm now looking into upper bounds for FCP.See you all in the morning.

-
I forgot to mention that all the numbers in the Set, along with C are non negative integers. – mikey Dec 5 '12 at 21:28
And the $x_i$ are unknown? (Just confirming...) – apnorton Dec 5 '12 at 21:34
Yes x's are unknowns. – mikey Dec 5 '12 at 21:35
I would suggest first trying it out for two numbers. – EuYu Dec 5 '12 at 21:47
I give one hint. The umbrella concept is numerical semigroup. It seems to me that in general the full answer is not known (or at least difficult to express), but I may be wrong. Because all the variables must be non-negative it is not just about gcd. – Jyrki Lahtonen Dec 5 '12 at 21:50

This way is really inefficient for a large number of variables, but Integer Programming is a built-in feature in most scientific computation software these days.

Try to find whether this Integer Program has a solution

$$\mathbf{min} \sum_ix_i$$ $$s.t. \sum_i a_i x_i = C$$ $$x_i \geq0$$ where all $x_i$ are integers. This will give you a dirty but easy answer.

Note: The objective function $\sum x_i$ is just a placeholder. It can be replaced by any other increasing function. If the software supports it, even $\mathbf{min}\mbox{ } 0$ is fine. Thanks to Jacob for pointing it out.

-
You don't need to minimize anything. The OP is merely asking for a feasible solution to your problem. Also $x_i \ge 0$. – Jacob Dec 5 '12 at 22:26
@Jacob: An IP must have an objective function to minimize. Before solving, all solvers check whether it is feasible or not. So, I have put a dummy objective fn – dexter04 Dec 5 '12 at 22:29
Not really. $\text{minimize } 0$ is fine. – Jacob Dec 5 '12 at 22:29
yeah. that is fine. I was just trying to formulate it as an IP. – dexter04 Dec 5 '12 at 22:33

Solve it as a knapsack problem. $a_i$ is your weight, $x_i$ is the quantity of each item and set the "value" for each $x_i$ as 1. $C$ is the total weight your knapsack can carry. If you do find a solution, check if the total "weight" is equal to $C$ ; then you have a solution.

-