1
$\begingroup$

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.

  • 0
    I forgot to mention that all the numbers in the Set, along with C are non negative integers.2012-12-05
  • 0
    And the $x_i$ are unknown? (Just confirming...)2012-12-05
  • 0
    Yes x's are unknowns.2012-12-05
  • 0
    mikey: While formatting your question, I added the "non-negative" qualifications for the $a_i$ and $C$, okay?2012-12-05
  • 0
    Yeah, thanks for that.2012-12-05
  • 0
    How much help do you want us to give you here? I could tell you the answer, but you wouldn't learn very much...2012-12-05
  • 0
    Well, some hint would be nice, like what was your train of thought while solving it... what did you look at first etc etc... This problem is due in tuesday so i've got time no probs :)2012-12-05
  • 2
    I would suggest first trying it out for two numbers.2012-12-05
  • 1
    I give one hint. The umbrella concept is [numerical semigroup](http://en.wikipedia.org/wiki/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.2012-12-05
  • 0
    Ok, here's a hint: what happens if all the $a_i$ are even? What if they're all multiples of $3$, or $6$, or $k$ for any integer $k$ you like? Under what conditions can you find a solution? Then start considering small cases (two variables, like EuYu suggests, or maybe three) that aren't so simple, and see when you can find solutions2012-12-05
  • 0
    For an example see [this question](http://math.stackexchange.com/q/69961/11619), where the case $n=2$, $a_1=3$, $a_2=5$ is analyzed in detail.2012-12-05
  • 0
    looks very like a projection of position vector onto a normal vector to N dimentional surface, beying C it's "distance" to the origin2012-12-05
  • 0
    A dynamic programming solution (based on knapsack) would work2012-12-07
  • 0
    Will dynamic programming give definitive answers of the type *If the numbers $a_i$ have no common divisors, then all sufficiently large $C$ can be written in this form*?2012-12-07

2 Answers 2