Two people take turns coloring a convex polyhedron












3












$begingroup$


Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first and both players use their optimal strategies, who wins the game?



I don't really understand where to start. I tried playing the game but that didn't help much for me because I couldn't think of any ideas. I know that for a tetrahedron, the game results in a tie. I know that for a cube the first person wins if they pick something adjacent to their first move. After this, I am not sure with a pentagon because if it is a square-based-pyramid, the first person wins if the pick the square but if it is a triangular prism, it results in a tie.










share|cite|improve this question











$endgroup$












  • $begingroup$
    I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
    $endgroup$
    – Theo Bendit
    3 hours ago
















3












$begingroup$


Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first and both players use their optimal strategies, who wins the game?



I don't really understand where to start. I tried playing the game but that didn't help much for me because I couldn't think of any ideas. I know that for a tetrahedron, the game results in a tie. I know that for a cube the first person wins if they pick something adjacent to their first move. After this, I am not sure with a pentagon because if it is a square-based-pyramid, the first person wins if the pick the square but if it is a triangular prism, it results in a tie.










share|cite|improve this question











$endgroup$












  • $begingroup$
    I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
    $endgroup$
    – Theo Bendit
    3 hours ago














3












3








3


3



$begingroup$


Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first and both players use their optimal strategies, who wins the game?



I don't really understand where to start. I tried playing the game but that didn't help much for me because I couldn't think of any ideas. I know that for a tetrahedron, the game results in a tie. I know that for a cube the first person wins if they pick something adjacent to their first move. After this, I am not sure with a pentagon because if it is a square-based-pyramid, the first person wins if the pick the square but if it is a triangular prism, it results in a tie.










share|cite|improve this question











$endgroup$




Rachel and Beatrice take turns coloring the faces of a convex polyhedron red and blue, respectively. A player wins if she gets her color on three faces that share a common vertex. If Rachel goes first and both players use their optimal strategies, who wins the game?



I don't really understand where to start. I tried playing the game but that didn't help much for me because I couldn't think of any ideas. I know that for a tetrahedron, the game results in a tie. I know that for a cube the first person wins if they pick something adjacent to their first move. After this, I am not sure with a pentagon because if it is a square-based-pyramid, the first person wins if the pick the square but if it is a triangular prism, it results in a tie.







combinatorics game-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 4 hours ago







Math_Guy

















asked 4 hours ago









Math_GuyMath_Guy

627




627












  • $begingroup$
    I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
    $endgroup$
    – Theo Bendit
    3 hours ago


















  • $begingroup$
    I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
    $endgroup$
    – Theo Bendit
    3 hours ago
















$begingroup$
I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
$endgroup$
– Theo Bendit
3 hours ago




