Moving Coins (triangle)

Run LPL Code  ,  PDF Document

Problem

Figure 1 displays 10 coins arranged in a triangle pointing to the top. Arrange the coins in a triangle such that it is pointing down by moving as few coins as possible.

---

---

Modeling Steps

We introduce a grid of n×n grid points. Let the coins be positioned on the grid points. Let a_i,j with i,j ∈{1…n} be a 0-1 matrix, such that a_i,j = 1 if and only if (i,j) is initially occupied by a coin. A possible matrix is displayed in Table 1 (we set n = 20 and put the triangle in the middle of the given 20 × 20 grid – all grid points outside the table are zero). We define the variables and constraints as follows:

1. We define a binary variable x_i,j with the following meaning: x_i,j = 1 (is true) if and only if a coin is placed at the grid position (i,j) in the final layout (a triangle pointing down).

2. The first constraint is as follows: The number of the coins cannot change, hence:

   

3. Let a particular grid point (i,j) with i ≥ 4 and j ≥ 4 be the bottom corner in the final triangle, then (if we count from top j = 1 to bottom j = n) the following expression must be true (this corresponds to a triangle pointing down):

   

4. The constraint now is as follows: At least one of all K_i,j with i,j ≥ 4 must be true. That is:

   

5. The objective is to move as few coins as possible. This can be expressed by the objective function maximizing the number of coins that remain at their initial position:

   

model triangle "Moving Coins"; 
    set i,j:=[1..20]; 
    parameter a{i,j}:=[(8,10)=1 (7,11)=1 (9,11)=1 (6,12)=1 
      (8,12)=1 (10,12)=1 (5,13)=1 (7,13)=1 (9,13)=1 (11,13)=1]; 
    binary variable x{i,j}; 
    constraint R: sum{i,j} x = sum{i,j} a; 
    constraint S: or{i,j|j>=4 and i>=4} 
     (x[i,j] and x[i-1,j-1] and x[i+1,j-1] and 
      x[i-2,j-2] and x[i,j-2] and x[i+2,j-2] and 
      x[i-3,j-3] and x[i-1,j-3] and x[i+1,j-3] and x[i+3,j-3]); 
    maximize obj: sum{i,j|a} x; 
    Draw.Scale(50,70); 
    for{i,j|a} do Draw.Circle(i,j,.5,2,0,3); end 
    for{i,j|a} do Draw.Circle('1$',i,j,.4,-1,0,1); end 
    for{i,j|x and ~a} do Draw.Circle('1$',i,j,.4,Rgb(240,240,240),3,1); end 
    for{i,j|~x and a} do Draw.Circle('$',i,j,.4,Rgb(240,240,240),3,1); end 
  end

Solution

The objective value is 7, that means we only need to move 3 coins, since 7 keep their place. In the Figure 2 the coins that are filled with a light color have to be moved to a position with a light border coin position.

---

---

Further Comments

The problem is easy to solve if you have the “right” look. Concentrate on the red (dark-grey) hexagon in the middle of the triangle (see Figure 3). One can see that all the coins inside the hexagon do not need to be moved. Only the three coins outside the hexagon must be moved appropriately. It is not so easy to see that 3 is indeed the minimal number of coins to be moved. For that we had to build and solve the mathematical model.

To prove this, the mathematical model suggests another (simpler) way to solve the problem in polynomial time: Draw the original triangle as shown in Figure 1 On a piece of paper. Make a copy on a transparency and turn the transparency upside down, such that the triangle on the transparency is pointing down. Now put the transparency on top of the up-pointing triangle. Move the bottom circle to every position 4 ≤ i,j ≤ n and count each time the overlapping number of coins with the initial (up pointing) triangle. Keep the position that had the maximal overlapping. I am sure the reader can write a program for this! And it shows that the problem can be solved in polynomial time. We do not need integer programming for this problem and it can be solved much more efficiently.

---

---

Questions

1. A triangle of 10 coins needs a minimum of 3 moves. What about a triangle of 15 coins (add another line of 5 coins at the bottom) ?

2. How many moves do you need at least for a triangle of 21 coins (add another line of 6 coins) ?

3. Can you generalize your observation ?

4. Build a mathematical model that generalizes the triangle to any row of coins.

Answers

1. Minimally 5 coins must be moved.

2. 7 coins al least must be moved

3. For every row 2 additional coins must be moved. Hence, in a triangle with n rows, the number of coins C to be moved is at least:

   

4. A triangle with 4 rows has 10 coins, with 5 rows it has 15 coins, and for n rows it has:

   

   A general model can be downloaded here: triangle1.

References