Given A,B and n find the minimum value of Ax-By where x+y = n












-1












$begingroup$


Given $A$, $B$, $n$ we're interested in non negative values $Ax-By$, where $A,B,n$ $in$ $mathbb Z$, n $le$ $10^5$, $A+B=n$
and the value of the equation is minimized in case of multiple possible values of $x,y$



My idea is nothing but plain bruteforce, checking each values from $i$ to $n$ and $n-i$,thus finding minimum value.



For example:



$A=5,B=6$



$6*5 - 4*6 = 6$



Need some efficient ideas. Thanks in advance.










share|cite|improve this question











$endgroup$












  • $begingroup$
    are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
    $endgroup$
    – gt6989b
    Jan 9 at 4:59












  • $begingroup$
    yes A,B>0 and x,y are integers as well.
    $endgroup$
    – some user
    Jan 9 at 5:06










  • $begingroup$
    the actual value should be minimized
    $endgroup$
    – some user
    Jan 9 at 10:47










  • $begingroup$
    Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
    $endgroup$
    – Peter
    Jan 9 at 11:54












  • $begingroup$
    Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
    $endgroup$
    – Peter
    Jan 9 at 11:57


















-1












$begingroup$


Given $A$, $B$, $n$ we're interested in non negative values $Ax-By$, where $A,B,n$ $in$ $mathbb Z$, n $le$ $10^5$, $A+B=n$
and the value of the equation is minimized in case of multiple possible values of $x,y$



My idea is nothing but plain bruteforce, checking each values from $i$ to $n$ and $n-i$,thus finding minimum value.



For example:



$A=5,B=6$



$6*5 - 4*6 = 6$



Need some efficient ideas. Thanks in advance.










share|cite|improve this question











$endgroup$












  • $begingroup$
    are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
    $endgroup$
    – gt6989b
    Jan 9 at 4:59












  • $begingroup$
    yes A,B>0 and x,y are integers as well.
    $endgroup$
    – some user
    Jan 9 at 5:06










  • $begingroup$
    the actual value should be minimized
    $endgroup$
    – some user
    Jan 9 at 10:47










  • $begingroup$
    Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
    $endgroup$
    – Peter
    Jan 9 at 11:54












  • $begingroup$
    Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
    $endgroup$
    – Peter
    Jan 9 at 11:57
















-1












-1








-1





$begingroup$


Given $A$, $B$, $n$ we're interested in non negative values $Ax-By$, where $A,B,n$ $in$ $mathbb Z$, n $le$ $10^5$, $A+B=n$
and the value of the equation is minimized in case of multiple possible values of $x,y$



My idea is nothing but plain bruteforce, checking each values from $i$ to $n$ and $n-i$,thus finding minimum value.



For example:



$A=5,B=6$



$6*5 - 4*6 = 6$



Need some efficient ideas. Thanks in advance.










share|cite|improve this question











$endgroup$




Given $A$, $B$, $n$ we're interested in non negative values $Ax-By$, where $A,B,n$ $in$ $mathbb Z$, n $le$ $10^5$, $A+B=n$
and the value of the equation is minimized in case of multiple possible values of $x,y$



My idea is nothing but plain bruteforce, checking each values from $i$ to $n$ and $n-i$,thus finding minimum value.



For example:



$A=5,B=6$



$6*5 - 4*6 = 6$



Need some efficient ideas. Thanks in advance.







number-theory elementary-number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 9 at 11:19







some user

















asked Jan 9 at 4:38









some usersome user

32




32












  • $begingroup$
    are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
    $endgroup$
    – gt6989b
    Jan 9 at 4:59












  • $begingroup$
    yes A,B>0 and x,y are integers as well.
    $endgroup$
    – some user
    Jan 9 at 5:06










  • $begingroup$
    the actual value should be minimized
    $endgroup$
    – some user
    Jan 9 at 10:47










  • $begingroup$
    Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
    $endgroup$
    – Peter
    Jan 9 at 11:54












  • $begingroup$
    Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
    $endgroup$
    – Peter
    Jan 9 at 11:57




















  • $begingroup$
    are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
    $endgroup$
    – gt6989b
    Jan 9 at 4:59












  • $begingroup$
    yes A,B>0 and x,y are integers as well.
    $endgroup$
    – some user
    Jan 9 at 5:06










  • $begingroup$
    the actual value should be minimized
    $endgroup$
    – some user
    Jan 9 at 10:47










  • $begingroup$
    Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
    $endgroup$
    – Peter
    Jan 9 at 11:54












  • $begingroup$
    Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
    $endgroup$
    – Peter
    Jan 9 at 11:57


