$begingroup$
I would say, based on your own investigations, a fair answer to this question would be "it depends". If you want to go further, you could try finding a proof that the second player can never force a win (or find an example where she can, though I suspect this won't happen). If you really want to complete your investigation, you could try finding a characterisation of polyhedra for which one player or the other can force a win. But, I would say you've answered your own question, until you clarify further what you hope to achieve.
$endgroup$
– Theo Bendit
3 hours ago










3 Answers
3






active

oldest

votes


















3












$begingroup$

Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.



Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.



Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.



What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces:
$$3F = 2E$$
$$4V ge 2E$$
$$V+F = E+2$$
The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these,
$$12E+24=12(V+F)=4cdot 3F+3cdot 4V ge 4cdot 2E+3cdot 2E = 14E$$
and $Ele 12$. That leads to three possibilities:





  • $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.


  • $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.


  • $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.


So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.






share|cite|improve this answer









$endgroup$





















    0












    $begingroup$

    I do not have an answer, but I may be able to contribute:



    Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.






    share|cite|improve this answer









    $endgroup$





















      0












      $begingroup$

      All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.



      The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.






      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%2f3123313%2ftwo-people-take-turns-coloring-a-convex-polyhedron%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        3












        $begingroup$

        Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.



        Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.



        Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.



        What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces:
        $$3F = 2E$$
        $$4V ge 2E$$
        $$V+F = E+2$$
        The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these,
        $$12E+24=12(V+F)=4cdot 3F+3cdot 4V ge 4cdot 2E+3cdot 2E = 14E$$
        and $Ele 12$. That leads to three possibilities:





        • $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.


        • $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.


        • $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.


        So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.






        share|cite|improve this answer









        $endgroup$


















          3












          $begingroup$

          Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.



          Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.



          Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.



          What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces:
          $$3F = 2E$$
          $$4V ge 2E$$
          $$V+F = E+2$$
          The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these,
          $$12E+24=12(V+F)=4cdot 3F+3cdot 4V ge 4cdot 2E+3cdot 2E = 14E$$
          and $Ele 12$. That leads to three possibilities:





          • $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.


          • $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.


          • $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.


          So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.






          share|cite|improve this answer









          $endgroup$
















            3












            3








            3





            $begingroup$

            Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.



            Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.



            Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.



            What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces:
            $$3F = 2E$$
            $$4V ge 2E$$
            $$V+F = E+2$$
            The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these,
            $$12E+24=12(V+F)=4cdot 3F+3cdot 4V ge 4cdot 2E+3cdot 2E = 14E$$
            and $Ele 12$. That leads to three possibilities:





            • $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.


            • $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.


            • $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.


            So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.






            share|cite|improve this answer









            $endgroup$



            Generalizing that cube strategy, the first player $R$ wins if there's any face with four or more edges. Choose that face first. Whatever the second player $B$ does, there are three consecutive edges of that face with the other faces on them open. Choose the face connected to the middle edge. There are then two open faces that lead to a victory on $R$'s next move; $B$ can only block one of them, and $R$ wins.



            Similarly, if there's any vertex that's part of five or more faces, the first player wins. Just keep choosing faces at that vertex until you've got three of them.



            Both of these strategies win in the minimum three moves, so they don't have to worry about playing defense - the opponent doesn't get the chance to color enough faces for a chance of winning.



            What polygons don't fit into either one of these categories? We need all faces to be triangles, and all vertices to have degree $4$ or less. That gives us the following system for the numbers of vertices, edges, and faces:
            $$3F = 2E$$
            $$4V ge 2E$$
            $$V+F = E+2$$
            The last equation there is the Euler characteristic, true for any polyhedron without holes. Combining these,
            $$12E+24=12(V+F)=4cdot 3F+3cdot 4V ge 4cdot 2E+3cdot 2E = 14E$$
            and $Ele 12$. That leads to three possibilities:





            • $E=6,F=4,V=4$. The tetrahedron. Since neither player gets the chance to color three faces, it's a draw.


            • $E=9,F=6,V=5$. This can be realized by building two triangular pyramids on opposite sides of the same base. The first player has a winning strategy here. Their first move is a face that covers two of the degree-$4$ vertices and one degree-$3$ vertex (because all of the faces are like that). Her second move is any face edge-connected to the first. On her third move, there are three or four winning options, of which at most two are blocked.


            • $E=12,F=8,V=6$. The octahedron. As @Jaarbahd noted, this one's a victory for the first player $R$. Alternately, there's a strategy that doesn't bother with defense - for $R$'s second move, choose one of the three faces edge-connected to their first move (at least two are available). There are then four possible faces that win on the next move, and the first player's two moves can only block two of them.


            So, there it is. On anything other than the tetrahedron, the first player wins in the minimum three moves, not bothering with defense. It's not much of a game.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered 3 hours ago









            jmerryjmerry

            9,9711225




            9,9711225























                0












                $begingroup$

                I do not have an answer, but I may be able to contribute:



                Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.






                share|cite|improve this answer









                $endgroup$


















                  0












                  $begingroup$

                  I do not have an answer, but I may be able to contribute:



                  Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.






                  share|cite|improve this answer









                  $endgroup$
















                    0












                    0








                    0





                    $begingroup$

                    I do not have an answer, but I may be able to contribute:



                    Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.






                    share|cite|improve this answer









                    $endgroup$



                    I do not have an answer, but I may be able to contribute:



                    Consider the octohedron. You will find that Player 1 always wins with optimal strategy. Whichever face P2 picks for their first move, P1 replies by painting the opposite face. Unless P2 picks the face opposite P1's first move. In which case, P1 responds by selecting any face that is connected edgewise to P2's choie. Whatever P2 picks after that leaves a winning move.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered 4 hours ago









                    JaarbahdJaarbahd

                    116




                    116























                        0












                        $begingroup$

                        All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.



                        The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.






                        share|cite|improve this answer









                        $endgroup$


















                          0












                          $begingroup$

                          All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.



                          The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.






                          share|cite|improve this answer









                          $endgroup$
















                            0












                            0








                            0





                            $begingroup$

                            All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.



                            The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.






                            share|cite|improve this answer









                            $endgroup$



                            All polyhedra with a vertex, $v*$, of degree 5+ is a win for player one. There are 5 faces incident to $v*$ each turn, player one chooses one of these faces, and player two is helpless. Additionally, all polyhedra with a non-triangular face, $f$, are a win for player 1. Player 1 chooses $f$ which is incident to 4+ vertices, and it plays out just like the cube scenario.



                            The only remaining case is the octohedron and and no pyramid, which I’ll leave you to work out.







                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered 3 hours ago









                            Zachary HunterZachary Hunter

                            582111




                            582111






























                                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%2f3123313%2ftwo-people-take-turns-coloring-a-convex-polyhedron%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

                                Liste der Baudenkmale in Friedland (Mecklenburg)

                                Single-Malt-Whisky

                                Czorneboh