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
George and Mildred have bought a brand new house …a great buy! A very nice house at an extremely cheap price.
As the summer approaches, they start discovering why it was so cheap …due to a nearby unattended deposit of nuclear wastes, a terrifying kind of mutant mosquito lives in the area. A mutant mosquito is double-headed and it can only be affected by shooting at short distance, with special radiation guns, simultaneously at its two heads. In this way the mosquito does not disappear, but it rather splits in two smaller mosquitoes, each moving towards the origin of the shot.
More precisely, consider a grid where cells are identified by their coordinates (i,j). A mosquito can be in any cell. When it is in (i,j) in order to hit its heads with the radiation guns, the neighbor cells (i + 1,j) and (i,j + 1) must be free. After shooting it, the original mosquito disappears and two smaller mosquitoes appears in (i + 1,j) and (i,j + 1). An example, with the mosquito in (0,0) is given in the picture below, where also the duplication effect of the firing is illustrated:
(a)
(b)
Continuing from the situation in picture (b), the mosquito in (0,1) can be shot as illustrated in (c) below. This leads to the situation depicted in (d). Here the mosquito in (1,0) cannot be shot, since the neighbor cell (1,1), where a gun should be placed, is not free.
(c)
(d)
Continuing from (d), the mosquito in (1,1) can be shot, leading to (e). Now, the mosquito in (1,0) can be shot and this leads to (f), and so on.
(e)
(f)
Now, assume that the house of George and Mildred has a square base of k × k cells, and it is placed at the bottom corner (0,0) of the grid. As an example, with k = 4, the house would occupy the grey area in the picture below.
The question is whether it is always possible for George and Mildred, once a mosquito is found at the corner (0,0) (as in the picture above), to completely free their house from the mosquitoes by using the radiation guns. Clearly this is possible (in one step) for k = 1, but …is this always possible independently of the size k of the house?
A solution
For k = 2 it is still possible to free the house in four more steps from the situation in picture (f), e.g. by shooting consecutively at the mosquitoes in cells (1,2), (2,2), (2,1), (1,1). Instead, quite surprisingly, for k ≥ 3 it is not possible to free the house.
The proof is based on the definition of a suitable invariant for the grid. Let us identify the state of the grid with the set of cells occupied by mosquitoes. For example, the state corresponding to picture (d) is
{(0,2), (1,1), (1,0)}
Let us denote by C = {(i,j)∣0 ≤ i,j } the set of all cells. Then, we consider a weight function w : 2C → ℕ over states defined by
w(S) = ∑ (i,j)∈S 1/(2i+j)
for any state S ∈ 2C.
It is easy to check that the weight of the grid is invariant: whenever we move from state S to S′ by shooting a mosquito, then w(S) = w(S′). In fact, suppose that we move from state S to S′ by shooting at the mosquito in cell (i,j) for some i and j. Then w (S′) = w (S ):
Since w({(0,0)}) = 1, we have that w(S) = 1 must hold for any reachable state S.
Let us denote by Ck the set of cells whose indices are both less than k, i.e., Ck = {(i,j)∣0 ≤ i,j < k}. Clearly C3 corresponds to the area of the house when the size k = 3. Then observe that w(C3) = 49/16 and w(C) = 4:
Now, it easily follows that for every reachable state S at least one of the cells in C3 will contain a mosquito. In fact, given any state S without any mosquito in C3, i.e., S ⊆ C \C3, we have w(S) ≤ w(C) – w(C3) = 15/16 < 1. Hence S is not reachable, since all reachable states must weight exactly 1.