$begingroup$
are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
$endgroup$
– gt6989b
Jan 9 at 4:59






$begingroup$
are you assuming $A,B>0$? are $x,y in mathbb{R}$ or are they integers?
$endgroup$
– gt6989b
Jan 9 at 4:59














$begingroup$
yes A,B>0 and x,y are integers as well.
$endgroup$
– some user
Jan 9 at 5:06




$begingroup$
yes A,B>0 and x,y are integers as well.
$endgroup$
– some user
Jan 9 at 5:06












$begingroup$
the actual value should be minimized
$endgroup$
– some user
Jan 9 at 10:47




$begingroup$
the actual value should be minimized
$endgroup$
– some user
Jan 9 at 10:47












$begingroup$
Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
$endgroup$
– Peter
Jan 9 at 11:54






$begingroup$
Sorry, I overlooked that you clarified that $Ax-By$ should be non-negative, so it boils down to minimize $|Ax-By|$
$endgroup$
– Peter
Jan 9 at 11:54














$begingroup$
Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
$endgroup$
– Peter
Jan 9 at 11:57






$begingroup$
Did you try to minimize the expression $$|A(n-y)+By|=|An-(A-B)y|$$ which we get by inserting $x=n-y$ ?
$endgroup$
– Peter
Jan 9 at 11:57












1 Answer
1






active

oldest

votes


















1












$begingroup$

$y=n-x$ and you minimize $$Ax-B(n-x)=(A+B)x-Bn.$$



All values taken by this expression differ in multiples of $A+B$, and the smallest positive value is



$$(-Bn)bmod(A+B),$$ which is in $[0,A+B)$.





UPDATE:



The conditions in the title and in the body define completely different problems !






share|cite|improve this answer











$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067075%2fgiven-a-b-and-n-find-the-minimum-value-of-ax-by-where-xy-n%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












    $begingroup$

    $y=n-x$ and you minimize $$Ax-B(n-x)=(A+B)x-Bn.$$



    All values taken by this expression differ in multiples of $A+B$, and the smallest positive value is



    $$(-Bn)bmod(A+B),$$ which is in $[0,A+B)$.





    UPDATE:



    The conditions in the title and in the body define completely different problems !






    share|cite|improve this answer











    $endgroup$


















      1












      $begingroup$

      $y=n-x$ and you minimize $$Ax-B(n-x)=(A+B)x-Bn.$$



      All values taken by this expression differ in multiples of $A+B$, and the smallest positive value is



      $$(-Bn)bmod(A+B),$$ which is in $[0,A+B)$.





      UPDATE:



      The conditions in the title and in the body define completely different problems !






      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $begingroup$

        $y=n-x$ and you minimize $$Ax-B(n-x)=(A+B)x-Bn.$$



        All values taken by this expression differ in multiples of $A+B$, and the smallest positive value is



        $$(-Bn)bmod(A+B),$$ which is in $[0,A+B)$.





        UPDATE:



        The conditions in the title and in the body define completely different problems !






        share|cite|improve this answer











        $endgroup$



        $y=n-x$ and you minimize $$Ax-B(n-x)=(A+B)x-Bn.$$



        All values taken by this expression differ in multiples of $A+B$, and the smallest positive value is



        $$(-Bn)bmod(A+B),$$ which is in $[0,A+B)$.





        UPDATE:



        The conditions in the title and in the body define completely different problems !







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 9 at 12:49

























        answered Jan 9 at 12:41









        Yves DaoustYves Daoust

        128k675227




        128k675227






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067075%2fgiven-a-b-and-n-find-the-minimum-value-of-ax-by-where-xy-n%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Human spaceflight

            Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

            張江高科駅