Move Over Ed McMahon, It's Retsy Boss's Star Search

When designing her new nation’s flag, Retsy Boss wanted to compactly arrange some stars. These stars were positioned along a square grid, but she only wanted to include stars whose centers were at most two units away from some point on the plane.

For example, if she had centered the circle on a star itself, then she could have placed a total of 13 stars on the flag, as shown below:

What is the greatest number of stars Retsy could have placed on the flag?

Let's define the function $N(h,k,R)$ to be the number of integer lattice points within distance $R$ of the point $(h,k) \in \mathbb{R}^2,$ in particular, we have $$N(h,k,R) = \# \left\{ (m,n) \in \mathbb{Z}^2 \mid (m-h)^2 + (n-k)^2 \leq R^2 \right\}.$$ If we have a fixed value of $k,$ let's say, then we see will have $$\eta_n(h,k,R) = \left\lfloor \sqrt{R^2 - (n-k)^2} + h \right\rfloor + \left\lfloor \sqrt{R^2 - (n-k)^2} - h \right\rfloor + 1,$$ where for clarity $\lfloor x \rfloor = \max \{ n \in \mathbb{Z} \mid n \leq x \}$ and in particular $\lfloor x \rfloor = -1$ for $x \in [-1,0).$ So in particular, we have $$N(h,k,R) = \sum_{n=-\lfloor R - k \rfloor}^{\lfloor R + k \rfloor} \eta_n (h,k,R).$$ We see for instance, that when $h=k=0$ and $R=2,$ that we indeed recover $\eta_{-2}(0,0,2) = \eta_2(0,0,2) = 1, \eta_{-1}(0,0,2) = \eta_1(0,0,2) = 3,$ and $\eta_0 (0,0,2)= 5,$ so we have $$N(0,0,2) = \sum_{n=-2}^2 \eta_n(0,0,2) = 1 + 3 + 5 + 3 + 1 = 13.$$

Now, since we also see that everything is periodic and symmetric, in order to solve Retsy's problem we only need to find $$N^* = \max \left\{ N(h,k,2) \mid 0 \leq k \leq h \leq \frac{1}{2} \right\},$$ since everything else in the unit square will can be recovered from this region and everything else in the plane is periodic so $N(h,k,2) = N([h], [k],2),$ for all $(h,k) \in \mathbb{R}^2,$ where $[x] = x - \lfloor x \rfloor$ is the fractional part function.

We can code this up in the following Python code to explore the phase space and empirically determine $N^*$:

 

import math

import numpy as np

​

def _stars(h, k, R):

    num = 0

    lst_y = list(range(-math.floor(R-k), math.floor(R+k)+1))

    for y in lst_y:

        root = math.sqrt(R*R - (y-k)*(y-k))

        num += math.floor(root + h) + math.floor(root - h) + 1

    return num

​

def stars(h, k, R):

    tmph = h.copy()

    tmpk = k.copy()

    shape = h.shape

    if len(shape) == 1:

        shape = (shape[0],1)

    out = np.zeros(shape=shape)

    tmph.resize(shape)

    tmpk.resize(shape)

    for i in range(shape[0]):

        for j in range(shape[1]):

            out[i,j] = _stars(tmph[i,j], tmpk[i,j], R)

    return out

Using this Python code, we can plot the following contour plot, which shows that anywhere in the dark blue region produces the the largest possible number of stars that Retsy could place on the flag is $N^*=14.$ In particular, we can take the point $(h,k) = (0.5, 0.125)$ for foreshadowing purposes and explicitly compute that \begin{align*} \eta_{-1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-1-0.125)^2 } - 0.5 \rfloor + 1 \\ &\quad = \lfloor 1.654\dots + 0.5 \rfloor + \lfloor 1.654\dots - 0.5 \rfloor + 1 = 4\\ \eta_{0}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.996\dots + 0.5 \rfloor + \lfloor 1.996\dots - 0.5 \rfloor + 1 = 4\\ \eta_{1}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (1-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (1-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 1.798\dots + 0.5 \rfloor + \lfloor 1.798\dots - 0.5 \rfloor + 1 = 4\\ \eta_{2}(0.5,0.125,2) &= \lfloor \sqrt{ 4 - (2-0.125)^2 } + 0.5 \rfloor + \lfloor \sqrt{ 4 - (2-0.125)^2 } - 0.5 \rfloor + 1\\ &\quad =\lfloor 0.696\dots + 0.5 \rfloor + \lfloor 0.696\dots - 0.5 \rfloor + 1 = 2\end{align*} so that $$N(0.5,0.125,2)=N^*=4+4+4+2=14.$$