By Paolo Baldan (1) and Roberto Bruni (2)
(1) Univ. of Padova, Department of Pure and Applied Mathematics
(2) Univ. of Pisa, Computer Science Department
The country of Batalia consists of a peninsula separated by a channel from the island of Rosolia, as shown in the following map.
The prime minister, Silvestro Tomboloni, leader of the Blue party, during the electoral campaign, promised the realisation of a bridge connecting the main land to the island: this would have been the longest in the world! The opponent party, Red party, leaded by the secessionist Bobo Castagni, is firmly against the project. During his government, due to the economical crisis, Tomboloni manages only to set up some pillars where the bridge will be based. Then the opponent Red party takes over the government and stop the construction. The pillars are organised in an (n + 1) × n rectangle, as depicted in the map (blue circles). Castagni’s Red government, funds the basement of another grid of pillars also organised in a n × (n + 1) rectangle (red circles in the map). These other pillars are intended to be used to build a barrier, separating the main land from the island of Rosolia and blocking the possibility of ever completing the bridge, as explained below.
A long period of political instability follows, in which the Blue and Red parties, alternatively win the elections and govern the country for just three months. During each government of the Blue party, only a bridge fragment can be built, connecting two contiguous blue pillars. Similarly, for each government of the Red party, only a barrier fragment can be built, connecting two contiguous red pillars.
The aim of the Blue party is to complete a bridge, connecting the peninsula to the island. The aim of the Red party is to complete a barrier (completely crossing the channel from the left to the right side) preventing the bridge to be ever completed. The Blue party is governing first and thus starting the construction.
A possible situation after each party has governed three times each, is depicted in Fig. 1(Left). Fig. 1(Right) shows a situation in which the Blue party won, completing the bridge on its fifth turn.
Question. Does the Red party has a winning strategy to prevent the bridge to be completed, independently of the size of the grids (n ≥ 1)? Or does the Blue party has a winning strategy to complete the bridge?
Solution. A first observation is that the game does not admit a draw. In fact, the only state in which the construction of the bridge fails is the one in which a complete barrier has been built going from left to right, and vice versa.
To see this, consider a situation in which the Blue party does not have any move left and assume that it has not been able to build a complete bridge. Define B1 as the subset of the nodes of the Blue graph reachable from the top nodes and B2 as the set of remaining nodes. Nodes in B1 form a connected component and there is no edge connecting a node in B1 to a node in B2. Since the Blue party has no moves left, for any node in B1, the absence of an edge connecting it to an adjacent node in B2 must be due to the presence of a barrier. For instance, consider the situation in Fig. 2 below.
Assume that the light blue nodes are those in B1, while the dark blue nodes are those in B2. The absence of an edge from node b1 to node b2 is only justified by the presence of a barrier from r1 to r2. The same argument applied to all “borderline” nodes in B1 (those which are not connected to an adjacent node in B2) provides a complete red barrier from left to right, because B1 necessarily contains all the top nodes (the Red party cannot prevent the Blue party from connecting adjacent top nodes). Hence the Red party completed the barrier.
A symmetric argument would apply to the case where the Red party run out of moves and had not been able to build a complete barrier.
Now, let us prove that the Blue Party (first player) has a winning strategy. We proceed by contradiction: assume that there is no winning strategy for the Blue party. Then, since there cannot be no draw, there must be a winning strategy for the Red party.
However, since the game is quite symmetric, the Blue party could follow, after the first move, the winning strategy of the Red party and win, leading to a contradiction.
More precisely, the Blue party can act as follows. It starts by building the first bridge fragment anywhere. Then, after the Red party has built his first barrier fragment, the Blue party starts behaving according to the winning strategy of the Red party. The fact that the Blue party already built a bridge fragment in the first move, does not cause any problem: if the fragment will not be prescribed by the strategy it will not interfere in any way. If instead, at some turn, it will be prescribed by the strategy, then for that turn the Blue party can simply build a bridge fragment somewhere else. In this way the Blue party will complete the bridge, even in the case the Red party is following the winning strategy. This is a contradiction!
This puzzle is an adaptation of the Bridg-It game invented by David Gale (1921–2008), professor emeritus of mathematics at the University of California, Berkeley, and a puzzle lover who made fundamental contributions to economics and game theory.