Are there basic weighing puzzles requiring adaptive strategies?












1












$begingroup$


Let us define a basic weighing puzzle as such:




  • There are <number> identical balls, except one weighs <more/less/a different amount than the others>

  • A balance scale may be used to weigh two subsets of the balls, giving <information about comparative weight>

  • The goal is to determine which ball weighs a different weight in <number> weighings <and optionally whether it weighs more or less if that isn't known>


For example, one such puzzle is:




  • There are 12 identical balls, except one weighs a different amount than the others

  • A balance scale may be used to weigh two subsets of the balls, giving either which subset is heavier or that both subsets weigh the same amount

  • The goal is to determine which ball weighs a different weight in 3 weighings and whether it weighs more or less


Now, the first answer gives a strategy conditional on what each weighing comes out as. The second answer, however, gives a strategy without branching: before knowing the results of any weighing we can determine what all (three) weighings will be.



In my limited experience with 'basic' weighing puzzles, I've never come across one where branching is necessary. So my question is:




Does there exist a basic weighing puzzle which requires some sort of branching: where a fixed strategy of weighings cannot be determined in advance?




Secondary questions (not necessary to answer but I would be curious to know if it's easy to prove):




  • If so, what are some necessary / sufficient conditions?

  • If not, what generalisations of a basic weighing puzzle make branching necessary / also do not require branching?










share|improve this question









$endgroup$

















    1












    $begingroup$


    Let us define a basic weighing puzzle as such:




    • There are <number> identical balls, except one weighs <more/less/a different amount than the others>

    • A balance scale may be used to weigh two subsets of the balls, giving <information about comparative weight>

    • The goal is to determine which ball weighs a different weight in <number> weighings <and optionally whether it weighs more or less if that isn't known>


    For example, one such puzzle is:




    • There are 12 identical balls, except one weighs a different amount than the others

    • A balance scale may be used to weigh two subsets of the balls, giving either which subset is heavier or that both subsets weigh the same amount

    • The goal is to determine which ball weighs a different weight in 3 weighings and whether it weighs more or less


    Now, the first answer gives a strategy conditional on what each weighing comes out as. The second answer, however, gives a strategy without branching: before knowing the results of any weighing we can determine what all (three) weighings will be.



    In my limited experience with 'basic' weighing puzzles, I've never come across one where branching is necessary. So my question is:




    Does there exist a basic weighing puzzle which requires some sort of branching: where a fixed strategy of weighings cannot be determined in advance?




    Secondary questions (not necessary to answer but I would be curious to know if it's easy to prove):




    • If so, what are some necessary / sufficient conditions?

    • If not, what generalisations of a basic weighing puzzle make branching necessary / also do not require branching?










    share|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      Let us define a basic weighing puzzle as such:




      • There are <number> identical balls, except one weighs <more/less/a different amount than the others>

      • A balance scale may be used to weigh two subsets of the balls, giving <information about comparative weight>

      • The goal is to determine which ball weighs a different weight in <number> weighings <and optionally whether it weighs more or less if that isn't known>


      For example, one such puzzle is:




      • There are 12 identical balls, except one weighs a different amount than the others

      • A balance scale may be used to weigh two subsets of the balls, giving either which subset is heavier or that both subsets weigh the same amount

      • The goal is to determine which ball weighs a different weight in 3 weighings and whether it weighs more or less


      Now, the first answer gives a strategy conditional on what each weighing comes out as. The second answer, however, gives a strategy without branching: before knowing the results of any weighing we can determine what all (three) weighings will be.



      In my limited experience with 'basic' weighing puzzles, I've never come across one where branching is necessary. So my question is:




      Does there exist a basic weighing puzzle which requires some sort of branching: where a fixed strategy of weighings cannot be determined in advance?




      Secondary questions (not necessary to answer but I would be curious to know if it's easy to prove):




      • If so, what are some necessary / sufficient conditions?

      • If not, what generalisations of a basic weighing puzzle make branching necessary / also do not require branching?










      share|improve this question









      $endgroup$




      Let us define a basic weighing puzzle as such:




      • There are <number> identical balls, except one weighs <more/less/a different amount than the others>

      • A balance scale may be used to weigh two subsets of the balls, giving <information about comparative weight>

      • The goal is to determine which ball weighs a different weight in <number> weighings <and optionally whether it weighs more or less if that isn't known>


      For example, one such puzzle is:




      • There are 12 identical balls, except one weighs a different amount than the others

      • A balance scale may be used to weigh two subsets of the balls, giving either which subset is heavier or that both subsets weigh the same amount

      • The goal is to determine which ball weighs a different weight in 3 weighings and whether it weighs more or less


      Now, the first answer gives a strategy conditional on what each weighing comes out as. The second answer, however, gives a strategy without branching: before knowing the results of any weighing we can determine what all (three) weighings will be.



      In my limited experience with 'basic' weighing puzzles, I've never come across one where branching is necessary. So my question is:




      Does there exist a basic weighing puzzle which requires some sort of branching: where a fixed strategy of weighings cannot be determined in advance?




      Secondary questions (not necessary to answer but I would be curious to know if it's easy to prove):




      • If so, what are some necessary / sufficient conditions?

      • If not, what generalisations of a basic weighing puzzle make branching necessary / also do not require branching?







      strategy optimization weighing






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked Sep 8 '18 at 9:45









      boboquackboboquack

      15.4k149118




      15.4k149118






















          1 Answer
          1






          active

          oldest

          votes


















          0












          $begingroup$

          No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:



          Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.



          We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].



          That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.



          The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.



          That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.



          So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).



          That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)






          share|improve this answer








          New contributor




          Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.






          $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: "559"
            };
            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: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            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%2fpuzzling.stackexchange.com%2fquestions%2f71713%2fare-there-basic-weighing-puzzles-requiring-adaptive-strategies%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









            0












            $begingroup$

            No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:



            Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.



            We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].



            That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.



            The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.



            That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.



            So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).



            That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)






            share|improve this answer








            New contributor




            Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.






            $endgroup$


















              0












              $begingroup$

              No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:



              Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.



              We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].



              That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.



              The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.



              That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.



              So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).



              That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)






              share|improve this answer








              New contributor




              Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






              $endgroup$
















                0












                0








                0





                $begingroup$

                No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:



                Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.



                We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].



                That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.



                The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.



                That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.



                So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).



                That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)






                share|improve this answer








                New contributor




                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






                $endgroup$



                No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:



                Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.



                We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].



                That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.



                The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.



                That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.



                So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).



                That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)







                share|improve this answer








                New contributor




                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.









                share|improve this answer



                share|improve this answer






                New contributor




                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.









                answered 18 mins ago









                Dark ThunderDark Thunder

                11




                11




                New contributor




                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.





                New contributor





                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






                Dark Thunder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f71713%2fare-there-basic-weighing-puzzles-requiring-adaptive-strategies%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

                    How to label and detect the document text images

                    Vallis Paradisi

                    Tabula Rosettana