Settlers in a circle

In this Riddler problem, the goal is to spread out settlements in a circle so that they are as far apart as possible:

Antisocial settlers are building houses on a prairie that’s a perfect circle with a radius of 1 mile. Each settler wants to live as far apart from his or her nearest neighbor as possible. To accomplish that, the settlers will overcome their antisocial behavior and work together so that the average distance between each settler and his or her nearest neighbor is as large as possible.

At first, there were slated to be seven settlers. Arranging that was easy enough: One will build his house in the center of the circle, while the other six will form a regular hexagon along its circumference. Every settler will be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile.

However, at the last minute, one settler cancels his move to the prairie altogether (he’s really antisocial). That leaves six settlers. Does that mean the settlers can live further away from each other than they would have if there were seven settlers? Where will the six settlers ultimately build their houses, and what’s the maximum average distance between nearest neighbors?

Here is my solution:
[Show Solution]

8 thoughts on “Settlers in a circle”

  1. Great write-up. It’s interesting that this particular metric (average nearest neighbor distance) admits asymmetric solutions, where I think something like average pairwise distance will not (?).

  2. “Yuck!” is right. I got only as far as recognizing that the house in the middle would have to be displaced slightly from the center in a direction opposite from one of the perimeter houses. But my resulting “solution” was off because I still assumed that the five houses on the perimeter would have to form a regular pentagon to maximize average distances to the nearest neighbor, an assumption I now see is completely wrong.

    Nice job, Laurent!

    1. I found the same solution, but only for 6 settlers, and not analytically. I used a simple grid search over the displacement distance and angles of the two pentagon points (other two placed with symmetry). Follow “Antisocial Settlers” link from https://sites.google.com/view/msbits if you wish to see.

      Fantastic write up, Laurent.

  3. What am I missing? Looking at the diagram, how can z > 1 if x > 0? I notice that in the published solution on fivethirtyeight, z isn’t even shown.

    1. You are correct that $z \lt 1$. But remember the task is to optimize the average of the nearest-neighbor distances. For some settlers (i.e. Settlers B,C,F in the diagram), the nearest-neighbor distance is greater than 1, for the rest (Settlers A,D,E, it’s less than 1). But these distances are such that the average of all of them is greater than 1.

      1. Ah. Got it! Thank you. I knew the problem (as I understood it) was far too simple for a Riddler Classic but I just couldn’t see where I was going wrong. Average was indeed the key word. I need to revise my comprehension skills.

Leave a Reply

Your email address will not be published. Required fields are marked *