Romanian Master of Mathematics

First solution. The required number is $2^{n-1}$. On a jump, every bishop moves the same number of rows up or down; call this number of rows the length of the jump.

Step 1. We show that the length of any jump is of the form $2^d$ for some integer $d\le n-1$. Assign each bishop the number of the column it is situated on before the jump. Let $k$ be the length of the jump; then each bishop's column number either increases by $k$, or decreases by $k$ in the jump. Thus, bishops 1, 2, \ldots, $k$ should move to columns $k+1$, $k+2$, \ldots, $2k$, as they cannot move leftwards. On the other hand, after the jump columns 1, 2, \ldots, $k$ should be filled by the bishops $k+1$, $k+2$, \ldots, $2k$. So the leftmost $2k$ bishops still fill the columns 1, 2, \ldots, $2k$ after the jump.

Repeating the argument shows that the next $k$ bishops move rightwards, and the next $k$ bishops beyond move leftwards, and so on and so forth. Finally, the bishops all split into contiguous groups of length $2k$, and in each group the leftmost $k$ bishops move rightwards, whereas the rightmost $k$ bishops move leftwards. Hence $2k\mid 2^n$, so $k$ is indeed of the form $2^d$ with $d\le n-1$.

Step 2. To make a more explicit description of the column change during the jump, assign each column the $n$-digit binary expansion of less 1 its number, augmented with zeroes leftwards if necessary. It is then easily seen that a jump of length $2^d$ just switches the $d$-th digit from the left, 0 to 1 and vice versa. Thus, the resulting permutation also has the following form: For every $d=0,1,\dots ,n-1$, the $d$-th digit is either swapped for all bishops, or it is preserved for them all. Moreover, notice that the total length of all jumps is odd, so there will be an odd number of jumps of length 1. Hence the 0-th (the rightmost) digit will be switched anyway. This leaves the room for $2^{n-1}$ possible permutations.

Step 3. It remains to show that all $2^{n-1}$ permutations are indeed possible. Let us show how to reach any of them. Start by getting to the bottom row by downward jumps of lengths 1, 2, 4, ..., $2^{n-1}$ that will switch all $n$ digits. Now, if we want to switch the $i$-th digit back, $1\le i\le n-1$, make two upward jumps of length $2^{i-1}$, followed by a downward jump of length $2^i$. Combine such modifications for all possible digit combinations to get all desired permutations.

---

Alternative solution.

Second solution. Proceed until the end of Step 1 just like in the first solution. Then extend the board to a vertical strip of width $2^n$, this will not affect the result, as it will be seen at the end of the proof. We will show that any two jumps commute. Consider two jumps of length $p$ and $q$ with $p<q$, and call them the $p$-jump and the $q$-jump. As described in the first step, the bishops will be split in contiguous groups. For the $p$-jump, we look at groups of length $p$, call these $p$-groups; for the $q$-jump, we look at groups of length $q$, call these $q$-groups. Since $2p$ divides $q$, any $p$-group is fully contained in a single $q$-group, and a $q$-group contains an even number of $p$-groups. First, let's look at the first two $q$-groups, and denote by $g_1,\dots ,g_{2k}$ the $p$-groups contained in the first $q$-group, and $g_1^{\prime },\dots ,g_{2k}^{\prime }$ the $p$-groups contained in the second $q$-group, where $2k=q/p$. The $p$-jump will swap $g_{2i-1}$ with $g_{2i}$, and same for their $g^{\prime }$ counterparts, whereas a $q$-jump will swap $g_j$ with $g_j^{\prime }$. When putting these together, it follows that applying both jumps in either order gives the same result: $g_{2i-1}$ is swapped with $g_{2i}^{\prime }$ and $g_{2i}$ is swapped with $g_{2i-1}^{\prime }$. Repeat now the same argument for the next two $q$-groups, and so on and so forth, until the entire row will be accounted for. We will now establish a bijection from the odd numbers between 1 and $2^n-1$ to the desired permutations. Let $x=\sum 2^k{a}_k$ be an odd number between 1 and $2^n-1$, where each $a_k$ is either 0 or 1, in particular $a_0=1$. Perform $a_k$ jumps of length $2^k$ in increasing order of $k$, then perform $2^n-1-x$ additional jumps of length 1 in order to reach the final row. This will result in a permutation $\sigma$, and set $f(x)=\sigma$. This provides a well defined function $f$. To prove $f$ injective, it suffices to look at bishop numbered 1 and show that it will end up in position $x+1$. For any of jump of length $2^k$, this bishop will move rightwards, as its position just before the jump was $1+a_0+2a_1+...+2^{k-1}{a}_{k-1}\le 2^k$. Therefore, before the additional jumps of length 1, this bishop will reach position $x+1$. Any two jumps of same length cancel each other out, and there is an even number of additional jumps of length 1, so the final position will also be $x+1$. Consequently, $f$ is injective. To prove $f$ surjective, consider a $\sigma$ with the desired property, let $b_k$ be the number of jumps of length $2^k$, and let $a_k$ be the remainder of $b_k$ modulo 2. Since the total length of all jumps is odd, there has to be an odd number of jumps of length 1, so $a_0=1$. Let $x=\sum 2^k{a}_k$, and note that this is an odd number between 1 and $2^n-1$. From Step 2 in Solution 1, the order of the jumps does not matter. Since two consecutive jumps of same length cancel each other out, performing $a_k$ jumps of length $2^k$ is the same as performing $b_k$ jumps of length $2^k$. So $f(x)=\sigma$, as the $2^n-1-x$ additional jumps of length 1 at the end also cancel each other out.

---

Alternative solution.

Third solution. Run again Step 1 through in Solution 1. Look at the two halves $1,\dots ,2^{n-1}$ and $2^{n-1}+1,\dots ,2^n$ and let $h(i)=i\pm 2^{n-1}$ be the counterpart of $i$ in the other half, where the sign is chosen appropriately. A jump of length $2^{n-1}$ will swap the halves between themselves, so $i$ will be swapped with $h(i)$. From Step 1, it follows that any shorter jump will only perform swaps inside a single half, and will act the same way on the other half; specifically, if a jump swaps $i$ with $j$, it will also swap $h(i)$ with $h(j)$. Furthermore, applying two jumps of $2^{n-1}$ will just cancel each other out, regardless of any other jumps in between, because we swapped $i$ with $h(i)$ twice, and the inner configuration of each half is changed in the same way. Induct now on $n$. There are $2^{n-2}$ possible permutations for the $2^{n-1}\times 2^{n-1}$ board. Performing jumps of the same length on a $2^n\times 2^n$ board gives the same configuration in each of the two halves. Now we can either apply a jump of length $2^{n-1}$, which will swap the halves, or we can apply two jumps of length $2^{n-2}$, which will cancel each other. This provides a construction for $2^{n-1}$ permutations in the $2^n\times 2^n$ board. To show that these are the only ones, consider now a valid permutation for the $2^n\times 2^n$ board which is obtained from some jumps. First, discard the jumps of length $2^{n-1}$, then attempt to apply the rest on the $2^{n-1}\times 2^{n-1}$ board. If a jump would exit the board, then make the jump of the same length in the opposite direction instead, which will stay on the board because its length is at most $2^{n-2}$. Since the length is the same, the resulting bishop configuration is also the same. Since the total length of the moves executed so far is odd, we can make an even number of moves of length 1 in order to reach the final row of the $2^{n-1}\times 2^{n-1}$ board, and this will not change the configuration in the end. Therefore, we obtain a corresponding permutation for the $n-1$ case which describes the configuration in each of the halves. From there, the only variations are whether the halves are swapped or not, depending on whether the number of jumps of length $2^{n-1}$ was odd or even. So this valid permutation corresponds to one constructed in the earlier paragraph, which completes the induction.