Finding the winning strategy of a variation of the Nim game












1












$begingroup$


Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:



The games starts with 16 stones arranged as follow:



o (first pile)



ooo (second pile)



ooooo (third pile)



ooooooo (fourth pile)



Rules



1.Two players take turns to take away stones.



2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.



3.The player who takes away the last stone loses.



4.If one pile is split into two piles, you have to take away them in at least two turns.



For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)



o



ooo



ooxxo



ooooooo



Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:



First turn: oo xxo



Second turn: xxxx o



And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.



The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?






game-theory combinatorial-game-theory







share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:04












  • $begingroup$
    There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:06










  • $begingroup$
    I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
    $endgroup$
    – Learning Mathematics
    Dec 20 '18 at 23:47










  • $begingroup$
    You can learn about this stuff with things from this list of resources
    $endgroup$
    – Mark S.
    Dec 20 '18 at 23:50










  • $begingroup$
    One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
    $endgroup$
    – Mark S.
    Dec 21 '18 at 3:15
















1












$begingroup$


Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:



The games starts with 16 stones arranged as follow:



o (first pile)



ooo (second pile)



ooooo (third pile)



ooooooo (fourth pile)



Rules



1.Two players take turns to take away stones.



2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.



3.The player who takes away the last stone loses.



4.If one pile is split into two piles, you have to take away them in at least two turns.



For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)



o



ooo



ooxxo



ooooooo



Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:



First turn: oo xxo



Second turn: xxxx o



And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.



The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?






game-theory combinatorial-game-theory







share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:04












  • $begingroup$
    There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:06










  • $begingroup$
    I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
    $endgroup$
    – Learning Mathematics
    Dec 20 '18 at 23:47










  • $begingroup$
    You can learn about this stuff with things from this list of resources
    $endgroup$
    – Mark S.
    Dec 20 '18 at 23:50










  • $begingroup$
    One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
    $endgroup$
    – Mark S.
    Dec 21 '18 at 3:15














1












1








1





$begingroup$


Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:



The games starts with 16 stones arranged as follow:



o (first pile)



ooo (second pile)



ooooo (third pile)



ooooooo (fourth pile)



Rules



1.Two players take turns to take away stones.



2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.



3.The player who takes away the last stone loses.



4.If one pile is split into two piles, you have to take away them in at least two turns.



For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)



o



ooo



ooxxo



ooooooo



Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:



First turn: oo xxo



Second turn: xxxx o



And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.



The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?






game-theory combinatorial-game-theory







share|cite|improve this question









$endgroup$




Here is a variant of the Nim game which I could not find out the winning strategy, the game rule is like this:



The games starts with 16 stones arranged as follow:



o (first pile)



ooo (second pile)



ooooo (third pile)



ooooooo (fourth pile)



Rules



1.Two players take turns to take away stones.



2.Each time you can at most take away all stones in the same pile , and you must at least take away one stone.



3.The player who takes away the last stone loses.



4.If one pile is split into two piles, you have to take away them in at least two turns.



For instance the third and fourth stones in the third pile was taken: (x represents the taken stones)



o



ooo



ooxxo



ooooooo



Then you are not allowed to take away all stones in the third pile in one turn. You have to take away all of them in at least two turns since it has been split into two piles:



First turn: oo xxo



Second turn: xxxx o



And for pattern like oxxoxoo, you have to take away all of them in at least 3 turns, etc.



The first three rules are similar to the classic NIM game(I know the winning strategy in the classic one), however the last rule makes it not applicable. My question is who has the winning strategy in this game, and what is the winning strategy?






game-theory combinatorial-game-theory




game-theory combinatorial-game-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Dec 20 '18 at 14:20









Learning MathematicsLearning Mathematics

767




767








  • 1




    $begingroup$
    Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:04












  • $begingroup$
    There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:06










  • $begingroup$
    I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
    $endgroup$
    – Learning Mathematics
    Dec 20 '18 at 23:47










  • $begingroup$
    You can learn about this stuff with things from this list of resources
    $endgroup$
    – Mark S.
    Dec 20 '18 at 23:50










  • $begingroup$
    One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
    $endgroup$
    – Mark S.
    Dec 21 '18 at 3:15














  • 1




    $begingroup$
    Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:04












  • $begingroup$
    There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
    $endgroup$
    – Mark S.
    Dec 20 '18 at 17:06










  • $begingroup$
    I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
    $endgroup$
    – Learning Mathematics
    Dec 20 '18 at 23:47










  • $begingroup$
    You can learn about this stuff with things from this list of resources
    $endgroup$
    – Mark S.
    Dec 20 '18 at 23:50










  • $begingroup$
    One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
    $endgroup$
    – Mark S.
    Dec 21 '18 at 3:15








