7. (7) On a square board of size $2018 \times 2018$, a token started from some cell and made a tour, moving to an adjacent cell each time and ending in the starting cell. In the process, it entered each cell exactly once. For what smallest $k$ can it make such a tour, entering each column and each row no more than $k$ times?

(Canada National Olympiad 2015)
Answer: 1010.

We will prove that for a board of size $(4 n+2) \times(4 n+2)$, the smallest $k$ is $2 n+2$. Indeed, with each move, we either enter a new column or a new row. Therefore, after $(4 n+2)^{2}$ moves, the total number of "entries" will be $(4 n+2)^{2}$. Since the total number of rows and columns is $8 n+4$, either some row or some column will be entered at least $2 n+2$ times, or each row and each column will be entered exactly $2 n+1$ times.

Suppose the latter. Consider some side column or row. After the chip enters it, it will make at least one more move along this column or row. This means that all segments of the path in this column or row have a minimum length of 1. Since there are $2 n+1$ such segments, each of them must have a length of 1. But in the corner, some segment of the path will have a length of 2, which is a contradiction. Therefore, the minimum $k=2 n+2$.
![](https://cdn.mathpix.com/cropped/2024_06_04_faac9ba8ecce81f7654cg-42.jpg?height=608&width=1250&top_left_y=1248&top_left_x=94)

Figure 6: Solution to problem 7.

Some possible examples are shown (for a $18 \times 18$ table, i.e., $n=4$) in Figure 6. It is easy to see that $k=2 n+2$ results.