PeroK said:
Here's how I approached the problem. In general, if we have a ##m \times m## chessboard and we want to do this thing with the bishops, where the bishops move ##k## rows, then this divides the ##m## squares into sets of ##2k## bishops. E.g.
For ##k = 1##, we must interchange bishops 1 and 2, interchange bishops 3 and 4 etc.
For ##k = 2##, we must interchange bishops 1 and 3, bishops 2 and 4, bishops 5 and 7, bishops 6 and 8 etc.
To do this, ##m## must be divisible by ##2k##.
Note that I worked this out because originally we had a ##2n \times 2n## chessboard.
If we take ##m = 2^n##, then this allows us all values of ##k## up to ##2^{n-1}##.
The next step was to express these permutations as products of disjoint cycles. Let's take ##n = 3##, so we have a regular 8 x 8 chessboard. We have:
$$\sigma_1 = (1 \ 2)(3 \ 4)(5 \ 6)(7 \ 8)$$$$\sigma_2 = (1 \ 4)(2 \ 3)(5 \ 8)(6 \ 7)$$$$\sigma_3 = (1 \ 5)(2 \ 6)(3 \ 7)(4 \ 8)$$Then, there are two things to notice. First, that all these permutations commute with each other. And, second, for all ##k##, ##\sigma_k^2 = 1## (the identity permutation).
Next, I worked out all the (4) final permutations for ##n = 3##. At that point I noticed something that allowed a simple, inductive proof for all ##n##.
OK, I'll try.
Claim I: A jump must have length (number of squares away vertically) ##2^t## for some ##0\leq t\leq n-1##.
Proof: Suppose a jump had length ##r##. Then, we have a permutation ##\pi: \{1, 2, \cdots, 2^n\} \mapsto \{1, 2, \cdots, 2^n\}## such that ##\pi(x) \in \{x-r, x+r\}## for every ##x\in \{1, 2, \cdots, 2^n\}##. Note that, because we must have ##\pi(x) \in \{1, 2, \cdots, 2^n\}##, we must have that ##\pi(1) = r+1##, ##\pi(2) = r+2##, ##\cdots##, ##\pi(r) = 2r##. Since ##1, 2, \cdots, r## must have preimages, we must have ##\pi(r+1) = 1##, ##\pi(r+2) = 2##, ##\cdots##, ##\pi(2r) = r##. So, we have that ##\{1, 2, \cdots, 2r\}## must be mapped to itself by ##r##. We can apply the same logic for ##\{2r+1, \cdots, 4r\}## (and this must exist otherwise by the above logic ##\pi## cannot be a bijection), and etc., which implies that ##\{1, 2, \cdots, 2^n\}## can be split into intervals of length ##2r##, and there cannot be any remainder because of the above logic, and so ##2r\mid 2^n##, and so ##r\mid 2^{n-1}##, implying the result. ##\square##
Now, let the permutation corresponding to a jump of length ##2^t## be ##\pi_t##. Note that all ##\pi_t##'s are involutions, because from the above logic, we can see that in an interval ##\{2^{t+1}k+1, \cdots, 2^{t+1}k+2^{t+1}\}##, we have that for ##1\leq x\leq 2^t##, ##2^{t+1}k+x## gets mapped to ##2^{t+1}k + x+2^t##, and vice versa. (This also implies that there is at most one permutation arising from doing a jump of length ##2^t##)
Claim II: ##\pi_r(\pi_t(x)) = \pi_t(\pi_r(x))## for all ##x\in \{1, 2, \cdots, 2^n\}##.
Proof: Without loss of generality, suppose ##r < t## (if ##r = t## then the result is trivially true). We have ##4## cases.
If ##\pi_t(x) = x+2^t## and ##\pi_r(x) = x+2^r##, then if we let ##R(x, y)## be the remainder when ##x## is divided by ##y## if ##y\nmid x##, and ##y## if ##y\mid x##, we have that ##R(x, 2^{t+1}) \leq 2^t## and ##R(x, 2^{r+1}) \leq 2^r## by the above. Note that $$R(\pi_t(x), 2^{r+1}) = R(x+2^t, 2^{r+1}) = R(x, 2^{r+1}) \leq 2^r \ \mathrm{as} \ t\geq r+1 \ ,$$ so ##\pi_r(\pi_t(x)) = x + 2^t + 2^r##. Note that since ##R(x, 2^{r+1}) \leq 2^r## and ##2^{r+1} \mid 2^t##, ##R(x, 2^{t+1}) \leq 2^t##, it follows that ##R(x, 2^{t+1}) \leq 2^t - 2^r##, so consequently $$R(\pi_r(x), 2^{t+1}) = R(x+2^r, 2^{t+1}) \leq 2^t,$$ and so ##\pi_t(\pi_r(x)) = x + 2^r + 2^t## and so the statement is true in this case.
If ##\pi_t(x) = x - 2^t## and ##\pi_r(x) = x+2^r##, then we have that ##P(x, 2^{t+1}) > 2^t## and ##P(x, 2^{r+1}) \leq 2^r##. Note that $$R(\pi_t(x), 2^{r+1}) = R(x-2^t 2^{r+1}) = R(x, 2^{r+1}) \leq 2^r \ \mathrm{as} \ t\geq r+1 \ ,$$ so ##\pi_r(\pi_t(x)) = x-2^t+2^r##. Note that since ##R(x, 2^{r+1}) \leq 2^r## and ##2^{r+1} \mid 2^{t+1}##, we have that ##R(x, 2^{t+1}) \leq 2^{t+1} - 2^r##. Therefore, ##2^t < R(x, 2^{t+1}) \leq 2^{t+1}-2^r##, so $$R(\pi_r(x), 2^{t+1}) = R(x+2^r, 2^{t+1}) > 2^t,$$ so ##\pi_t(\pi_r(x)) = x + 2^r-2^t## and so the statement is true in this case.
If ##\pi_t(x) = x+2^t## and ##\pi_r(x) = x-2^r##, then we have that ##P(x, 2^{t+1}) \leq 2^t## and ##P(x, 2^{r+1}) > 2^r##. Note that $$R(\pi_t(x), 2^{r+1}) = R(x+2^t, 2^{r+1}) = R(x, 2^{r+1}) > 2^r \ \mathrm{as} \ t\geq r+1\ ,$$ so ##\pi_r(\pi_t(x)) = x+2^t-2^r##. Note that since ##R(x, 2^{r+1}) > 2^r##, and ##2^{r+1} \mid 2^{t+1}##, we have that ##R(x, 2^{t+1}) > 2^r##. Therefore, we have that ##2^r < R(x, 2^{t+1}) \leq 2^t##, so $$R(\pi_r(x), 2^{t+1}) = R(x-2^r, 2^{t+1}) \leq 2^t,$$ so ##\pi_t(\pi_r(x)) = x-2^r+2^t## and so the statement is true in this case.
Finally, if ##\pi_t(x) = x-2^t## and ##\pi_r(x) = x-2^r##, then we have that ##P(x, 2^{t+1}) > 2^t## and ##P(x, 2^{r+1}) > 2^r##. Note that $$R(\pi_t(x), 2^{r+1}) = R(x-2^t, 2^{r+1}) = R(x, 2^{r+1}) > 2^r \ \mathrm{as} \ t\geq r+1\ ,$$ so ##\pi_r(\pi_t(x)) = x-2^t-2^r##. Note that since ##R(x, 2^{r+1}) > 2^r## and ##2^{r+1} \mid 2^t##, ##R(x, 2^{t+1}) > 2^t##, we have that ##R(x, 2^{s+1}) > 2^t + 2^r##. Therefore, we have that ##2^t+2^r < R(x, 2^{t+1}) \leq 2^{t+1}##, so $$R(\pi_r(x), 2^{t+1}) = R(x-2^r, 2^{t+1}) > 2^t,$$ and so ##\pi_t(\pi_r(x)) = x - 2^r - 2^t## and so the statement is true in this case.
So we've exhausted all cases and so our proof of Claim II is complete. ##\square##
To finish, note that combining this with the fact that each ##\pi_t## is an involution, it readily follows that each permutation ##\sigma## can be written as a composition of many ##\pi_t## for ##0\leq t \leq n-1##, and the order of the composition does not matter. Note that there must be an odd number of jumps of length ##1## because the bottom row is a length ##2^n-1## away and all other jumps have even length. Otherwise, each ##\pi_t## for ##1\leq t\leq n-1## can either appear an even number of times and odd number of times in the sequence, corresponding to appearing ##0## or ##1## times. Therefore, each permutation ##\sigma## can be expressed as ##\pi_0 \circ \pi_1^{0,1} \circ \pi_2^{0,1} \circ \cdots \circ \pi_{n-1}^{0,1}##, so there are at most ##2^{n-1}## of them.
To see that all of these permutations can be achieved, note that $$2^n = 2^{n-1} + 2^{n-2} + \cdots + 2^1 + 2^0$$(i.e. a jump of length ##2^{n-1}## followed by a jump of length ##2^{n-2}## plus etc.) corresponds to ##\pi_0\circ \pi_1\circ \cdots \circ \pi_{n-1}##, and if you want some ##\pi_t## for some ##1\leq t\leq n-1## to not appear in the composition, just replace ##2^t## with ##(2^{t-1} + 2^{t-1})## above; then this will correspond to no moves because we apply ##\pi_{t-1}^2 = \text{id}## twice.
Thus, we have shown that there are exactly ##2^{n-1}## permutations ##\sigma##, as desired.
##\blacksquare##
Do you think it's fine?
