brainwagon

Comment from Tim
Time 8/24/2009 at 4:43 am

SPOILERS AHEAD! (Assuming you are not allowed to move any of the coins…)

Here’s my reasoning, by considering cases. It would be nice if there was a neater way of proving it.

There are 12 equilateral triangles to hit, of 4 different sizes. If we start by removing the centre circle first, or a corner circle, we still need to remove 3 more to hit all the small triangles. If we start by removing one of the other 6 circles there is exactly one way of hitting all the remaining small triangles by removing just 2 more circles, but this leaves one intermediate size triangle. So we must have to remove at least 4 circles.

It’s a nice puzzle. What surprised me is that there is only one solution (allowing for symmetry) for the case of removing 4 circles. I had to use some python code to convince myself of this.

Comment from Alan Yates
Time 8/24/2009 at 6:27 am

Mark,

Damn, I’ve spent hours on this tonight – interesting problem.

I’ve taken what may be an unusual/crazy approach, because of the 3-fold symmetry I defined a 3-tuple coordinate system to name each vertex and wrote some code to generate valid vertex sets for triangles numbers of order N, i.e:

1: (0,0,0)
2: (0,1,1) (1,0,1) (1,1,0)
3: (0,2,2) (1,1,2) (1,2,1) (2,0,2) (2,1,1) (2,2,0)
4: (0,3,3) (1,2,3) (1,3,2) (2,1,3) (2,2,2) (2,3,1) (3,0,3) (3,1,2) (3,2,1) (3,3,0)
etc

I can’t seem to prove it, but it looks very likely that if you construct a graph of all the equilateral triangles such that each is defined by 3 directed edges forming a cycle then removing vertices (and associated edges) until there are no more 3-cycles finds cases where there are no triangles formed by the vertices.

OK, that is worded poorly, but the edge sets of my construction for the trivial 2nd and 3rd order cases are:

{(0,1,1)->(1,1,0)}
{(1,0,1)->(0,1,1)}
{(1,1,0)->(1,0,1)}

and

{(0,2,2)->(1,2,1)}
{(0,2,2)->(2,2,0)}
{(1,1,2)->(2,1,1)}
{(1,1,2)->(0,2,2)}
{(1,2,1)->(2,2,0)}
{(1,2,1)->(1,1,2)}
{(2,0,2)->(1,1,2)}
{(2,0,2)->(0,2,2)}
{(2,1,1)->(2,0,2)}
{(2,1,1)->(1,2,1)}
{(2,2,0)->(2,1,1)}
{(2,2,0)->(2,0,2)}

It is pretty obvious by inspection for those cases that the minimum vertex removals are 1 and 2 respectively. At the 4th order things get a lot tougher as there are more than 200 4-removals.

There is an obvious 4-removal for the 4th order case but I can’t see any obvious 3-removals – maybe its just too late in the evening. I could extend the code to exhaustively document all possible removals to find the minimum, as long as my assumption that the 3-cycle nature of these constructed graphs is indeed a valid test of equilateral triangle presence.

The graph construction algorithm does hint at a “remove at least 1 vertex an integer distance along any axis from each vertex” algorithm for constructing vertex sets that don’t describe any triangles. I dunno if that could be bashed into a proof…

Anyway, enough for tonight, I’ll try some more tomorrow.

Regards,
Alan

Comment from Mark VandeWettering
Time 8/24/2009 at 7:55 am

To verify my solution, I wrote a little Python that took a list of coin removals, and verified that the resulting pattern had no equilateral triangles in it. I then simply tested it against all the 1024 possible set of removals, and verified that my guess was amongst the shortest of the winners. It was indeed.

I suspect that someone more versed in graph theory could map this to a more famous math question. I think Alan is on the right track. Let’s say we number the vertices starting with zero from the lower left, going to three across the bottom, then four in the next row and so on up to 8, then the biggest triangle is [0, 3, 8], and the [0, 1, 4] is one of the smallest, then we are looking for the shortest list of coordinates [x₀, x₁ …] so that at least one x is in each of the triangles.

Comment from Alan Yates
Time 8/24/2009 at 7:24 pm

Mark,

I hit upon a different and perhaps better approach in the middle of the night (as always). Using the same coordinate system I decided to define something I am calling the “participation number” for each vertex. It represents the number of triangles that the vertex is part of and can be computed by counting the number of pairs of vertices at the same distance in each of the 6 directions from the reference vertex. This can be expressed by defining basis vectors for my coordinate system then taking them in pairs and spanning them using a free parameter that takes values from [-N:N] but not 0. (I used 6 pairs initially and the parameter [1:N] instead).

You can think of this participation number as the count of the 3-hyperedges connecting a vertex to its corresponding equilateral vertices. It will become 0 for all vertices when no triangles are described by the current vertices placement.

The initial placement of the vertices can be achieved by using vertex coordinates (i,j,k) such that i, j, and k are elements of [0:N-1] and i+j+k == 2(N-1).

While there are vertices with non-zero participation number remove the highest participant vertex.

There will often be 3k highest participant vertices because of symmetry, you can try each but it appears the result is always a symmetric solution – haven’t proven that however, especially for higher orders. The algorithm finds removals that yield no triangles. I can’t seem to prove it finds the minimum.

I’ll code this up when I get a chance and try higher orders. For each vertex the naive algorithm needs to check for the existence of 6(N-1) vertices, but less if it knows about the relative boundaries of the current vertex and placement.

Here is a sketch I made this morning on the ferry to explain my coordinate system:

nexus.cable.nu/junk/triangle-problem-sketch.jpg

Very interesting problem Mark. It cost me some sleep, but it is a lot of fun – thanks! Still no closer to anything but a brute-force proof of minimalism though.

Regards,
Alan

PS: does your comment system silently drop posts, perhaps those with URLs in the body? Or have I just filled your moderation queue? I didn’t get any feedback with the first post so I wasn’t sure what happened.

Comment from Mark VandeWettering
Time 8/24/2009 at 8:37 pm

Most of the time, posts with no links are immediately available. If there are links, they often enter a moderation queue, and I’ll have to approve them (normally, that’s within 12 hours or so). Nothing should get dropped.

I’ve been thinking about this problem a bit more: I think it is an instance of the so called exact cover problem, which is known to be NP-complete, perhaps generate and test is about as good as we can arrange, with an expontential runtime. Still, it seems like it is a good candidate for solution via Knuth’s Dancing Links technique, which I’ve always meant to implement, but never gotten around to. But it’s a bit more work than I feel like doing at the moment. I think I have the solution for the n=5 case (which interestingly enough is also unique except for rotational symmetry) and n=6 (which is not). I doubt my current program will scale well enough to reach the n=7 case.

Comment from Roger Walter
Time 5/29/2011 at 8:31 pm

Sorry, Tim, there are at least two different solutions. start with the biggest triangle, and remove one circle, let’s say the top one. Clearly this MUST be removed. This leaves two intermediate triangles, (and 8 small triangles) which have no points in common. Two more points MUST be removed, but as the most small triangles each of these can take out is three, one further (fourth) point is required. There is your proof, Alan. Off the top of my head, one solution is to remove the center circle and all three corner circles. Another different solution is to remove the top circle, the middle circle, and the middle two of the bottom row.

It depends on how you approach it, but a bright junior maths student could come up with this simple solution.