City of Oneway

EDIT: I just realized that the problem has been rephrased to use "trees" instead of "buildings". I haven't got any time to edit this solution, so replace "building" with "tree" in the following.

---

We claim that for a $r \times c$ grid, there must be at least

$\left\lceil \dfrac{(r-1)(c-1) + 1}{3} \right\rceil$

buildings. In addition, we claim that if $r = 2^n + 1, c = 2^{n+1} + 1$ for some nonnegative integer $n$ , this bound can be achieved. Since our problem is simply $n = 9$ , this gives the minimum number of buildings.

First, we begin by proving the bound. The idea is to count the number of lattice segments (the sides of the cells) in order to bound the number of empty cells, and thus the number of buildings.

After erecting the buildings, create a graph; the vertices are the cells that remain empty, and two vertices are adjacent exactly if their cells are orthogonally adjacent. The condition on the problem implies that the resulting graph must be a tree: it may not have any cycle (if it has a cycle, pick any two vertices on the cycle; there are two ways from one vertex to go to the other), and it must be connected (if it isn't, pick two vertices on different components; by definition, there is no path between them).

Suppose we have $v$ vertices in our graph. Note that since we want to minimize the number of buildings, then we want to maximize the number of empty cells, so we want to maximize $v$ . Since the graph is a tree, it has $v-1$ edges.

An equally important observation is to notice the shape produced by the empty cells. Our former observation implies that there are $v-1$ segments of the lattice grid that are between two adjacent empty cells.

Now, we claim by induction on $v$ that the perimeter of the shape is $2v+2$ .

For $v = 1$ , this is trivial; there's only one empty cell, so its perimeter is 4. If we have proven the claim for $v = k$ , then consider the case $v = k+1$ . This is the result of adding a new cell to a shape of $k$ cells. The new cell must be adjacent to at least one earlier cell (otherwise it's unattached), but it cannot be adjacent to two or more cells: if it is adjacent to $p, q$ , then since $p, q$ both belong to the shape, there is already a path connecting them together. Adding the new cell would give $p, q$ a second way (through the new cell), so this is not allowed. Thus the new cell is adjacent to exactly one previous cell: from the perimeter, one unit is lost (the side where the new cell sticks in), but three units is gained (the other three sides), so the perimeter increases by 2, from $2k+2$ to $2k+4$ . This proves the claim.

Finally, we gather all observations together. There are $v-1$ segments between two adjacent empty cells. There are $2v+2$ segments between an empty cell and a not-empty cell (whether that's a building or the outside of the grid). How many segments do we have between two not-empty cells? At least one: around the border of the grid, there must be at least one building, otherwise the border of the grid creates a cycle of empty cells. This building and the outside of the grid are two adjacent not-empty cells.

In total, we have shown that there must be at least $(v-1) + (2v+2) + 1 = 3v+2$ segments. But the number of segments in total is $r(c+1) + (r+1)c = 2rc + r + c$ . Thus we must have $2rc+r+c \ge 3v+2$ , or $v \le \frac{2rc+r+c-2}{3}$ . Since $v$ is the number of empty cells, the number of buildings is then $rc-v \ge \frac{rc-r-c+2}{3} = \frac{(r-1)(c-1) + 1}{3}$ , proving the bound.

It remains to prove that this bound is achievable, at least for the special case $r = 2^n + 1, c = 2^{n+1} + 1$ (in which the bound says $\left\lceil \frac{2^{2n+1} + 1}{3} \right\rceil$ ). We prove this by induction on $n$ .

The base case $n = 0$ is straightforward; put one building on the middle of bottom row. This matches the bound of 1.

Suppose we have proven the claim for $n = k$ , and we want to prove the claim for $n = k+1$ . We "blow up" the city for $n = k$ , inserting a new row between each pair of adjacent rows, and similarly with columns. We then add a building on the intersections of the newly added rows and columns.

We will claim that this matches the bound, and it's valid.

Matching the bound is easy: we added $2^k$ rows and $2^{k+1}$ columns, so there are $2^{2k+1}$ new buildings. With $\left\lceil \frac{2^{2k+1} + 1}{3} \right\rceil$ buildings previously built, we have a total of $2^{k+1} + \left\lceil \frac{2^{2k+1} + 1}{3} \right\rceil = \left\lceil \frac{2^{2k+3} + 1}{3} \right\rceil$ buildings, matching the bound.

Proving that it's valid is also pretty straightforward. Each yellow empty cell (the newly added empty cells) is adjacent to one or two empty cells (it's clear that it's adjacent to at most two empty cells, because two of its neighbors are buildings on new intersections; proving at least one empty cell can be done by induction to show that no two buildings are adjacent). Considering the graph of empty cells, note that the graph is bipartite, colored white and yellow. (Easy to prove: new rows and columns mean no two white vertices are now adjacent, and buildings on intersections mean no two yellow vertices are adjacent.) Suppose $u, v$ are two vertices in this graph. Any path connecting them must alternate between white and yellow vertices by the graph being bipartite; furthermore, if $p, q$ are two consecutive white vertices on this path, there is exactly one yellow vertex $r$ that is adjacent to both $p, q$ (indeed, there is exactly one yellow vertex between each pair of formerly adjacent white vertices). Thus we can ignore the yellow vertices on the path, since we can uniquely recover them. This gives a sequence of white vertices, which must be a path in the original city. Since the original city has only one path between $u, v$ , there can only be one path in this new city either.

Thus we have proven that the construction is valid, proving the claim. Plugging in $n = 9$ to the bound gives $\left\lceil \frac{2^{19} + 1}{3} \right\rceil = \boxed{174763}$ .