Skip to main content
added 529 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Here(I assume that the OP wants to minimize is a very shortthe number of turns rather than the total amount of absolute turning angles.)

If we restrict to moving only parallel to the axes, here is an elementary proof, but perhaps not completely trivial.

Assume there are $n$ rows and $m$ columns. Represent the traversing path by a line,segments going from the center of one unit square to the center of the next and so on.

There There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERSTURNs):

Unit square typesUnit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit squarean X-square must contain at least $2$ CORNER squaresTURN-squares. Likewise any column containing a VERTICAL unit squareY-square must contain at least $2$ CORNER squaresTURN-squares.

Conclusion: if each row contains at least one HORIZONTAL squareX-square, then there are at least $2n$ CORNER squaresTURN-squares. Otherwise there is one row consisting entirely of VERTICAL squaresY-squares, in which case each column contains at least one VERTICAL squareY-square, and then there are at least $2m$ CORNER squaresTURN-squares.

Since Since $2$ of the $2n$ or $2m$ CORNER squaresTURN-squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$$\min(2n,2m)-2$ true cornersturns, as expected.


ADDENDUM 7/8/2024. (As per comments, if I understood correctly.)

If any piecewise linear path in the plane is allowed (self-crossing, not grid-aligned, not contained in the minimal rectangle around the lattice points), then the above result doesn't hold. The picture shows an example for $m=n=4$, with only $5$ turns:

wild path

Here is a very short elementary proof, but perhaps not completely trivial.

Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to the center of the next and so on.

There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERS):

Unit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit square must contain at least $2$ CORNER squares. Likewise any column containing a VERTICAL unit square must contain at least $2$ CORNER squares.

Conclusion: if each row contains at least one HORIZONTAL square, then there are at least $2n$ CORNER squares. Otherwise there is one row consisting entirely of VERTICAL squares, in which case each column contains at least one VERTICAL square, and then there are at least $2m$ CORNER squares.

Since $2$ of the $2n$ or $2m$ CORNER squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$ true corners, as expected.

(I assume that the OP wants to minimize is the number of turns rather than the total amount of absolute turning angles.)

If we restrict to moving only parallel to the axes, here is an elementary proof.

Assume there are $n$ rows and $m$ columns. Represent the traversing path by segments going from the center of one unit square to the center of the next and so on. There are then three (overlapping) types of unit squares with path-segments, according to the diagram pictured (notice that end-of-path squares are considered TURNs):

Unit square types

Trivial observation: any row of the rectangle containing an X-square must contain at least $2$ TURN-squares. Likewise any column containing a Y-square must contain at least $2$ TURN-squares.

Conclusion: if each row contains at least one X-square, then there are at least $2n$ TURN-squares. Otherwise there is one row consisting entirely of Y-squares, in which case each column contains at least one Y-square, and then there are at least $2m$ TURN-squares. Since $2$ of the $2n$ or $2m$ TURN-squares are end-of-path squares, there are at least $\min(2n,2m)-2$ true turns, as expected.


ADDENDUM 7/8/2024. (As per comments, if I understood correctly.)

If any piecewise linear path in the plane is allowed (self-crossing, not grid-aligned, not contained in the minimal rectangle around the lattice points), then the above result doesn't hold. The picture shows an example for $m=n=4$, with only $5$ turns:

wild path

added 4 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Here is a very short elementary proof, but perhaps not completely trivial.

Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to the center of the next and so on.

There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERS):

Unit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit square must contain at least $2$ CORNER squares. Likewise any column containing a VERTICAL unit square must contain at least $2$ CORNER squares.

Conclusion: if each row contains at least one HORIZONTAL square, then there are at least $2n$ CORNER squares. Otherwise there is one row consisting onlyentirely of VERTICAL squares, in which case each column contains at least one VERTICAL square, and then there are at least $2m$ CORNER squares.

Since $2$ of the $2n$ or $2m$ CORNER squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$ true corners, as expected.

Here is a very short elementary proof, but perhaps not completely trivial.

Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to the center of the next and so on.

There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERS):

Unit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit square must contain at least $2$ CORNER squares. Likewise any column containing a VERTICAL unit square must contain at least $2$ CORNER squares.

Conclusion: if each row contains at least one HORIZONTAL square, then there are at least $2n$ CORNER squares. Otherwise there is one row consisting only of VERTICAL squares, in which case each column contains at least one VERTICAL square, and then there are at least $2m$ CORNER squares.

Since $2$ of the $2n$ or $2m$ CORNER squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$ true corners, as expected.

Here is a very short elementary proof, but perhaps not completely trivial.

Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to the center of the next and so on.

There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERS):

Unit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit square must contain at least $2$ CORNER squares. Likewise any column containing a VERTICAL unit square must contain at least $2$ CORNER squares.

Conclusion: if each row contains at least one HORIZONTAL square, then there are at least $2n$ CORNER squares. Otherwise there is one row consisting entirely of VERTICAL squares, in which case each column contains at least one VERTICAL square, and then there are at least $2m$ CORNER squares.

Since $2$ of the $2n$ or $2m$ CORNER squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$ true corners, as expected.

Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Here is a very short elementary proof, but perhaps not completely trivial.

Assume there $n$ rows and $m$ columns. Represent the traversing path by a line, going from the center of one unit square to the center of the next and so on.

There are then three (overlapping) types of unit squares with path-segments, according to the Venn diagram pictured (notice that end-of-path squares are considered CORNERS):

Unit square types

Trivial observation: any row of the rectangle containing a HORIZONTAL unit square must contain at least $2$ CORNER squares. Likewise any column containing a VERTICAL unit square must contain at least $2$ CORNER squares.

Conclusion: if each row contains at least one HORIZONTAL square, then there are at least $2n$ CORNER squares. Otherwise there is one row consisting only of VERTICAL squares, in which case each column contains at least one VERTICAL square, and then there are at least $2m$ CORNER squares.

Since $2$ of the $2n$ or $2m$ CORNER squares are end-of-path squares, there are at least $\min(2n-2,2m-2)$ true corners, as expected.