How many times do we need to lift the pencil if we want to draw the grid of a chessboard on a piece of paper (its perimeter and internal lines), if we are only allowed to traverse each line once?

If we are allowed to traverse some segments more than once, what is the shortest path that allows us to cover the grid of the board without lifting the pencil? The perimeter of the board is $128 \mathrm{~cm}$.
a) By drawing the network and (with a different colored pencil) retracing it. Considering the intersections of the dividing and boundary lines of the board as nodes, 4 paths lead from the internal nodes to the adjacent nodes (even nodes), 2 paths from the corner nodes (even nodes), and 3 paths from the nodes on the boundary and dividing lines (odd nodes).

When looking for the minimum number of pencil lifts, we only lift the pencil at a point $V$ where we cannot proceed further, obviously only at a node, if we have drawn the last path belonging to it. The starting point can only be a node as well, because the pencil line can be extended backward. In every $K$ starting point, we use 1 path, which is why the node - in terms of the remaining paths - changes to the opposite parity (from odd to even, from even to odd). If we pass through a node, the number of remaining paths decreases by 2, so its parity does not change. Thus, we complete the drawing of all paths from a corner node in one pass, and from the internal nodes in two passes (unless we started from such a node). For an odd node, however, only 1 path remains free after one pass, and we must lift the pencil when we arrive there again.

It is evident from this that it is only useful to use an originally odd node as $K$, and - adhering to this rule - only an originally odd node can be $V$. The number of $K$ and $V$ points is equal. There are 7 odd nodes on each side, totaling 28, of which 14 will be $K$ and 14 will be $V$, so we need to lift the pencil 13 times and 14 times at the end to finish.

![](https://cdn.mathpix.com/cropped/2024_05_02_90c9129066af9dc3414fg-1.jpg?height=559&width=507&top_left_y=802&top_left_x=755)

Figure 1

b) To complete our path without lifting the pencil, we need to retrace every path from each $V$ to the next $K$, so we must choose a nearby new $K$ for each $V$. The distance between adjacent odd points on the same side is equal to the side $c$ of the squares, and the nearest odd points on two adjacent sides are $2c$ apart (on the line). The 7 odd points on each side can be paired into three adjacent $V-K$ pairs, resulting in $4 \cdot 3c = 12c$ extra paths. If we choose the remaining odd point on each side to be the neighbor of two opposite corners of the board (points $A, B, C, D$ in the figure), and the connecting path's $K$ and $V$ are $A$ and $D$, then an additional $2c$ extra path is needed between $B$ and $C$.

The perimeter of the board is $32c = 128$, so $c = 4 \text{ cm}$. The length of the lines in the network is $2 \cdot 9 \cdot 8c = 576 \text{ cm}$, the retraced path is $14c = 56 \text{ cm}$, so the length of the shortest path is $632 \text{ cm}$. Figure 1 shows that such a retracing path indeed exists.

Kultsár Szabolcs (Hajdúböszörmény, Bocskai I. g. II. o. t.) Padányi Piroska (Budapest, Radnóti M. g. I. o. t.)

Note. If the network contains $2n \times 2n$ squares instead of $8 \times 8$, or $2n+1$ segments of length $2nc$ in each direction, then the number of odd nodes is $4(2n-1)$, and thus the pencil must be lifted (including the final lift) $2(2n-1) = 4n-2$ times. If we want to retrace this network without lifting the pencil, then the path length is

$$
[2(2n+1)2n + 4(n-1) + 2]c = (8n^2 - 8n - 2)c
$$

If, however, we are dealing with a $(2n+1)^2$ chessboard, then the $4 \cdot 2n$ odd nodes require $4n$ lifts, and the total path length of the pencil is

$$
[2(2n+2)(2n+1) + 4n - 1]c = (8n^2 + 16n + 3)c
$$

Indeed, here the pairing of the $2n$ odd nodes on each side into $V-K$ pairs requires $nc$ extra paths, but one such pairing is redundant in the entire network because 2 (adjacent) nodes serve as the $K$ and $V$ of the entire path. The existence of such a path for a $7 \times 7$ chessboard is shown in Figure 2.

![](https://cdn.mathpix.com/cropped/2024_05_02_90c9129066af9dc3414fg-2.jpg?height=409&width=382&top_left_y=159&top_left_x=861)

Figure 2

(K and V are not marked for symmetry reasons; any two endpoints of a retraced $c$-segment can be used for this purpose.) The wiring can be used for any (greater than 1) odd number of squares, because when transitioning from $2n+1$ to $2n+3$, we have 2 more parallels in each direction, and thus the number of round trips increases by 1. The principle in Figure 1 can also be used for any even number of squares.

Szidarovszky Ferenc (Budapest, Fazekas M. gyak. g. II. o. t.)