Cats among Pigeons (cats)

Run LPL Code  ,  PDF Document

Problem

Downs, Heath, Field, Forest, and Marsh – five elderly pigeon fanciers – were worried by the depredations of marauding cats owned by five not less elderly ladies. Hoping to get control of the cats, they married the cat owners.

The scheme worked well for each of them so far as his own cat and pigeons were concerned; but it was not long before each cat had claimed a victim and each fancier had lost his favorite pigeon.

(1) Mr. Downs’ pigeon was killed by Mrs. Heath’s cat. (2) Mrs. Downs’ cat killed the pigeon owned by the man who married the owner of the cat which killed Mr. Marsh’s pigeon. (3) Mr. Forest’s pigeon was killed by the cat owned by the lady who married the man whose pigeon was killed by Mrs. Field’s cat.

Who was the owner of the pigeon killed by Mrs. Forest’s cat? This puzzle is from [1].

Modeling Steps

1. We introduce a set holding the family names of the five couples. Each couple had a cat: c = {1,…, 5} and a pigeon: p = {1,…, 5}.

2. A binary variable x_c,p is used to represent which cat murdered which pigeon. For example if Mrs. Heaths cat killed Mr. Downs’ pigeon, the variable x_{′Heath′,′Downs′} is true (1).

3. The first two constraints make sure that each cat murders exactly one pigeon and that each pigeon is murdered by exactly one cat.

4. The next constraint expresses the fact that Mr. Downs’ pigeon was killed by Mrs. Heaths cat.

5. A fourth constraint is used to express that Mrs. Downs’ cat killed the pigeon owned by the man who married the owner of the cat which killed Mr. Marsh’s pigeon. We can formulate this as an equivalence: “For each owner p we have: if and only if Downs cat killed the pigeon of owner p then the cat of owner p killed the pigeon of Marsh”.

   

   We can translate this logical equivalence directly into linear equalities as:

   

   (if x_{′Downs′,p} is true then x_{p,′Marsh′} is true, if x_{′Downs′,p} is false then x_{p,′Marsh′} is false.)

1. The last constraint says that Mr. Forest’s pigeon was killed by the cat owned by the lady who married the man whose pigeon was killed by Mrs. Field’s cat. This is similar to the previous constraint.

2. By minimizing all possible victims of Mrs. Forest’s cat, we make sure, that only one answer exists.

model cats "Cats among Pigeons"; 
    set c,p := [Downs Heath Field Forest Marsh] 
      "c stands for cats; p stands for pigeons"; 
    binary variable x{c,p|c<>p}; 
    constraint 
      A{c}: sum{p} x = 1; 
      B{p}: sum{c} x = 1; 
      C: x['Heath','Downs']; 
      D{p}: x['Downs',p] = x[p,'Marsh']; 
      E{p}: x['Field',p] = x[p,'Forest']; 
    for{c} do 
      minimize obj: x['Forest',c]; 
      if(x['Forest',c]) then 
        Write('%s was the owner of the pigeon killed by Mrs. Forests cat.', c); 
      end 
    end 
  end

References