9
$\begingroup$

Consider a $n \times n$ square grid (finite) (a square is divided into smaller squares by lines parallel to its sides). The boundary of the square is oriented, (clockwise or anticlockwise) that is, a direction is chosen on it and fixed, such that if you move in that direction along the boundary, the internal points of the square always stay on your left or on your right (depending on the orientation). For each of the internal edges of the subdivision, a direction is specified, such that for each interior vertex, there are exactly two edges coming to the vertex and two edges going away from it (see diagram below).

Then my question is that does it follow that there is atleast one oriented face in the subdivision?

Figure

(For example in the figure, there is exactly one such face, namely in the extreme lower right corner).

$\endgroup$
4
$\begingroup$

Yes. More generally, in an $m\times n$ grid ($m,n \in \mathbb{N}\setminus \{0\}$) where the edges are oriented satisfying these conditions there is always at least one square whose boundary is oriented like the boundary of the whole grid.

Let's suppose the large boundary is oriented positively (counterclockwise).

The assertion is easily verified if $n = 1$ (and it's trivial for $m = n = 1$). Since the uppermost horizontal edge is oriented left, and the bottommost edge right, there must be at least one square whose top edge is oriented left and whose bottom edge is oriented right (go from top to bottom until you hit the first square whose bottom edge is oriented right).

So assume $n > 1$ and look at the left edge of the square in the top right corner. If that edge is downward oriented, there is at least one square in the rightmost column whose boundary is positively oriented. If the square in the corner isn't it, its bottom edge is oriented left, so the left and bottom edge of that square both come into the bottom left vertex of that square, and hence the other two edges adjacent to that vertex go out. In particular, the left edge of the square below goes down. Then either its bottom edge is oriented right, and we have our oriented boundary, or it's oriented left and we have the same configuration as above, so the left edge of the third square from the top in the rightmost column is also oriented downwards. This stops at the latest when we reach the square in the bottom right corner.

If all left edges of the squares in the rightmost column are oriented upwards, we can simply drop (ignore) the rightmost column and are in the $m \times (n-1)$ case, where the induction hypothesis guarantees an oriented square.

Thus it remains to look at the case where the leftmost edge of the top right square is oriented upwards, and there is at least one square in the rightmost column whose left edge is oriented downwards. Look at the topmost such square, call it $s_1$. Then the two vertical edges adjacent to its top left vertex go out, and hence the top edge of $s_1$ is oriented left. Then we are essentially in the situation first discussed. If $s_1$'s boundary isn't yet oriented, its bottom edge is oriented left, and the left edge of the square below is also oriented downwards. As soon as we find a square below $s_1$ whose bottom edge is oriented right, we are done, and that must occur, since the bottom edge of the bottom right square is oriented right.

$\endgroup$
1
  • $\begingroup$ Brilliant!! Many Thanks!! :) $\endgroup$ – r9m Aug 28 '16 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.