Belarusian Mathematical Olympiad

$$\{\begin{array}{ll}2k^2+k,& \text{if }n=2k;\\ 2(k+1{)}^2,& \text{if }n=2k+1.\end{array}$$

If the length $n$ of the town square is odd, i.e. $n=2k+1$, then from the solution of Problem D8 it follows that the minimal value of the required lampposts is equal to $$2(k+1)\left[\frac{n+1}{2}\right]=2(k+1{)}^2.$$

Now let $n=2k$ is even. We paint some tiles of the town square black (see Fig. 1).



Fig. 1 Fig. 2

Consider the tiles which form the painted "angle" (see Fig. 2). It is easy to see that to illuminate each of these tiles by at least two lamps we need at least three lampposts in total. From our coloring it follows that any lamp cannot illuminate two colored tiles if they are not adjacent (we call two tiles adjacent if they have either the common side or the common corner). Thus, the minimum value of the required lamppost is equal to $3r+2l$, where $r$ is the number of the colored angles and $l$ is the number of the solitary colored tiles. Since $r=k$ and $l=k^2-k$, we need at least $3r+2l=2k^2+k$ lampposts.

On the other hand, if we place the lampposts as it is shown in Fig. 1 (the lampposts are indicated as uncolored circles), then any tile of the town square will be illuminated by two lamps. So, if $n=2k$, then $2k^2+k$ lampposts are sufficient to illuminate the town square so that the problem condition holds.