tl;dr: we solve the lollipop problem for \(n=5,6,7,10\), and in the equal radii variant for all \(n\)
Recently, I came across a Numberphile video where Neil Sloane (the creator of the OEIS) talks about the unsolved lollipop problem:
What is the maximum number of regions the plane is divided into by \(n\) lollipops?
So what is a lollipop here? It looks like this:
It consists of a circle and of a ray perpendicular to it, the infinitely long stem of the lollipop. The ray starts at a point on the circle, but does not extend into the interior of the circle. Each lollipop can be of arbitrary size and orientation (the variant where all lollipops have the same size is studied at the end).
The corresponding problems for lines or circles are well-known and not difficult (see for example A014206 and the references therein). But with lollipops it gets much more interesting. The preprint Cutting a Pancake with an Exotic Knife by David Cutler, Jonas Karlsson, and Neil Sloane studies the problem in detail. They investigate many other shapes as well, and the lollipop is among the few ones where the problem is not fully solved yet.
The lollipop problem was also featured in a Christmas posting by Neil Sloane on the SeqFan mailing list. This initiated a lot of progress and eventually led to a complete solution for \(n = 4\). However, like probably many other people, I learned about this nice problem only this weekend from the Numberphile video :-)
For \(n=1,2,3,4\) the lollipop problem is solved and the answers are \(2,10,25,45\), see also A389624. In addition, the aforementioned article by Neil Sloane et al. provides lower and upper bounds for \(n \ge 5\). These are described later in more detail.
On this webpage, I want to explain how one can get even better upper bounds. The improved bounds for \(n = 5,6,7,10\) will imply the optimality of previously known constructions, thus solving the lollipop problem for these four new values of \(n\) and contributing a few terms to A389624. Furthermore, at the end I will give a full solution to the variant with equally-sized lollipops (A396714). The progress can be summarized in the following table:
| standard lollipop problem | equal radii variant | ||
|---|---|---|---|
| \(n\) | lower bound | upper bound | exact answer |
| 1 | 2 | 2 | 2 |
| 2 | 10 | 10 | 10 |
| 3 | 25 | 25 | 25 |
| 4 | 45 | 45 | 44 |
| 5 | 71 | 71 | 70 |
| 6 | 104 | 104 | 103 |
| 7 | 142 | 142 | 140 |
| 8 | 186 | 187 | 184 |
| 9 | 237 | 238 | 235 |
| 10 | 294 | 294 | 290 |
| 11 | 356 | 357 | 352 |
| 12 | 425 | 427 | 421 |
| 13 | 500 | 501 | 494 |
| 14 | 580 | 582 | 574 |
| 15 | 667 | 670 | 661 |
| 16 | 761 | 763 | 752 |
It is funny that we know the answer for \(n=10\), but not yet for \(n=8\) or \(n=9\).
As mentioned by Neil Sloane in the Numberphile video, the number of regions is directly related to the number of intersection points via the formula \[ \#\text{regions} = \#\text{intersections} + n + 1 \] (at least if no three lollipops meet in a single point, which is satisfied by an optimal configuration). So we can maximize the number of intersection points between lollipops instead. This is much easier to handle, since we can just take the sum over all pairs of lollipops.
It is easy to see that two lollipops meet in at most 7 points:
This already gives a rough upper bound of \(7\binom n2\) intersections or \(7\binom n2+n+1\) regions.
And this bound can indeed be reached for \(n=3\), even when restricting to equally-sized lollipops:
For \(n=4\), there is an ingenious construction by Jonas Karlsson: one can add a very tiny fourth lollipop to the previous configuration in such a way that it intersects two lollipops in 7 points and one lollipop in 5 points. This gives 40 intersection points or 45 regions, which is actually optimal (see also the next section). I will not reproduce the picture for \(n=4\), you can find links in the OEIS entry. It is really necessary to use lollipops of different sizes here: the answer with equally-sized lollipops would be 44, as we will see later.
As explained in the article by Neil Sloane et al., one can produce an example with \(n+1\) lollipops from an example with \(n\) lollipops by copying one lollipop and slightly perturbing it. A lollipop has self-intersection number 4, meaning that it intersects a sufficiently small but general perturbation of itself in exactly 4 points. Therefore, if we duplicate a lollipop having \(s\) intersections with other lollipops, we get \(s+4\) new intersections in this way. If we start from Karlsson's \(n=4\) example and choose the duplications in an optimal manner, we arrive at the best currently known lower bounds.
The optimality proof in the article by Neil Sloane et al. for \(n=4\) is based on the following beautiful idea:
If the stem directions of two lollipops differ by at most 90 degrees, the two lollipops meet in at most 5 points.
In fact, the 2 intersections are already lost within the 4 stem-circle intersections (see Lemma 2 on page 42). Clearly, among four directions there are always two which are at most 90 degrees apart, so the improved bound of \(7\binom 42-2\) intersections follows.
More generally, we gain an improvement of \(2a_n\) to the basic upper bound, where \[a_n:=\left\lceil\frac{n(n-3)}6\right\rceil\] are the guaranteed pairs of "similar" directions among \(n\) directions. Unfortunately, this upper bound is not strong enough for \(n\ge5\) to establish the optimality of the known constructions.
Inspired by this approach, the idea is now to consider another property of a pair of lollipops that similarly reduces the number of their intersection points. Unlike the similarity of the stem directions, this one will depend on the circle positions. And again the idea will be that by some kind of Ramsey type argument, there is an abundance of pairs satisfying this property.
The property is the following:
A pair of lollipops is called intriguing if their circles either do not intersect, or if their circles intersect at an angle of at most 90 degrees.
Note that the intersection angle is measured by giving both circles the same orientation (both positive or both negative). For example, the following pair of lollipops is intriguing:
While this one is not:
But this one is:
Let us introduce a word for the stem condition as well:
A pair of lollipops is called close if the angle between their stems is at most 90 degrees.
Now we can observe the following:
The first statement is the lemma from loc. cit., and like in their case, I do not want to write down a formal proof for the second or third statement either. However, it is not too difficult to verify the validity of these geometric statements by drawing a few pictures. For example, in the second statement, if the circles do not meet at all, we already lose 2 intersections there, while if they meet, intriguity implies that the two stem-circle pairs give at most 1 intersection each. The cases in the third statement can be handled similarly: if the circles do not meet at all, we actually lose 2 stem-circle intersections from closeness as well as 2 circle-circle intersections, so we even have at most 3 intersections in this case. And if the circles meet, there are already at most 4 intersections from intriguity alone: in order for both remaining stem-circle intersections to occur, the stems need to be directed outwards from the overlapping region of the two circles, meaning that the stems themselves cannot intersect.
How did I come up with this property? I was trying to construct a 72 region example for \(n=5\) by adding two tiny lollipops to \(n=3\) like in Karlsson's construction, but such that the two tiny ones intersect each other in 7 points. It seemed to be impossible, and while trying to understand why, I came up with this obstruction.
The last step is to show that these pairs with few intersections are forced to occur:
The first statement is obvious and we already talked about it.
The second statement is a bit more tricky to prove. I came up with the following analytic proof, but would be very interested in a more elementary argument.
Suppose we have 5 circles with centers \(x_i\in\mathbb R^2\) and radii \(r_i\gt0\) such that they pairwisely intersect at obtuse angles.
This boils down to the condition \[ r_i^2+r_j^2\lt|x_i-x_j|^2\lt(r_i+r_j)^2 \quad\forall i\ne j \;. \]
Now let us consider the vectors \[ v_i = \frac1{r_i}(1,r_i^2-|x_i|^2,x_i) \in \mathbb R^4 \]
together with the symmetric bilinear form \[ \left<(\alpha,\beta,x),(\alpha',\beta',x')\right> := \frac{\alpha\beta'+\beta\alpha'}2+x\cdot x' \]
on \(\mathbb R^4\), where \(x\cdot x'\) denotes the standard scalar product on \(\mathbb R^2\). It is not difficult to compute that \( \left<v_i,v_i\right>=1 \)
and that our condition translates into \[ -1\lt\left<v_i,v_j\right>\lt0 \quad\forall i\ne j \;. \]
As five vectors in \(\mathbb R^4\) cannot be linearly independent, there exist \(\lambda_1,\ldots,\lambda_5\in\mathbb R\), not all zero, such that \(\sum_i\lambda_i v_i=0\).
Since the first component of each \(v_i\) is positive, there exist positive as well as negative \(\lambda_i\). We may assume that at most two of them are positive, otherwise
replace each \(\lambda_i\) by \(-\lambda_i\). By reordering, we may therefore arrange that \(\lambda_1\gt0\) and \(\lambda_3,\lambda_4,\lambda_5\lt0\) (the sign of \(\lambda_2\) is not known yet).
From
\[ 0 = \left<\sum_i\lambda_i v_i,v_1\right> = \sum_i\lambda_i\left<v_i,v_1\right> \]
we get \(\lambda_1+\lambda_2\left<v_1,v_2\right>\lt0\) (because \(\lambda_i\left<v_i,v_1\right>>0\) for \(i=3,4,5\)) and in particular \(\lambda_2\gt0\).
But then
\[ 0 = \left<\sum_i\lambda_i v_i,v_1+v_2\right> = \sum_i\lambda_i(\left<v_i,v_1\right>+\left<v_i,v_2\right>) \;, \]
while all summands are positive, contradiction!
Proof of the second statement (click to expand)
Having proved these statements, one can deduce purely combinatorially that there are at least \(a_n\) close pairs and at least \(b_n\) intriguing pairs among \(n\) lollipops,
where \[a_n:=\left\lceil\frac{n(n-3)}6\right\rceil\] as before and \[b_n:=\left\lceil\frac{n(n-4)}8\right\rceil \]
(these sequences are shifted versions of A130518 and A130519, respectively).
We proceed by induction on \(n\). Clearly, \(a_4=1\) and \(b_5=1\), and all previous terms vanish.
Let \(c_n\) denote \(a_n\) or \(b_n\).
For the induction step \(n\to n+1\),
observe that every \(n\)-subset of our \(n+1\) lollipops contains \(c_n\) pairs with the desired property.
Since every pair is counted at most \(n-1\) times, we get at least \[ \left\lceil \frac{(n+1)c_n}{n-1} \right\rceil \] pairs with the property.
So it suffices to show that the positive values of \(c_n\) satisfy the recursion
\[ c_{n+1} = \left\lceil \frac{(n+1)c_n}{n-1} \right\rceil \;, \]
which can be verified for \(a_n\) and \(b_n\) by direct computations.
Proof of this claim (click to expand)
Now we are ready to put everything together and arrive at an improved upper bound for the number of intersection points between \(n\) lollipops. Each close pair of lollipops reduces the \(7\binom n2\) bound by 2, and each intriguing pair further reduces the bound by at least 1: the maximum number of intersections for this pair either goes down from 7 to 5 (if it is intriguing but not close) or from 5 to 4 (if it is both intriguing and close). Therefore, there are at most \(7\binom n2-2a_n-b_n\) intersections. This can be rephrased as follows:
Theorem. The plane is divided by \(n\) lollipops into at most \[ \frac{7n(n-1)}2-2\left\lceil\frac{n(n-3)}6\right\rceil-\left\lceil\frac{n(n-4)}8\right\rceil+n+1 \] regions.
Comparing this with the known lower bounds outlined at the beginning, we obtain the table above. In consequence, the lollipop problem is currently solved for \(n\le7\) and \(n=10\). Also note that our upper bound is in \(\left(3+\frac{1}{24}\right)n^2+O(n)\), while the lower bound can be shown to be in \(\left(3+\frac{1}{32}\right)n^2+O(n)\), which is very close.
When learning about the lollipop problem, many people (including me) wonder what happens if we assume that the radii of the circles are all equal, so that the lollipops are congruent to each other. It turns out that this variant of the question is much easier to answer: the method from above gives a full solution to the problem in this case. Namely, we can strengthen the statement
Among 5 lollipops, there is always an intriguing pair.in our previous argument to
Among 4 equally-sized lollipops, there is always an intriguing pair.
And the proof is much shorter: if we denote the circles' common radius by \(r\), then our earlier condition for no intriguing pairs to exist just says that all distances between two circle centers are strictly larger than \(r\sqrt2\) and strictly smaller than \(2r\). However, this is impossible: it is known that the ratio between the largest and the smallest distance among four points in the plane is at least \(\sqrt2\).
Hence, we get an upper bound of \(7\binom n2-3a_n\) for the number of intersections between \(n\) equally-sized lollipops. But these are exactly (I omit some tedious calculations here) the number of intersections you get if you start with an optimal configuration of three equally-sized lollipops (see the picture at the beginning) and replace the \(i\)-th lollipop for \(i=1,2,3\) with \(n_i\) slightly perturbed copies of itself (of course without changing their size) where \(n=n_1+n_2+n_3\) is the "most uniform" partition of \(n\), i.e. \(n_1=n_2=\left\lfloor\frac{n+1}3\right\rfloor\) and \(n_3=n-n_1-n_2\). So here is the theorem:
Theorem. The maximum number of regions the plane is divided into by \(n\) congruent lollipops is exactly \[ \frac{7n(n-1)}2-3\left\lceil\frac{n(n-3)}6\right\rceil+n+1 \;. \]
Update (2026-06-04): This is A396714 now.