6
$\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).

Improve this question
$\endgroup$
4
  • $\begingroup$ Better suited to math.stackexchange.com ? $\endgroup$
    – Bohemian
    Aug 28, 2016 at 21:55
  • 1
    $\begingroup$ @Bohemian sorry .. I have already asked it on MSE here. I just wanted to post it here as well (because it comes from a local puzzling contest.) Thanks! :) $\endgroup$
    – r9m
    Aug 28, 2016 at 21:58
  • $\begingroup$ Can you post the source? If not, this will be deleted due to plagiarism. $\endgroup$
    – Deusovi ♦
    Aug 28, 2016 at 22:03
  • $\begingroup$ @Deusovi I have edited the source pdf (It's past deadline of submission, so it should be okay to discuss it here right?) $\endgroup$
    – r9m
    Aug 28, 2016 at 22:07

2 Answers 2

Reset to default
2
$\begingroup$

Yes, there exists a unidirectional unit square in the grid.

Take the shape with smallest area in the grid which has unidirectional boundary. If it is not a unit square, then it contains an inner edge. Starting from this edge, going backwards and forwards, you can create a unidirectional path, connecting two points on the boundary of the shape. If this path intersects itself, then this is already a unidirectional shape with smaller area. If not, the path, combined with one of the two semi-boundaries of the outer shape will form a unidirectional shape with smaller area.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I suppose 'starting from this edge, going backwards and forward ..' needs an inductive explanation (but it should be possible, as I understand from the answer provided here ) .. thanks! Unless I am missing something even simpler/obvious. $\endgroup$
    – r9m
    Aug 28, 2016 at 22:56
  • $\begingroup$ @r9m You can even skip induction. Just keep going "forward" until you make a loop or hit the boundary. Then you go "backward" until you make a loop or hit the boundary. You will never get stuck since the inner nodes have equal in- and out-degrees, and passing through a node decreases both by 1. $\endgroup$
    – Puzzle Prime
    Aug 28, 2016 at 23:02
  • $\begingroup$ But I don't follow how making a loop will ensure that the resultant cycle we get will enclose a smaller area (we might not have any path from the boundary of this minimal oriented cycle leading to an interior point, meaning the loops we create as a result might not be restricted inside this minimal oriented cycle). Again I am not arguing that this is incorrect in any way, just that I am lacking imagination/motivation to see it's a sufficient argument. $\endgroup$
    – r9m
    Aug 28, 2016 at 23:09
  • 1
    $\begingroup$ @r9m, the point is that you will always create a unidirectional path which starts from the boundary of the shape, ends on it, and is entirely contained inside the shape. If this path intersects itself, i.e. forms a loop/cycle, then you are done - it will be smaller than the starting shape. If not, then the path combined with one of the two semi-boundaries of the outer shape once again will form a smaller shape. $\endgroup$
    – Puzzle Prime
    Aug 28, 2016 at 23:15
  • 1
    $\begingroup$ Yes! That's the general strategy. Thanks! :-) $\endgroup$
    – r9m
    Aug 28, 2016 at 23:19
2
$\begingroup$

This can be shown by induction. Suppose without loss of generality that the main square is clockwise oriented.

Then the arcs from the top-left-most inner vertex, shared with the vertices on the main square, must both either enter the vertices on the main square or both leave them (and enter the top-left-most inner vertex).

Now to avoid breaching either the "two in, two out" condition or creating an oriented inner square, we must set the other arcs from the top-left-most inner vertex in the opposite direction to corresponding arcs entering it: one of each horizontal and vertical arcs is an entry and one of each an exit.

Then along the same horizontal line, that is, the top-most inner vertices and left-most inner vertices of each row and column, the arcs must have identical direction, so all such vertices follow the same condition: one each of horizontal and vertical is an entry and an exit.

Thus, all main squares can be considered an extension of the main square with one less vertex in each column and row; apply this inductively to obtain the $2×2$ case.

Again without loss of generality, suppose the vertical arcs of the inner vertex are determined, either both up or both down. Then the horizontal arcs must also be both left or both right. But then at least one of the four inner squares must have one up, one down, one left, one right arc. This square is oriented by definition, so an oriented square exists, as in the diagrams below.

the examples from a 2×2 main square

Improve this answer
$\endgroup$
4
  • $\begingroup$ The top-left most square lets name it $\overline{ABCD}$ (named clockwise where $A$ is the top left most vertex of the large square). Then $\overrightarrow{DA}, \overrightarrow{AB}$ are the two sides shared with the boundary (which is assumed to be clockwise oriented). Then $\overrightarrow{DC},\overrightarrow{CB}$ is an assignment where not both edges are entering/leaving $C$ yet no oriented $1 \times 1$ square is formed. $\endgroup$
    – r9m
    Aug 29, 2016 at 0:32
  • $\begingroup$ @r9m the oriented square doesn't have to be the top-left-most. I construct explicitly so that it is not, becauae otherwise it is proof by assuming the conclusion. $\endgroup$
    – Nij
    Aug 29, 2016 at 0:38
  • $\begingroup$ So your induction hypothesis is for arbitrary oriented cycles in the grid? (not particularly for squares?) .. in which case the assignment I mentioned boils down to a case covered by this induction hypothesis. $\endgroup$
    – r9m
    Aug 29, 2016 at 0:43
  • $\begingroup$ @r9m it shows that any rectangular case can be either simplified to the 2×2 case, or has already contained an oriented square. Then showing the 2×2 case must have an oriented square, means all rectangles have an oriented square, including your n×n main square. $\endgroup$
    – Nij
    Aug 29, 2016 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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