Who can win the bowling match？

Question

There are $n$ bowling pins arranged from left to right, numbered from $1$ to $n$ in the order they are standing. Two people throw bowling balls and hit them in turn. Each time they hit a pin, they knock over that pin, and its two adjacent pins. (If you hit pin number $x$, then pins $x$, $x-1$ and $x+1$ will fall, if they had not fallen earlier). The player who hits the last pin wins. Who can win?

For example, if you hit pin 3, and pins 2 and 4 are all standing, you will knock down pins 2, 3, and 4. If you hit the 3th pin, but only the 3rd and 4th pin is standing, you will knock down the 3rd and 4th pins. If you hit pin 3, and the 4th and 2nd pins are not standing, you will only knock down pin 3.

I guess when $n\ge 4$, if $n$ is an odd number, the first hand can hit the middle three, and then mirror the operation of the second hand, and the first hand will win. If n is even, it seems a little complicated?

Answer 1

Here's a simple Python script to calculate the nim-value of this game (i.e., the size of the equivalent Nim heap) for each starting number of pins. The precise rule I'm using is that you can knock down 2 or 3 pins from the end of a row, or any adjacent 3 from the middle.

def mex(vals):
  # return the minimum value excluded from `vals`
  v = 0
  while v in vals: v += 1
  return v

def nimVal(n, cache = { 0:0, 1:1 }):
  if n in cache: return cache[n]
  vals = [nimVal(n-2, cache)] # knock down 2 pins on the end
  if n >= 3:
    vals.append(nimVal(n-3, cache)) # knock down 3 pins on the end
    for m in range(1, n-3):
      # knock down 3 pins in the middle, leaving m on one side
      # and n-m-3 on the other
      vals.append(nimVal(m, cache) ^ nimVal(n-m-3, cache))
  ret = cache[n] = mex(vals)
  return ret

Running this script shows the periodicity to be $34$, and that the second player wins when the initial number of pins is sufficiently large and is equal to $4$, $8$, $20$, $24$, or $28$ (mod $34$). In fact "sufficiently large" isn't that large... the only deviations from this rule are $N=14$ and $N=34$, which are also second-player wins.

Answer 2

Note: This answer is incorrect, see mjqxxxx's answer. I'll edit again if I figure out how to fix.

---

I'm interpreting the question as follows. There are pins numbered 1, ..., 100. On your turn you can select any pin that's still standing, and knock down that pin and the pins immediately adjacent to it. (If the adjacent pins are already down, then they stay down.) For example, you can select pin 3 and knock down 2, 3, 4. The pins at the ends only have one adjacent pin each, so selecting pin 1 knocks down 1 and 2, and selecting pin 100 knocks down 99 and 100. There are two players alternating turns and the winner is the player who knocks down the last pin. And to clarify, you cannot select a pin that's already down, otherwise the player who's about to lose can select the same pin over and over and the game would not end.

The main observation is that the solution must also consider the misère version – same rules, except the player who knocks down the last pin loses.

Let's introduce some notation: $G(n)$ for the game starting with $n$ pins, and $G^*(n)$ for the misère version starting with $n$ pins. So for example, $G(1)$, $G(2)$, $G(3)$ are evidently wins for the first player, while $G^*(3)$ is also a win for the first player. $G(4)$ is a loss for the first player while $G^*(4)$ is a win for the first player.

Let $W$ be the set of all $n \in \mathbb{N}$ such that $G(n)$ is a win for the first player and $G^*(n)$ is a loss for the first player; let $L$ be the set of all $n$ such that $G(n)$ is a loss and $G^*(n)$ is a win; and let $B$ be the set of all $n$ such that both $G(n)$ and $G^*(n)$ are wins. We have $W = \{1, 2, 6, 7, ...\}$, $L = \{0, 4, 8, ...\}$, $B = \{3, 5, ...\}$.

Now let's say we're in the middle of a game and we're looking at a board with $k$ groups of consecutive pins, with lengths $\ell_1$, ..., $\ell_k$. Then which player will win the game is determined by which of the classes $W$, $L$, $B$ the lengths $\ell_i$ belong to. I'll leave it to you to prove this lemma:

Lemma. If at least one of the $\ell_i$'s is in $B$, then the next person to play wins iff an odd number of $\ell_i$'s are in $B$. Otherwise, the next person to play wins iff an odd number of $\ell_i$'s are in $W$.

This completely solves the game (i.e. tells us how to play perfectly) as long as we can figure out these classes $W$, $L$, $B$. And we can, by recursion. Armed with the Lemma, any first move we can make in $G(n)$ or $G^*(n)$ reduces us to the result of $G(m)$ or $G^*(m)$ for one or more $m < n$.

Thus, $G(n)$ is a win for the first player iff $n-2 \in L$ or $\exists j$ ($0 \le j \le n-3$) such that $j$ and $n-3-j$ are in the same class. This generalizes the observation the OP made: If $n$ is odd, then $\exists j$ such that $j = n-3-j$ which means the first player wins $G(n)$.

Likewise, $G^*(n)$ is a win for the first player iff $n-2 \in W$ or $\exists j$ ($0 \le j \le n-3$) such that $j \in L$ and $n-3-j \in W$.

Finally, doing some computations, we find \begin{align*} W &= \{1, 2, 6, 7, 11, 15, 16, 20, 21, 25, ...\} \\ L &= \{0, 4, 8, 14\} \\ B &= \{3, 5, 9, 10, 12, 13, 17, 18, 19, 22, 23, 24, 26, 27, 28, ...\} \end{align*} and we notice that for $n > 14$ the behavior is periodic with period 14. This can be proven by casework, tedious but not very complicated.

So we conclude that the first player wins the game starting with any number of pins except for 4, 8, and 14.