Let n≥2 be an integer. Alice and Bob play a game concerning a country made of n islands. Exactly two of those n islands have a factory. Initially there is no bridge in the country. Alice and Bob take turns in the following way. In each turn, the player must build a bridge between two different islands I1 and I2 such that: ∙ I1 and I2 are not already connected by a bridge. ∙ at least one of the two islands I1 and I2 is connected by a series of bridges to an island with a factory (or has a factory itself). (Indeed, access to a factory is needed for the construction.) As soon as a player builds a bridge that makes it possible to go from one factory to the other, this player loses the game. (Indeed, it triggers an industrial battle between both factories.) If Alice starts, then determine (for each n≥2) who has a winning strategy. (Note: It is allowed to construct a bridge passing above another bridge.)
Problem
Source: Benelux Mathematical Olympiad 2017, Problem 2
Tags: combinatorics, combinatorics proposed, games
07.05.2017 03:22
If n is even, then a straightforward "mimicry algorithm" lets Bob win. If n is odd then consider that in order for a player to lose, they must be forced to create a losing bridge (only) in an "unfortunate configuration," which specifically is a partition of the bridge graph into two connected graphs so that there is one factory in each of the connected components. The number of edges in such a configuration is \binom{k}{2}+\binom{n-k}{2}=\binom{n}{2}+k(n-k)\equiv_2 \tbinom{n}{2}. Thus is n\equiv 1\pmod{4}, Bob will always be able to make a move without losing, and if n\equiv 3\pmod{4}, Alice will always be able to make a move without losing. Thus Alice has a winning strategy if n\equiv 3\pmod{4}, and Bob has a winning strategy otherwise.
30.03.2021 03:40
I claim that Alice wins when n \equiv 3 \pmod 4, and Bob wins otherwise. We will prove this by considering the value of n \pmod 4. Let this problem be represented by a graph, where the islands are vertices and the bridges by edges. The factories are any 2 islands. It suffices to determine the person who will be forced to make the graph connected. If n is even, Bob can copy Alice's move using the other factory. Since there are an even number of vertices, it is possible to divide the vertices into two groups of n/2 vertices such that Alice makes the complete graph of one group and Bob makes the complete graph of the other group of vertices. Then, Alice will be forced to draw an edge that makes the graph complete, meaning Bob wins. Claim: \binom{x}{2}+\binom{y}{2} is odd when x+y \equiv 3 \pmod 4 and \binom{x}{2}+\binom{y}{2} is even when x+y \equiv 1 \pmod 4. Proof: First consider when x+y \equiv 3 \pmod 4. We can let x>y. Then either x \equiv 1 \pmod 4, y \equiv 2 \pmod 4 OR x \equiv 3 \pmod 4, y\equiv 0 \pmod 4. In the case x \equiv 1 \pmod 4, y \equiv 2 \pmod 4, \binom{x}{2} is even and \binom{y}{2} is odd, so \binom{x}{2}+\binom{y}{2} is odd. In the case x \equiv 3 \pmod 4, y\equiv 0 \pmod 4, \binom{x}{2} is odd and \binom{y}{2} is even, so \binom{x}{2}+\binom{y}{2} is odd. Either way, \binom{x}{2}+\binom{y}{2} is odd. The proof is analogous for proving that \binom{x}{2}+\binom{y}{2} is even when x+y \equiv 1 \pmod 4. Just note that either x \equiv 1 \pmod 4, y \equiv 0 \pmod 4 OR x\equiv 3 \pmod 4, y\equiv 2 \pmod 4. In both cases, you get that \binom{x}{2}+\binom{y}{2} is even. Note that we can define \binom{1}{2}=0 so that the value of \binom{1}{2}=0 is consistent with the other values of 1 \pmod 4. Now consider when n\equiv 1 \pmod 4. The loosing move must be an edge that joins two complete graphs, where each complete graph has one factory as a vertex. Since a complete graph on k vertices has \binom{k}{2} edges, by the claim, no matter how the two complete graphs are created, the sum of the edges of both complete graphs must be even. Hence, Alice must be the one that makes a move that makes the graph connected, and Bob wins. Similarly, if n\equiv 1 \pmod 4, the sum of the edges of both complete graphs must be odd. Hence, Bob must be the one that makes the graph connected, and Alice wins. We've exhausted all cases, so Alice wins when n \equiv 3 \pmod 4, and Bob wins otherwise.