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?
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|
|8||11, 12, 13||14|
|9||14, 15, 16||17|
|11||21, 22, 23||22|
|12||25, 26, 27||25|
|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.