In how many ways can the numbers from 1 to 100 be arranged in a $2 \times 50$ rectangle so that any two numbers differing by 1 always end up in cells sharing a side?

#
Note that there is a one-to-one correspondence between the ways of arranging numbers and the rook's "tours" of the $2 \times 50$ board: if a method is given, we traverse the cells in the order of the numbers; if a tour is given, we number the cells in the order of the tour. This correspondence allows us to reason both in the "language of arrangement methods" and in the "language of rook tours." The cells with numbers 1 and 100 are called the ends of the tour.

A tour can contain a zigzag—a sequence of moves where vertical and horizontal moves strictly alternate, and at least one vertical move is made in a non-edge column (see the figure; for convenience, we have shaded the board in a checkerboard pattern).

![](https://cdn.mathpix.com/cropped/2024_05_06_309dcf72bd08bf7391b4g-19.jpg?height=157&width=975&top_left_y=530&top_left_x=539)

Let's see how the tour behaves at the edges of the zigzag. First, the zigzag can reach the end of the tour. This can only be the edge of the board (as on the left edge of the figure), otherwise the zigzag would "cut off" unvisited cells. Second, one can exit the zigzag with two horizontal moves. But then in the other row there remains a cell with a single "exit," and there can only be the end of the tour there. Thus, a zigzag is always confined between two (non-adjacent) columns with the ends of the tour, and therefore there are no other zigzags in this tour. Moreover, it is clear that the ends of the tour are uniquely determined by the zigzag.

On the other hand, the path between the edge of the board and the nearest column with the end of the tour is uniquely determined (start from the edge). Therefore, any zigzag (given a direction) is uniquely extended to a complete tour (see the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_309dcf72bd08bf7391b4g-19.jpg?height=154&width=975&top_left_y=1109&top_left_x=539)

A tour without zigzags can consist only of segments of a broken line (as in the following figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_309dcf72bd08bf7391b4g-19.jpg?height=154&width=983&top_left_y=1312&top_left_x=546)

However, this broken line has 100 segments, while the tour consists of 99 segments. Therefore, all such tours are obtained by removing one segment and correspond to placements of the ends in adjacent cells horizontally or on the edge vertically. Since any tour consists of an odd number of moves, the numbers 1 and 100 lie in cells of different colors. Moreover, from the above, it is clear that they fall into the same column only if it is the edge. A pair of 1 and 100, satisfying these two conditions, is called admissible. We have already shown that each admissible placement uniquely determines a zigzag (or its absence), and therefore the entire tour.

Let's count the number of admissible placements (this will be the number of ways). Forget for a moment about the second condition. Then the number 1 can be placed anywhere (100 possibilities), and after that, the number 100 in any cell of a different color (50 possibilities), for a total of $100 \cdot 50 = 5000$ such placements. To account for the second condition, we need to discard placements in non-edge columns. There are 48 such columns, and in each, the pair $\{1,100\}$ can be placed in two ways. Thus, the total number of admissible placements is $5000 - 2 \cdot 48 = 4904$.

## Answer

4904 ways.

Send a comment