Can You Fit the Stars on the Flag?

This is the Fiddler on the Proof problem verbatim from 6/3/2026.

“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?”

The function that will inevitibly be built will address the extra credit, so here is that problem verbatim as well.

“After 250 years, the nation has commissioned Retsy Boss VIII to design a new flag with one star for each of the nation’s current 58 states. As an homage to the original flag design, Retsy wants to select 58 stars from the square grid that are all at most some distance R from a point on the plane.

What is the minimum distance R that Retsy can use?”

Solution

Working off of the picture above, let’s assume that center star is at the origin (0,0) of the Cartesian plane. Let’s build a function that counts the number of integer pair points (a,b) that are contained in a circle of radius r. Note that we’ll only have to examine centers that are located in the sqaure defined by the diagonal (0,0) to (1/2, 1/2) since centers in other parts of the square with the (0,0) to (1,1) diagonal are vertical or horizontal reflections (or both).

Note that a circle of radius r with center (a,b) will take on the following form: \[ (x-a)^2 + (y-b)^2 = r^2 \]

The Functions

The following function was created to take a radius and center of a circle as input and produce the number of stars that this particular circle will encompass as output.

# inputs are radius of circle r and center of circle (a, b) (default to origin)
# output will be the number of stars in that circle
stars <- function(r, a = 0, b = 0) {
  ## create a grid of possible integer points
  xs <- ceiling(a - r):floor(a + r)
  ys <- ceiling(b - r):floor(b + r)
  pts <- expand.grid(x = xs, y = ys)
  
  # return the count of the points that satisfy the condition of being
  # encompassed by the circle
  sum((pts$x - a)^2 + (pts$y - b)^2 <= r^2)
}

stars(2, 0, 0)
## [1] 13

As we can see, it does spit out the result from the picture given in the problem statement.

Now, let’s build a function that will take as input a circle of radius r and output the maximum number of stars that a circle of that radius can cover.

# input radius r and a step (default .005) used to build the grid of points to 
# check inside the [0, 0.5] x [0, 0.5] square. 
maxStars <- function(r, step = 0.005) {
  centers <- expand.grid(
    a = seq(0, 0.5, by = step),
    b = seq(0, 0.5, by = step)
  )

  xs <- ceiling(-r):floor(0.5 + r)
  ys <- ceiling(-r):floor(0.5 + r)
  pts <- expand.grid(x = xs, y = ys)

  r2 <- r^2

  counts <- vapply(seq_len(nrow(centers)), function(i) {
    a <- centers$a[i]
    b <- centers$b[i]

    sum((pts$x - a)^2 + (pts$y - b)^2 <= r2)
  }, integer(1))

  max(counts)
}

maxStars(2)
## [1] 14

For a radius of 2, we can only improve to 14 stars. However, I’m interested in the minimum radius it takes to get 14 stars as well as 15. Oh, and of course, we want to know it for 58 as well.

Optimization of Radius

For a target number of stars, let’s build a function that will find the minimum radius building off of what we have created thus far.

# input the number of stars, a step with which to create the grid.
# An approximate r will be found using the square root of the number of starts
# over pi. A margin will be added to this.  For larger numbers of stars, 
# this margin should be increased logrithmically. 

minRadiusForStars <- function(numStars, step = 0.005, margin = 2) {
  centers <- expand.grid(
    a = seq(0, 0.5, by = step),
    b = seq(0, 0.5, by = step)
  )

  # A safe search box. Increase margin if numStars is large.
  approx_r <- sqrt(numStars / pi) + margin

  xs <- ceiling(-approx_r):floor(0.5 + approx_r)
  ys <- ceiling(-approx_r):floor(0.5 + approx_r)
  pts <- expand.grid(x = xs, y = ys)

  best_r2 <- Inf
  best_center <- c(NA_real_, NA_real_)

  for (i in seq_len(nrow(centers))) {
    a <- centers$a[i]
    b <- centers$b[i]

    d2 <- (pts$x - a)^2 + (pts$y - b)^2
    kth <- sort(d2, partial = numStars)[numStars]

    if (kth < best_r2) {
      best_r2 <- kth
      best_center <- c(a, b)
    }
  }

  list(
    radius = sqrt(best_r2),
    stars = numStars,
    center = best_center
  )
}

minRadiusForStars(15, step = .001, margin = 2)
## $radius
## [1] 2.061553
## 
## $stars
## [1] 15
## 
## $center
## [1] 0.5 0.0
minRadiusForStars(16, step = .001, margin = 2)
## $radius
## [1] 2.061553
## 
## $stars
## [1] 16
## 
## $center
## [1] 0.5 0.0
minRadiusForStars(58, step = .001, margin = 5)
## $radius
## [1] 4.155193
## 
## $stars
## [1] 58
## 
## $center
## [1] 0.500 0.125

We can see from this output that the radius required to get 15 and 16 is the same and is a little larger than the 2 that was given. We can also see that the minimum radius required to obtain 58 stars is about 4.155.

Best Picture Entry

For the best picture entry, I hired the help of Codex to design a heat map of the region [0,0.5] x [0,0.5] that represents the number of stars you can encompass with a circle of radius provided at the top right with center in the different regions defined on the heat map. Enjoy!