, 2018

The answer is: $2^{n-1}$.

We first prove the upper bound. Let $a$ be the number of friends of the wolf, and let $b$ be the number of pairs of friend sheep. Note that each time the wolf eats a sheep, the parity of $a+b$ changes. Therefore, if the wolf is able to eat all the sheep, it must be the case that $a+b+n-1 \equiv 1 \pmod{2}$ (after the wolf has eaten $n-1$ sheep, it must then be able to eat the last sheep). Hence, among the $2^n$ ways the wolf can choose its initial friend sheep, at most $2^{n-1}$ of them have a chance of allowing it to eat all the sheep.

Below we construct a sheep friendship configuration that achieves this upper bound. Number the sheep from $1$ to $n$, and let sheep $i$ and $i+1$ be friends $(i = 1, 2, \dots, n-1)$, with no other friendships. We will prove by mathematical induction that, under this friendship configuration, as long as the number of the wolf's initial friend sheep is odd, the wolf can always eat all the sheep:

(i) The case $n=1$ is obvious.

(ii) When $n > 1$, let $k$ be the largest number among the wolf's initial friend sheep. Note that the wolf can first eat sheep $k, k+1, \dots, n$ in order, after which the situation becomes identical to the case $n=k$ (note that the wolf has eaten $n-k+1$ sheep, and the number of pairs of friend sheep has also decreased by $n-k+1$, so the parity of the number of the wolf's friend sheep is preserved). Thus, by the induction hypothesis, the claim is proved.

Moreover, there are $2^{n-1}$ ways for the wolf to choose an odd number of friend sheep, so the above example achieves the upper bound.