Teaser 2161: Love hearts
From The Sunday Times, 15th February 2004 [link]
Bobby has made a Valentine’s card for his girlfriend Chin-We. He drew some increasing rows of touching circles, like those shown, but with more rows. Then he put a red heart in as many circles as possible without three of their centres forming an equilateral triangle. Then he put a pink heart in some of the remaining circles, and a white heart in the rest.
When Bobby counted the number of hearts of red, of pink and of white, he got three totals which (not necessarily in that order) formed three consecutive numbers.
How many red hearts are on the card?
Although the puzzle can be solved, the published solution was incorrect, and there are in fact two possible correct answers.
[teaser2161]
Frits and 
GeoffR, 
Hugh Casement, and 
John Crabtree and 
S2T2 
Jim Randell 10:13 am on 9 April 2023 Permalink |
I recently revisited Enigma 82 and Enigma 144 and this puzzle can also be solved using similar techniques.
The number of cells for an arrangement with n rows is obviously tri(n).
And if the number of red, pink and white hearts are {k − 1, k, k + 1} (in some order), then we can only find a solution when:
And so we can skip cases where tri(n) is not divisible by 3, i.e. n = 4, 7, 10, 13, …
Once we calculate the possible configurations that give equilateral triangles we can determine a minimum hitting set for these configurations, and all the remaining cells can then be coloured red without giving a configuration that has three reds forming an equilateral triangle, and this is the maximum possible number of reds.
If this number in in the set {k − 1, k, k + 1} then we have a viable solution, and the cells that form the hitting set can be divided into an appropriate number of pink and white cells.
This Python program uses the MiniZinc implementation of the minimum hitting set problem and can be used to examine the puzzle for various values of n. The first solution presents itself at n = 11, which the program solves in 3m35s (using the “scip” solver).
from enigma import (irange, subsets, div, empty, arg, printf) from utils_mzn import hitting_set # distance metric (cosine rule) # returns the square of the distance def dist(p, q): ((px, py), (qx, qy)) = (p, q) (a, b) = (abs(px - qx), abs(py - qy)) c = (1 if (px < qx) != (py < qy) else -1) return a * a + b * b - a * b * c # specify number of rows N = arg(9, 0, int) # enumerate the cells n = N - 1 vs = set((a, b) for a in irange(0, n) for b in irange(0, n - a)) # find the set of equilateral triangles tris = set() for (a, b, c) in subsets(vs, size=3): # is the triangle equilateral if dist(a, b) == dist(b, c) == dist(a, c): tris.add((a, b, c)) T = len(vs) t = len(tris) x = div(T, 3) ss = ({x - 1, x, x + 1} if x is not None else empty) printf("[N={N} -> {T} cells, {t} equilateral triangles, sequence = {ss}]", ss=sorted(ss)) # find a minimum hitting set for the equilateral triangles hs = hitting_set(tris, solver="minizinc --solver scip") printf("minimum hitting set size = {n}", n=len(hs)) r = T - len(hs) # max number of red hearts printf("maximum red hearts = {r}") printf("*** {x}SOLUTION ***", x=('' if r in ss else 'NOT A '))Solution: The smallest solution has 22 red hearts (with 11 rows of circles), but 25 red hearts is also possible (with 12 rows of circles).
The numbers in
seqappear to be growing more rapidly than the numbers inr, so it seems likely these are the only solutions.The solution at n = 2 is disallowed as the puzzle text implies that n > 3 (and also as it requires one of the colours to have no corresponding cells).
Here are some example maximal layouts for various n values:
The published solution is that there were 16 red hearts.
And so the numbers of red, pink, white hearts must be 14, 15, 16 to make a total of 45 cells, hence the arrangement has 9 rows.
However, as we have seen above, the maximum number red hearts for an arrangement with 9 rows is actually 17, so we do not get a solution at n = 9.
It is possible that the setter(s) assumed that the “inverted-V” shape that we see in solutions for n = 4, 5, 6, which gives a solution with 2(n − 1) red cells, would provide a maximal solution for larger n.
LikeLike
Frits 8:49 pm on 15 April 2023 Permalink |
@Jim,
I had a look at [ http://www.hakank.org/minizinc/hitting_set.mzn ] and tried the N=11 case in the MiniZinc program.
Your model ran for 10 min 52 secs:
The model with predicate hitting_set ran for 6 min 20 secs:
solve :: int_search(x, most_constrained, indomain_min, complete) minimize k; .... n = 715; v = [ {52, 61, 54}, {9, 29, 21}, .... {9, 2, 58} ];I guess it’s the “exists” statement in the predicate hitting_set that makes the difference.
LikeLike
Jim Randell 12:04 pm on 16 April 2023 Permalink |
@Frits: Thanks for the link. I did some tests (with MiniZinc 2.7.2), but found that in general my original formulation ran slightly faster than hakank’s model.
However, I did download the “scip” solver, and found that it was able to solve the N=11 case in 3m15s, and the N=12 case in just 29m.
LikeLike
Jim Randell 11:58 am on 5 May 2023 Permalink |
It is possible to install commercial solvers that integrate with MiniZinc and are able to use multiple CPUs.
The CPLEX solver can be installed from IBM (registration required), and this enables the
cplexsolver in MiniZinc (you may need to tell it where CPLEX is using the--cplex-dllparameter). You can then use the--parallel <n>parameter to enable multithreading.The free version of CPLEX is limited to models with 1000 variables/constraints, but this is sufficient for this problem up to N = 11, which is where the first solution is found. I found CPLEX could solve this using 4 threads in an elapsed time of 42.6s.
Installing the
gurobipypackage viapipprovides a license to use the Gurobi solver for models with up to 2000 variables/constraints. This is a bit trickier as the free version doesn’t integrate directly with MiniZinc, but I wrote a utils_gurobi.py module to provide the same interface viagurobipy.It solves (using 8 threads) the N = 11 case in 22.5s, and the N = 12 case in 9m07s, and the N = 13 case in 2h41m. And it should be able to do the N = 14 case.
The Gurobi solver uses more CPU time than the (single-threaded) SCIP solver, but because it is able to use multiple CPUs the elapsed time is shorter.
LikeLike
Jim Randell 2:09 pm on 12 May 2023 Permalink |
Update: I ran the N = 14 case using the Gurobi solver. It took >161 hours (elapsed time), and used >750 hours total CPU time, a lot of RAM, and basically tied up my machine for a week.
The size of the minimum hitting set is 74, which means the maximum number of red hearts is 31.
The configuration found looks like this:
LikeLike
Frits 4:57 pm on 12 May 2023 Permalink |
@Jim, are you going to publish utils_gurobi.py?
LikeLike
Jim Randell 12:16 am on 13 May 2023 Permalink |
@Frits: Certainly.
I’ve put it up here. [@github] (or [@replit])
LikeLike
Frits 2:14 pm on 13 May 2023 Permalink |
Or calling print_triangle(hs) for a graphical representation.
def print_triangle(s): # from top to bottom for r in range(N - 1, -1, -1): # in row r only (N - r) elements may be printed print(((r // 2) * " " + (" " if r % 2 else "")), end=" ") for c in range(N - r): print("." if (r, c) in s else "R", end=" ") print()LikeLike