16
$\begingroup$

When I draw a circuit on a 8x8 chess board that passes through all squares, no matter how many turns I draw, I always end up with 18 grid points outside my circuit (and 31 grid point inside). It looks to me that I get also constant values for any $n$ x $m$ board. Has anybody ever seen a formula of how many grid points are inside/outside for an $n$ x $n$ board? It looks obvious that there are (n/2 - 1) * (n - 2) points outside if $n$ is even, but I am searching for a proof.

If you could point me to some literature, that would be great!

enter image description here

$\endgroup$
9
  • $\begingroup$ Thanks so much! $\endgroup$ – Rüdi Jehn Jan 14 at 20:43
  • $\begingroup$ Interestingly, on the $7\times 7$ grid graph, the enclosed vertices represent a maximum induced tree subgraph. $\endgroup$ – Joffan Jan 14 at 22:07
  • $\begingroup$ @Joffan: What is a maximum induced tree subgraph? Could you send us a link? $\endgroup$ – Rüdi Jehn Jan 15 at 15:23
  • $\begingroup$ An induced subgraph of $G$ is a subset of the vertices of $G$ plus all the edges in $G$ that link them. An induced tree is just an induced subgraph that is a tree. The maximum part is to show that we have taken as many vertices as possible without creating circuits, and avoiding circuits means there are no excluded areas for the corresponding rook tour, $\endgroup$ – Joffan Jan 15 at 15:30
  • 1
    $\begingroup$ @Joffan Re "maximal tree", show that A) if there was a cycle, then the enclosing path will have a hole and B) If there are 2+ components, then the enclosing path will have 2+ components. $\endgroup$ – Calvin Lin Jan 15 at 16:36
12
$\begingroup$

For an $m$ by $n$ array with $mn$ even, consider a lattice on the centres of squares. The path passes through $mn$ lattice points and contains no internal points. So, by Pick's theorem it contains an area of $\frac{mn}{2}-1$.

This area consists of unit squares centred on the 'grid points' of the question and so there are $\frac{mn}{2}-1$ enclosed grid points.

$\endgroup$
2
  • $\begingroup$ Oh very nice! I tried Pick's theorem on the (0.5n, 0.5m) lattice, but that didn't work out well. You nailed the bijection that I was trying to express. $\endgroup$ – Calvin Lin Jan 15 at 16:33
  • $\begingroup$ Yes! I saw this problem and thought 'it has to be Pick's' but when I tried it with the lattice you tried it seemed too involved to explain. Then when I was watching a film I suddenly realised what I should have done. $\endgroup$ – S. Dolan Jan 15 at 16:38
11
$\begingroup$

The main idea here is to create a bijection from the enclosed grid points, to the area of the polygon, to the angle sum on the polygon. We will set this up in reverse.
Because the angle sum is a constant, hence the number of enclosed grid points is a constant, which we can then determine. From there, the number of exterior grid points is a constant.

Let the square be of size $ 2k \times 2k$. The question is for $k = 4$.
(It has to be of even size in order to form a circuit. The standard coloring argument applies.)

Show that

  • Let the circuit connect through the mid points of the grid squares. This gives us a polygon whose (interior) corner angles are $90^\circ$ or $ 270^\circ$.
  • For each grid square, there are exactly 2 lines that connect to the mid point. This splits the square into 2, one which is on the inside of the curve, and one which is on the outside of the curve. (This should be obvious, else appeal to high-power Jordan curve theorem.)
  • For each mid point of a grid square, associate it to the angle that lies on the inside of the curve. This angle is either $ 90 ^ \circ, 270^\circ$ (if the mid point is also a corner of the polygon, then it's equal to the interior angle), or $180^\circ$ (if the mid point lies within an edge of the polygon).
  • For each mid point of a grid square, the associated angle is also equal to "$180 ^ \circ -$ exterior angle of the polygon". Note that I'm taking "exterior angle = $180^\circ - $interior angle" as a signed angle, which could be negative. (Verify this for mid points that are on the edges and corners of the polygon.).
  • There are $4k^2$ such mid points of the grid squares.
  • The sum of all associated angles is thus
    $\sum_{\text{mid point}}(180 ^ \circ -$ exterior angle) = $180^\circ \times 4k^2 - \sum $ exterior angles$ = 180^\circ \times 4k^2 - 360^\circ$ . (Using that summation of signed exterior angles for a non-self intersecting polygon is $360^\circ$.)
  • Show that there is a bijection between each $90^\circ$ angle and the (obvious) $\frac{1}{2} \times \frac{1}{2}$ square that is contained within the curve. (There's some work here to establish the seemingly obvious bijection.)
  • Hence, the area enclosed by the curve is $ \frac{1}{4} \frac{1}{90^\circ} (180^\circ \times 4k^2 - 360^\circ) = 2k^2 - 1 $.
  • Show that there is a bijection between an enclosed grid point and the $1 \times 1$ square around it (which intersects 4 grid squares) that lies within the polygon. (There's some work here to establish the seemingly obvious bijection.)
  • Each enclosed grid point contributes exactly 1 to the area, hence there are $ 2k^2 -1 $ enclosed grid points.
  • Since there are $(2k-1)^2$ grid points, there are $ (2k-1)^2 - (2k^2 -1) = 2(k-1)^2$ excluded grid points.

For the general $ n \times m$ grid where $nm$ is even, you can follow the above proof to conclude that

  • area of enclosed polygon is $nm/2-1$, hence so is the number of enclosed grid points
  • $(n-1)(m-1)$ grid points,
  • $(n-1)(m-1) - ( nm/2 - 1) = \frac{1}{2} (n-2)(m-2)$ excluded grid points.
$\endgroup$
1
  • 1
    $\begingroup$ this is beautiful $\endgroup$ – t-tough Jan 14 at 19:02

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.