6
$\begingroup$

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.

enter image description here

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


$\endgroup$
9
  • $\begingroup$ What does this mean: will have its three corners marked by the centers of three pennies that remain? $\endgroup$
    – warspyking
    Sep 9, 2015 at 19:47
  • 1
    $\begingroup$ Although my guess is 3. $\endgroup$
    – warspyking
    Sep 9, 2015 at 19:47
  • $\begingroup$ @warspyking It just means that no equilateral triangle is formed by any three of the pennies that are left. $\endgroup$
    – Luke
    Sep 9, 2015 at 19:49
  • $\begingroup$ so 4 pennies, corners and center ? $\endgroup$
    – moonbutt74
    Sep 9, 2015 at 19:50
  • $\begingroup$ The answer's 3. If you notice 6 pennies surround the center penny. Remove every second one starting from the up left going clockwise. $\endgroup$
    – warspyking
    Sep 9, 2015 at 19:52

3 Answers 3

6
$\begingroup$

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.

enter image description here

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.

$\endgroup$
8
  • $\begingroup$ Hmm, I got 15 triangles. BCE and 2 friends are missing. $\endgroup$
    – Sleafar
    Sep 9, 2015 at 20:02
  • $\begingroup$ Dang, you're right! $\endgroup$
    – Luke
    Sep 9, 2015 at 20:10
  • 1
    $\begingroup$ Fixed, I think the logic still holds. $\endgroup$
    – Luke
    Sep 9, 2015 at 20:14
  • 4
    $\begingroup$ A simple explanation that 4 are required: one of AGJ must go, so pick A. Now, you are left with 3 non-overlapping triangles, BCE, DGH, and FIJ. So you must remove at least 3 more, so the minimum to remove is 4. Removing A,E,H,I works, so 4 is the solution. $\endgroup$ Sep 9, 2015 at 21:51
  • 1
    $\begingroup$ @numberknot That leaves behind BFH and CDI. $\endgroup$
    – Luke
    Sep 10, 2015 at 11:36
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If you replace the disjunctions with linear "cover" constraints of the form $\text{pins}_i+\text{pins}_j+\text{pins}_k \ge 1$, the linear programming relaxation yields a minimum of $10/3$, and the dual variables provide a short certificate of optimality. $\endgroup$
    – RobPratt
    Sep 27, 2022 at 14:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.