Let $n \geqslant 2$ be an integer. Alice and Bob are playing a game concerning a country made up of $n$ islands. Exactly two of these $n$ islands have a factory. Initially, there are no bridges in the country. Alice and Bob take turns playing in the following way. On each turn, the player must build a bridge between two different islands $I_{1}$ and $I_{2}$ such that:

- $I_{1}$ and $I_{2}$ are not already connected by a bridge,
- at least one of the two islands $I_{1}$ and $I_{2}$ has a factory or is connected to a factory by a sequence of bridges (indeed, access to a factory is necessary for construction).

As soon as a player builds a bridge that allows a passage from one factory to the other, that player loses the game (this triggers an industrial war between the two factories). If Alice is the first to play, determine for which $n \geqslant 2$ she has a winning strategy.
General Analysis We can start with small cases. A player is forced to lose when no one can build a bridge without connecting the two factories, so they lose if:

- the first factory is connected to $k$ islands and the $\binom{k}{2}$ bridges that can be built between these $k$ islands have been constructed,
- the second factory is connected to the remaining $n-k$ islands and the $\binom{n-k}{2}$ bridges that can be built between these $n-k$ islands have been constructed.

Therefore, in all cases, $T=\frac{k(k+1)}{2}+\frac{(n-k)(n-k+1)}{2}$ bridges have been constructed, so $T$ turns have elapsed, and the player who must play at this moment has lost. We now need to determine the parity of $T$.

## Case-by-Case Study

- If $n \equiv 1 \quad$ [4] and if $k \equiv 0,1 \quad$ [4] then $n-k \equiv 1,0 \quad[4]$; similarly, if $k \equiv 2,3 \quad$ [4] then $n-k \equiv 3,2[4]$.

We deduce after a quick analysis that $\frac{k(k-1)}{2}$ and $\frac{(n-k)(n-k-1)}{2}$ have the same parity, so $T$ is even, and it is Alice who faces the configuration that will be fatal to her.

- If $n \equiv 3$ [4] and if $k \equiv 0,1 \quad$ [4] then $n-k \equiv 3,2 \quad[4]$; similarly, if $k \equiv 2,3 \quad$ [4] then $n-k \equiv 1,0[4]$.

It follows that $\frac{k(k-1)}{2}$ and $\frac{(n-k)(n-k-1)}{2}$ are of different parity, so $T$ is odd, and it is Bob who will weep in despair at his crushing defeat...

- If $n$ is even, the parity of $T$ depends on $k$. We will therefore need to use another argument. Bob can always play the symmetric move to Alice's, since there is an even number of islands. More specifically, we number the islands from 1 to $n$. When Alice plays a bridge between island $i$ and island $j$, Bob plays the bridge between island $2n+1-i$ and island $2n+1-j$. In this case, if Alice can play on her $i$-th turn, then Bob can also play on his $i$-th turn. It follows that Alice will be the loser.

Conclusion Therefore, Alice wins only if $n \equiv 3[4]$, and Bob wins in all other cases.