To avoid making the explanation overly complex by starting with a general case, we will focus on specific examples. For the general solution, please refer to the implementation example below.

Implementation Example (Python)

First, let’s consider the case where \(N=2\). As an example, we will solve the problem for \(M=5\).

The initial state is as follows:

.1234512345.

In 4 moves, the inner 8 stones (23451234 part) can be moved outward and temporarily stored in a suitable location:

.1........5.........23..45..12..34.

By carefully placing the removed 8 stones back into the inner area, they can be arranged as follows:

.1122334455.

Thus, the case where \(N=2\) and \(M=5\) can be solved in 8 moves. In general, for \(N=2\), the problem can be solved in \(2(M-1)\) moves using a similar process.

Next, let us consider the general case for \(N\). As an example, we will solve the case where \(N=4\) and \(M=5\).

The initial state is as follows:

.12345123451234512345.

By performing the same operations as before, we can achieve the following state in \(8 \times 2 = 16\) moves:

.11223344551122334455.

We will call these operations the “first half.” Once the stones are arranged in this manner, the remaining steps are straightforward. By moving adjacent pairs of stones with the same color one by one, we can achieve the following state in 10 moves:

.....................11112222333344445555.

However, this results in \(16+10=26 \gt 25 = (4+1) \times 5\), which exceeds the move limit. Therefore, let us carefully observe the operations performed in the first half. To make it clearer, let us introduce a gap in the center and refer to the left side of the gap as the “left block” and the right side as the “right block.”

.1234512345  1234512345.
↓(4 moves)
.1........5  1234512345...23..45..12..34.
↓(4 moves)
.1122334455  1234512345.
↓(4 moves)
.1122334455  1........5...23..45..12..34.
↓(4 moves)
.1122334455  1122334455.

This sequence can be optimized to reduce the number of moves as follows:

.1234512345  1234512345.
↓(4 moves)
.1........5  1234512345...23..45..12..34.
↓(4 moves)
.1122334455  1........5...23..45..12..34.
↓(4 moves)
.1122334455  1122334455.

Instead of returning the stones removed from the left block back to the left block, we move the inner stones of the right block to the left block, and the stones removed from the left block are moved to the right block. This reduces the number of moves in the first half to \(12\) . The second half still takes 10 moves, so the total is 22 moves, satisfying the move limit.

The same method can be applied to the general case. First, divide the \(NM\) stones into blocks of \(2M\) stones each. Then, perform similar operations as described above. After removing the inner stones of the leftmost block, move the stones from the second block to the first block, from the third block to the second block, and so on, finally moving the stones from the leftmost block to the rightmost block. This reduces the first half of the operations to \(\left(\frac{N}{2}+1\right) \times (M-1)\) moves. The second half takes \(\frac{N}{2} \times M\) moves, so the total becomes \(NM+M-\frac{N}{2}-1 \le (N+1)M\) moves, satisfying the condition.