Arrange ten coins in a bowling formation. Fewest pennies to remove so no three pennies that remain have centers that form an equilateral triangle?

Question

Arrange ten coins in the familiar ten-pin bowling formation (see figure). What is the smallest number of pennies you must remove so that no equilateral triangle, of any size, will have its three corners marked by the centers of three pennies that remain? Not counting rotations and reflections as different, there is only one pattern for the removal of the minimum number of pennies.
Note that the original pattern contains two equilateral triangles that are tipped so that their bases are not horizontal.

Give also a simple proof that your answer is minimal.

This problem (without the request for a proof) is from Martin Gardner's "The Colossal Book of Short Puzzles and Problems".

---

Answer 1

Note there are 15 equilateral triangles. If we label the pennies A through J going from left to right and then row by row, they are ABC, BDE, CEF, DGH, EHI, FIJ, BCE, DEH, EFI, ADF, BGI, CHJ, AGJ, BFH, and CDI.

Note that AGJ, BFH, and CDI do not share any pennies, so we need to remove at least one penny from each of those sets. Also note that no matter which three we remove from those sets, some triangle with E will be left behind. Therefore we must remove at least four pennies.

One possible way to do this (the only possible way, if you ignore rotations) is to remove A, E, H, and I.

Answer 2

Not a proof, but if you look at it as a satisfiability problem, Z3 (SMT solver) can be of some help here:

from z3 import *

o = Optimize()

# Let's number the pins from 0 to 9, it's much easier that way
# A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7, I = 8, 
# J = 9
pins = [Bool("%d" % i) for i in range(0, 10)]

# Since there are 15 equilateral triangles, let's 
# add them as constraints to be solved
o.add(And(Or(pins[0], pins[1], pins[2]),
    Or(pins[1], pins[3], pins[4]),
    Or(pins[2], pins[4], pins[5]),
    Or(pins[3], pins[6], pins[7]),
    Or(pins[4], pins[7], pins[8]),
    Or(pins[5], pins[8], pins[9]),
    Or(pins[4], pins[1], pins[2]),
    Or(pins[7], pins[3], pins[4]),
    Or(pins[8], pins[4], pins[5]),
    Or(pins[0], pins[6], pins[9]),
    Or(pins[1], pins[6], pins[8]),
    Or(pins[2], pins[7], pins[9]),
    Or(pins[0], pins[3], pins[5]),
    Or(pins[3], pins[2], pins[8]),
    Or(pins[5], pins[1], pins[7])))

# minimize takes a variable, so let's pass 
# in sum since we can't pass the entire list
o.minimize(Sum(pins))

# check for satisfiability and 
# get the pins to be removed if it
# is satisfiable
if o.check() == sat:
    # Get the model
    m = o.model()
    # Print the number of pins to be removed
    print("The number of pins to be removed is %s" % str((m.evaluate(Sum(pins)))))
    # Print the pins to be removed
    print("The pins to be removed are: ", end="")
    for i in range(0, 10):
        if m.evaluate(pins[i]) == True:
            print("%d" % i, end=" ")
    print()
else:
    print("The problem is unsatisfiable")

This spits out:

The number of pins to be removed is 4
The pins to be removed are: 0 4 7 8

Which is the same as A, E, H, and I if you map 0 to A, 1 to B, and so on.

Answer 3

In any case, at least 3 coins must be removed because the 3 smallest triangles that can be formed with the corner coins don't intersect with each other, so we can do no less than removing 1 from each of these triangles. But is 3 enough?

The hexagonal part in the center contains at least one triangle as long as the coin in the middle is kept and there are two neighboring coins on its "edges". If we remove only 3 coins from the corner triangles, we end up either leaving the 3 outermost coins untouched or removing less than 3 of the coins on the hexagon's edges, both of which are unwanted consequences.

Since there are 15 triangles, eliminating 6 of them by taking the central one out would be a good move. The remaining triangles always rely on an outermost coin, so we can reach our goal by later taking out all 3.