Optimization problems

Consider a given tiling of a \(2N \times 2N\) board using tiles of the given type. Note that there are two types of paths. Some path are between two points lying on the boundary of the square, and the other paths are contained in the interior of the square, and form cycles. Let \(\mathcal{B}, \mathcal{C}\) denote the collection of paths of the first and second kind respectively. Observe that among the mid-points of the sides of these \(4N^2\) tiles, there are precisely \(4 \times 2N = 8N\) mid-points which lie on the boundary of the square. Since each of the paths, which are not cycles, have precisely two such points as end-points, and no two paths of these kind have an end-point in common, it follows that there are precisely \(4N\) paths, which are not cycles. Observe that no two paths have a segment in common. Note that the remaining paths, which are contained in the interior of the square, form cycles. Each of these cycles contains at least four segments. Hence, these cycles together contain at least \(4 \vert \mathcal{C} \vert\) segments. Also note that a path contains at least two segments, unless it is formed by single segment, and note that there are at least four such paths. Let \(s\) denote the number of paths consisting of a single segment. Since there are a total of \(4N^2\) tiles, each contributing two segments, we have \(8N^2\) segments in total. This shows that \[ 8N^2 \geq s + 2 (\vert \mathcal{B} \vert - s) + 4 \vert \mathcal{C} \vert , \] which yields \[ 8N^2 + 8N \geq 4 (\vert \mathcal{B} \vert + \vert \mathcal{C} \vert) - s . \] It follows that \[ \vert \mathcal{B} \vert + \vert \mathcal{C} \vert \leq 2N^2 + 2N + \frac{s}{4} \leq 2N^2 + 2N + 1 . \] This proves that there are exactly \(4N\) paths which are not cycles, and there are at most \(2N^2 + 2N + 1\) paths in total. The tiling, as illustrated in Fig. 3 in the case \(N = 4\), shows an example of a configuration where the number of paths is equal to \(4N\). The tiling, as illustrated in Fig. 4 in the case \(N = 4\), shows an example of a configuration where the number of paths is equal to \(2N^2 + 2N + 1\). Hence, the least possible number and the maximum possible number of paths are \(4N\) and \(2N^2 + 2N + 1\) respectively.