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.

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.

  • $\begingroup$ I forgot to mention that all the numbers in the Set, along with C are non negative integers. $\endgroup$ – mikey Dec 5 '12 at 21:28
  • $\begingroup$ And the $x_i$ are unknown? (Just confirming...) $\endgroup$ – apnorton Dec 5 '12 at 21:34
  • $\begingroup$ Yes x's are unknowns. $\endgroup$ – mikey Dec 5 '12 at 21:35
  • 2
    $\begingroup$ I would suggest first trying it out for two numbers. $\endgroup$ – EuYu Dec 5 '12 at 21:47
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ You don't need to minimize anything. The OP is merely asking for a feasible solution to your problem. Also $x_i \ge 0$. $\endgroup$ – Jacob Dec 5 '12 at 22:26
  • $\begingroup$ @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 $\endgroup$ – dexter04 Dec 5 '12 at 22:29
  • $\begingroup$ Not really. $\text{minimize } 0$ is fine. $\endgroup$ – Jacob Dec 5 '12 at 22:29
  • $\begingroup$ yeah. that is fine. I was just trying to formulate it as an IP. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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