The country of Squareland is shaped like a square and is divided into 64 congruent square cities. We want to divide Squareland into states and assign to each state a capital city so that the following rules are satisfied:

(a) Every city lies entirely within one state.

(b) Given any two states, the numbers of cities in them differ by at most 1 .

(c) Any city in a state shares at least one corner with the state's capital.

What is the smallest possible number of states?
In the diagram below, no city shares a corner with any two of the cities marked X. Therefore the nine X's are

![](https://cdn.mathpix.com/cropped/2024_04_17_921110140cad74839444g-1.jpg?height=615&width=618&top_left_y=847&top_left_x=1187)
in nine different states. The diagram at right shows that nine states are also sufficient ( $*$ denotes capital).
![](https://cdn.mathpix.com/cropped/2024_04_17_921110140cad74839444g-1.jpg?height=614&width=1398&top_left_y=1576&top_left_x=300)