Sunday Times Teaser 2161 – Love Hearts

by Hugh Bradley and Christopher Higgins

Bobby has made a Valentine card for his girlfriend Chin-We.   He drew rows of identical touching circles in a triangular formation as shown below but with more rows.

He then placed a red heart in as many circles as possible without any of these forming equilateral triangles. He continued by placing pink hearts in some of the other circles and white hearts in the remainder.

When he counted the number of hearts of different colours (in no particular order) he obtained three consecutive numbers.

How many red hearts are on the card?

I was reminded of this teaser recently when Jim Randell published a solution for the New Scientist Enigma number 82 on his Enigmatic Code site.

This puzzle is notable because the published answer is wrong.

Considering the three consecutive numbers of hearts first, if we let the centre number of the three be $$x$$, we must then have $$(x-1)+x+(x+1)=3x=r(r + 1)/2$$, where $$r$$ is the number of rows.  Hence the allowed $$x$$ values are $$r(r+1)/6$$, which shows that $$r$$ cannot be 1 mod 3 since $$x$$ would not then be integer.

Equilateral triangles can be formed in alignment with the formation or in inverted form (i.e. rotated 180 degress).   Moreover, although I originally overlooked it, Peter Hayes has pointed out that triangles can also be formed without any of their sides in alignment with the original formation.  My solution, which is described here, now considers all possible equilateral triangles.

The table below shows the number of rows, the possible numbers of red hearts (based on the total number of hearts) and the maximum number of red hearts that can be placed without forming equilateral triangles.

 rows possible values red hearts 5 4, 5, 6 8 6 6, 7, 8 10 7 12 8 11, 12, 13 14 9 14, 15, 16 17 10 20 11 21, 22, 23 22 12 25, 26, 27 25 13 28 14 34, 35, 36 31

Here are some examples of the maximum numbers of red hearts for varying numbers of rows:

It seems likely that the puzzle was set in the belief that the sequence 8, 10, 12, 14, … for 5, 6, 7, 8, .. rows would continue, giving the published answer of 16 in 9 rows. But, as shown above, the next value is 17 and beyond this the first solution is with 22 red hearts.

To obtain these solutions I started with the open source Gnu Linear Programming Kit but the 11 row solution took over 9 hours on my 2GHz i7 machine.  Fortunately, however, the team at Gurobi kindly provided access to their ‘state of the art’ LP solver and this allowed me to extend the coverage up to 13 rows in a reasonable time (the 13 row solution took about 3 hours).   With a 30 hour run I feel fairly sure I could get to 14 rows.  I am really grateful for the assitance that Gurobi provided in this investigation.  Further details are provided here.

Covering older teasers is an amazing activity as I always wished myself to have every single one of them in my teaserr archive , many thanks Brian for your neverending work on teasers world!

2. I can see why Enigma 82 reminded you of this problem, and it can easily be restated in similar terms. If you fill each triangle with a red heart then you want to find the minimum set of hearts to remove, such that each equilateral triangle is “spoilt”.

This code is adapted from my PyMathProg solution to Enigma 82, and uses the same method I used in Enigma 1473 to count the equilateral triangles.

As given it verifies that a triangle with 9 rows does not give a solution in 9s. It’s still running on N=11, which I assume will give the solution to the overall puzzle (of 22 red hearts).

It will be interesting to discover whether there is any major difference in speed in formulating this problem in the different ways.

I actually did better with this back in 2004 than I did recently 🙁 In fact my 2004 model was:

————————————————————————-
param n, integer, in (1..30);
var a{ i in 1..n, j in 1..i }, integer, >= 0, < = 1; maximize tri: sum{i in 1..n, j in 1..i } (a[i,j]); subject to sum{i in 1..n, j in 1..i, k in 1..n-i, m in 0..k-1} : a[i+m,j] + a[i+k,j+m] + a[i+k-m,j+k-m] <= 2; data; param n := 10; end;

————————————————————————-
which enumerates all the equilateral triangles for the constraints in a way that I am now struggling to understand!

• It took 9h39m to run with 11 rows, but confirms that in this situation the maximum number of red hearts is 22, hence this is the smallest solution to the problem.

That is around the same time as it took me so it appears that the different formulations have broadly similar performance. The CPLEX and GUROBI LP solvers would probably do much better but these are commercial solvers with costly licenses (unless you are an academic).

• I wrote a Python script to generate the data for a parameterised GPLK model and ran that directly in glpsol, as I thought it might be faster (it seemed to be for Enigma 82), but it took 17-18 hours to come up with the same answer (22 red hearts). I left it running for a few hours to see what it came up with, but it had only narrowed the solution space down to between 25 and 30 red hearts before I got bored, which doesn’t help much.

Here are some layouts I’ve found so far (if this works…)

The team at Gurobi gave me access ot their solver which I report on here:

https://brg.a2hosted.com/?page_id=882

for the 11 rows problem it is nearly 300 times faster than GLPK.

Nice drawings – did you automate drawing these. If I had realised how many drawings there would be, I think I would have spent some time on this!

• I downloaded lp_solve 5.5 and gave that a go (just having a Python program generate a .lp file) and it can solve the 11 row case in 32m38s (vs. 9h39m for GLPK). Not as fast a Gurobi, but a definite improvement.

3. Yes, the diagrams are generated (which is why there are no hearts on them). I have a simple plotting library that uses the Tk Canvas widget for visualising Enigma solutions, although every time I need it I have to add bits to it. This time I added circles (lines came in Enigma 82 and polygons for Enigma 1718). One day I’ll tidy it up and make it available.

• I should also mention that my program considers a triangle with 2 rows in it to be a degenerate solution to the problem. With 2 red hearts, 1 pink heart and 0 white hearts.