16
$\begingroup$

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both rounds the snake plays first and begins the game by joining with a straight line any two adjacent (either vertically or horizontally, but not diagonally) points. Thus the snake is born. From then on players take turns to lengthen the snake by one line on either of its extremes. At no stage can the snake “bite” itself. The round finishes when no further lengthening of the snake is possible, at which point the length of the snake, i.e., the number of its lines, is recorded.

In the second round players switch roles and the game proceeds in the same fashion. The winner of the game is whoever achieves the longest snake while playing the role of the snake. (The figure below shows a complete game won by the first player.)

Snake of length

First player's snake of length 25

Snake of length

Second player's snake of length 17

If both players play optimally during a given round, what is the length of the snake obtained?

Note: I originally posted this question in Mathematics Stack Exchange but received no answers.

Improve this question
$\endgroup$
16
  • 5
    $\begingroup$ I think this site is a lot more suitable for this question than puzzling.SE. $\endgroup$
    – domotorp
    Commented Jul 24, 2016 at 18:15
  • 6
    $\begingroup$ I would formulate this problem as follows. First of all, let's forget about the second round completely. Two players play on an $n\times n$ grid according to the above rules, and denote by $s(n)$ the length of the longest snake the first player can achieve with optimal strategies. What do we know about $s(n)$? Is it quadratic in $n$? What about small values? What about the analogous problem for other graphs than the grid? $\endgroup$
    – domotorp
    Commented Jul 24, 2016 at 19:38
  • 1
    $\begingroup$ s(2) = 3 is trivial and s(3) = 8 is easy to show. $\endgroup$
    – Bernardo Recamán Santos
    Commented Jul 24, 2016 at 21:09
  • 2
    $\begingroup$ The first player can achieve a full length snake in the 4x4 grid too. The first player starts with down (wlog). If the second player follows with a horizontal edge (right), the first one can win in such a way that the second player from now on has only forced moves. Otherwise the first player wins by: down-down(otherwise we won)-down-right(forced)-up, and from here it is easy in both cases. $\endgroup$
    – Daniel Soltész
    Commented Jul 28, 2016 at 2:15
  • 5
    $\begingroup$ @WhatsUp: your variant 2 is Slither, and was solved by William N. Anderson, Jr. here sciencedirect.com/science/article/pii/009589567490029X Your variant 1 seems to be the game called Trap here arxiv.org/pdf/1505.07485.pdf $\endgroup$
    – Zack Wolske
    Commented Sep 7, 2016 at 19:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .