Let $A=[0,0]$ and $B=[n,n]$. In how many ways can we go from $A$ to $B$, if we always want to go from lattice point to its neighbour (i.e. point with one coordinate the same and one smaller or bigger by one), we never want to visit the same point twice and we want our path to have length $2n+2$? (For example, path $[0,0],[0,1],[-1,1],[-1,2],[0,2],[1,2],[2,2],[2,3],[3,3]$ is one of the paths for $n=3$)

Theseus starts at the point $(0, 0)$ in the plane. If Theseus is standing at the point $(x, y)$ in the plane, he can step one unit to the north to point $(x, y+1)$, one unit to the west to point $(x-1, y)$, one unit to the south to point $(x, y-1)$, or one unit to the east to point $(x+1, y)$. After a sequence of more than two such moves, starting with a step one unit to the south (to point $(0, -1)$), Theseus finds himself back at the point $(0, 0)$. He never visited any point other than $(0, 0)$ more than once, and never visited the point $(0, 0)$ except at the start and end of this sequence of moves. Let $X$ be the number of times that Theseus took a step one unit to the north, and then a step one unit to the west immediately afterward. Let $Y$ be the number of times that Theseus took a step one unit to the west, and then a step one unit to the north immediately afterward. Prove that $|X - Y| = 1$. [i]Mitchell Lee[/i]

Let $n \geq 2$ be an integer. Switzerland and Liechtenstein are performing their annual festive show. There is a field divided into $n \times n$ squares, in which the bottom-left square contains a red house with $k$ Swiss gymnasts, and the top-right square contains a blue house with $k$ Liechtensteiner gymnasts. Every other square only has enough space for a single gymnast at a time. Each second either a Swiss gymnast or a Liechtensteiner gymnast moves. The Swiss gymnasts move to either the square immediately above or to the right and the Liechtensteiner gymnasts move either to the square immediately below or to the left. The goal is to move all the Swiss gymnasts to the blue house and all the Liechtensteiner gymnasts to the red house, with the caveat that a gymnast cannot enter a house until all the gymnasts of the other nationality have left. Determine the largest $k$ in terms of $n$ for which this is possible.

The figure shows a network of roads bounding $12$ blocks. Person $P$ goes from $A$ to $B,$ and person $Q$ goes from $B$ to $A,$ each going by a shortest path (along roads). The persons start simultaneously and go at the same constant speed. At each point with two possible directions to take, both have the same probability. Find the probability that the persons meet. [asy] import graph; size(150); real lsf = 0.5; pen dp = linewidth(0.7) + fontsize(10); defaultpen(dp); pen ds = black; draw((0,3)--(4,3),linewidth(1.2pt)); draw((4,3)--(4,0),linewidth(1.2pt)); draw((4,0)--(0,0),linewidth(1.2pt)); draw((0,0)--(0,3),linewidth(1.2pt)); draw((1,3)--(1,0),linewidth(1.2pt)); draw((2,3)--(2,0),linewidth(1.2pt)); draw((3,3)--(3,0),linewidth(1.2pt)); draw((0,1)--(4,1),linewidth(1.2pt)); draw((4,2)--(0,2),linewidth(1.2pt)); dot((0,0),ds); label("$A$", (-0.3,-0.36),NE*lsf); dot((4,3),ds); label("$B$", (4.16,3.1),NE*lsf); clip((-4.3,-10.94)--(-4.3,6.3)--(16.18,6.3)--(16.18,-10.94)--cycle); [/asy]

In a rectangle with vertices $(0, 0), (0, 2), (n,0),(n, 2)$, ($n$ is a positive integer) find the number of longest paths starting from $(0, 0)$ and arriving at $(n, 2)$ which satisfy the following: $\bullet$ At each movement, you can move right, up, left, down by $1$. $\bullet$ You cannot visit a point you visited before. $\bullet$ You cannot move outside the rectangle.