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".

  • $\begingroup$ What does this mean: will have its three corners marked by the centers of three pennies that remain? $\endgroup$ – warspyking Sep 9 '15 at 19:47
  • 1
    $\begingroup$ Although my guess is 3. $\endgroup$ – warspyking Sep 9 '15 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 '15 at 19:49
  • $\begingroup$ so 4 pennies, corners and center ? $\endgroup$ – moonbutt74 Sep 9 '15 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 '15 at 19:52

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.

  • $\begingroup$ Hmm, I got 15 triangles. BCE and 2 friends are missing. $\endgroup$ – Sleafar Sep 9 '15 at 20:02
  • $\begingroup$ Dang, you're right! $\endgroup$ – Luke Sep 9 '15 at 20:10
  • 1
    $\begingroup$ Fixed, I think the logic still holds. $\endgroup$ – Luke Sep 9 '15 at 20:14
  • 3
    $\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$ – user3294068 Sep 9 '15 at 21:51
  • 1
    $\begingroup$ @numberknot That leaves behind BFH and CDI. $\endgroup$ – Luke Sep 10 '15 at 11:36

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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