Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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...) –  anorton Dec 5 '12 at 21:34
    
Yes x's are unknowns. –  mikey Dec 5 '12 at 21:35
2  
I would suggest first trying it out for two numbers. –  EuYu Dec 5 '12 at 21:47
1  
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

2 Answers 2

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.