1




1




$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04






$begingroup$
Do you know the Sprague Grundy theorem? That's all but crucial for this problem. If you already know it, what are your thoughts/where did you get stuck? If you don't, where did you encounter thos problem (e.g. in a programming class where you just have to write a program to make the winning moves?)?
$endgroup$
– Mark S.
Dec 20 '18 at 17:04














$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06




$begingroup$
There's also a chance you know the theorem without the name, so did you learn about applying "nimbers" or "grundy values" to games other than nim?
$endgroup$
– Mark S.
Dec 20 '18 at 17:06












$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47




$begingroup$
I haven't learnt that yet. My classmates played this game with me, but both of us dont know the winning strategy. I would take a look of the theorem today
$endgroup$
– Learning Mathematics
Dec 20 '18 at 23:47












$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50




$begingroup$
You can learn about this stuff with things from this list of resources
$endgroup$
– Mark S.
Dec 20 '18 at 23:50












$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15




$begingroup$
One more thing: have you tried playing it like Nim against, say, a random opponent, to see what you learn?
$endgroup$
– Mark S.
Dec 21 '18 at 3:15










1 Answer
1






active

oldest

votes


















2












$begingroup$

Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.



With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.



However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.



For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.



So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.






share|cite|improve this answer









$endgroup$














    Your Answer








    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%2f3047583%2ffinding-the-winning-strategy-of-a-variation-of-the-nim-game%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









    2












    $begingroup$

    Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.



    With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.



    However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.



    For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.



    So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.






    share|cite|improve this answer









    $endgroup$


















      2












      $begingroup$

      Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.



      With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.



      However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.



      For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.



      So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.






      share|cite|improve this answer









      $endgroup$
















        2












        2








        2





        $begingroup$

        Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.



        With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.



        However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.



        For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.



        So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.






        share|cite|improve this answer









        $endgroup$



        Since you say you know the winning strategy in classical Nim, I presume you are familiar with the nim-sum $oplus$. If you play this position in classical Nim without the fourth rule, it is lost for the first player to move, as $1 oplus 3 oplus 5 oplus 7 = 0$.



        With the fourth rule, you get additional moves: If you have a stack with $x+y+k$ stones, you can remove $k$ stones and leave two piles with $x$ and $y$ stones. The resulting Nim value of these two piles are $x oplus y$.



        However, it is easy to show that $x oplus y leq x+y$. That means whenever you split a pile into two (or more!) piles, you can instead remove stones from the same pile without splitting it to get the same nim-value.



        For instead, if you split the pile with 3 stones into two piles like this: oxo, the two piles have nim-value $1 oplus 1 = 0$. So you get the same nim-value if you take all three stones to remove the entire pile.



        So the answers are: 1) In this game, the first player to move loses. 2) The winning strategy is exactly the same as in classical Nim, and you never have to split any piles. If your opponent does so, you always have an answer.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 29 '18 at 11:53









        JAskgaardJAskgaard

        1467




        1467






























            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%2f3047583%2ffinding-the-winning-strategy-of-a-variation-of-the-nim-game%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 change which sound is reproduced for terminal bell?

            Image
            3 Recently upgrade to 18.10 from 18.04, and using the terminal is becoming annoying: the new alert sound is a drip ( /usr/share/sounds/gnome/default/alerts/drip.ogg ), and the previous one is still located at ( /usr/share/sounds/ubuntu/stereo/bell.ogg ). My issue is that at the gnome-terminal, when autocompleting or pressing left BOTH sounds are reproduced, at the same time. I want to just have ubuntu/stereo/bell.ogg active, not both . At the moment I have been only able to reduce the volume of the alerts (but still both are played), or turn the alerts down (but I dislike both "solutions"). gnome-terminal 18.10 teminal-bell share | improve this question
            Read more

            Can I use Tabulator js library in my java Spring + Thymeleaf project?

            Image
            0 I want to add Tabulator js to my java project. I added tabulator.min.js, tabulator.min.css to resources folder. After that added to my html page these dependencies as recommending in readme.md. <link rel="stylesheet" th:href="@{/css/tabulator.min.css}"> <script type="text/javascript" th:src="@{/js/tabulator.min.js}"></script> Now my tables view all elements, that I have in the html page, but not correct. In the documentation of Tabulator is example how to create header and table, var table = new Tabulator("#example-table", { columns:[ {title:"Name", field:"name", sorter:"string", width:200, editor:true}, {title:"Age", field:"age", sorter:"
            Read more

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Image
            up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx
            Read more