2
$\begingroup$

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.

I can use LinearProgramming but that will give me the value that is satisfied by $Ax+By+Cz$ such that it is less than T. But I want to find the largest value which is less than T, but doesn't belong to $Ax+By+Cz$ for any value of x, y and z

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Linear programming won't help you one bit since everything is an integer. Can you solve the problem if $C = 0$? $\endgroup$
    – Yuval Filmus
    May 13 '13 at 2:07
  • $\begingroup$ @Yuval Filmus The constants A,B, C are greater than equal to 1 $\endgroup$
    – user77124
    May 13 '13 at 2:26
  • $\begingroup$ @YuvalFilmus. I can get a suboptimal solution though when I use LP that will be approximate of the true solution. But the main thing is I don't want to have the answer that satisfied Ax+By+Cz but the one that is largest but less than T and also isn't given by Ax+By+Cz for any integer value of x,y and z $\endgroup$
    – user77124
    May 13 '13 at 2:28
  • 2
    $\begingroup$ I suggest you first try to solve the easier $Ax+By$ case, which corresponds to $C=0$. Perhaps even start with $Ax$, i.e. $B=C=0$. That might help you solve the actual problem. $\endgroup$
    – Yuval Filmus
    May 13 '13 at 4:22
  • 1
    $\begingroup$ See this related problem on Math.SE $\endgroup$
    – Peter Shor
    Sep 16 '13 at 20:48

Your Answer

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

Browse other questions tagged or ask your own question.