By
Paolo Baldan, University of Padova
Roberto Bruni, University of Pisa
Some time ago George and Mildred have been bravely fighting against a terrifying kind of mutant mosquitoes grown in a nearby unattended deposit of nuclear wastes [link]. At those times the battle was finally won.
Now, seven years later, the support to environmental protection has been further reduced and a new accident occurs at the deposit: some nuclear waste gets out from the containers determining the born of a new horrible species of mutant mosquitoes.
The scientific community studies the phenomenon and understands that mutant mosquitoes can be of two types, referred to as α and β. Mosquitoes of type α are invulnerable, while those of type β can be killed by means of a special radiation gun. Mosquitoes attack in linear storms and whenever a type β mosquito is shot, it disappears, the storm breaks in two, but the mosquitoes that were adjacent to the one that have been shot, change their type (if they were of type α they turn to type β and vice versa).
As an example, consider the storm below, where α mosquitoes are circled.
A possible shooting sequence which destroys all the mosquitoes is illustrated below
Can you help George and Mildred to win this new battle against the mosquitoes? More precisely:
- Q1. Given a (non-empty) storm, can you identify a condition that is necessary for allowing the complete elimination of the mosquitoes in the storm?
- Q2. Is the condition also sufficient? If not, under this condition, is there a strategy that can be followed for successfully destroying the storm?
Of course you can also help them by producing a Prolog/ASP code for the problem simulation. Just in case, we report the the solutions to Q1 and Q2.
Solution for Q1. A necessary condition is the presence of an odd number of β mosquitoes in the storm. In fact, assume we have a non-empty storm that contains an even number of β mosquitoes. First, if there are no α mosquitoes it means that the storm is composed of β mosquitoes only and none can get killed. Second, suppose there are two or more β mosquitoes in the storm. Then one can choose a β mosquito and shoot it. Whatever mosquito is chosen, either the substorm on its left or that on its right will have, before the shot, an odd number of β mosquitoes. Hence, after the shot, at least one of the remaining substorms will be non empty and with an even number of β mosquitoes. This means that we reduce to shorter substorms, one of each is again, non-empty and with an even number of β mosquitoes. Eventually a non-empty storm will be produced that is made only of α (invulnerable) mosquitoes, that cannot be killed.
Solution for Q2. Having an odd number of β mosquitoes is not sufficient for destroying the whole storm, without taking some specific strategy. For instance, the following reduction gets stuck:
Whenever, a storm has an odd number of β mosquitoes, it is easy to see that the strategy consisting of shooting always the first β mosquito from the left will destroy all mosquitoes. In fact, the mosquito that is shot has an even number of β mosquitoes both on the left (none) and on the right. This means that after the shot, two substorms will be produced (possibly empty, since the β mosquito could be the leftmost or the only mosquito in the storm) and each non-empty substorm will have an odd number of β mosquitoes. While the overall number of β mosquitoes can increase, the remaining storms will be shorter than the original one so we obtain simpler instances of the original problem. Therefore, applying the same strategy to each substorm, eventually all mosquitoes will be killed.