4. A robot is located in one of the cells of an infinite grid paper, to which the following commands can be given:

- up (the robot moves to the adjacent cell above);
- down (the robot moves to the adjacent cell below);
- left (the robot moves to the adjacent cell to the left);
- right (the robot moves to the adjacent cell to the right).

For example, if the robot executes a sequence of four commands (up, right, down, left), it will obviously return to the initial position, i.e., it will end up in the same cell from which it started. How many different sequences of 8 commands exist that return the robot to the initial position?
Solution. For brevity, let's denote the command to move left as L, right as R, up as U, and down as D. For the robot to return to its initial position, it is necessary and sufficient that the number of L commands equals the number of R commands, and the number of U commands equals the number of D commands. Let $k$ be the number of L commands in the sequence. We will count the number $N_{k}$ of the desired sequences for $k$ from 0 to 4.

- $\boldsymbol{k}=\mathbf{0}$. The sequence consists only of U and D commands. Since they are equal in number, 4 out of 8 positions should be U, and the rest should be D. The number of ways to choose 4 positions out of 8 is $C_{8}^{4}$. Therefore, $N_{0}=C_{8}^{4}=70$;

## Interregional School Olympiad in Mathematics - $\boldsymbol{k}=\mathbf{1}$. The sequence consists of one L command, one R command, and three U and three D commands. The number of ways to place two L and R commands on 8 positions is $C_{8}^{2} \cdot C_{2}^{1}$: $C_{8}^{2}$ is the number of ways to choose 2 positions out of 8, and $C_{2}^{1}=2$ is the number of ways to place the L and R commands on these two positions. The number of ways to place 3 U commands on the remaining 6 positions is $C_{6}^{3}$. Therefore, $N_{1}=C_{8}^{2} \cdot C_{2}^{1} \cdot C_{6}^{3}=1120$;
- $\boldsymbol{k}=\mathbf{2}$. Here, there are two L commands, two R commands, and two U and two D commands. The number of ways to place L and R commands is $C_{8}^{4} \cdot C_{4}^{2}$. The number of ways to place 2 U commands on the remaining 4 positions is $C_{4}^{2}$. Therefore, $N_{2}=$ $C_{8}^{4} \cdot C_{4}^{2} \cdot C_{4}^{2}=2520$.

By reasoning similarly, it can be shown that $N_{3}=N_{1}$ and $N_{4}=N_{0}$. Thus, the desired number of sequences is $2 \cdot\left(N_{0}+N_{1}\right)+N_{2}=4900$.

Answer: 4900.