Problem

Source: 2021 Macedonian Balkan MO TST - Problem 4

Tags: combinatorics, graph theory, geometry, 3D geometry



Viktor and Natalia play a colouring game with a 3-dimensional cube taking turns alternatingly. Viktor goes first, and on each of his turns, he selects an unpainted edge, and paints it violet. On each of Natalia's turns, she selects an unpainted edge, or at most once during the game a face diagonal, and paints it neon green. If the player on turn cannot make a legal move, then the turn switches to the other player. The game ends when nobody can make any more legal moves. Natalia wins if at the end of the game every vertex of the cube can be reached from every other vertex by traveling only along neon green segments (edges or diagonal), otherwise Viktor wins. Who has a winning strategy? (Prove your answer.) Proposed by Viktor Simjanoski