Bishops and permutations on chessboard

[HighPhy]

Let $n$ be a positive integer. Initially, a bishop is placed in each square of the top row of a $2^n \times 2^n$ chessboard; those bishops are numbered from $1$ to $2^n$ from left to right. A jump is a simultaneous move made by all bishops such that each bishop moves diagonally, in a straight line, some number of squares, and at the end of the jump, the bishops all stand in different squares of the same row.

Find the total number of permutations σ of the numbers $1, 2, \ldots, 2^n$ with the following property: There exists a sequence of jumps such that all bishops end up on the bottom row arranged in the order $\sigma(1), \sigma(2), \ldots, \sigma(2^n)$, from left to right.




In this case, adjacent corners have opposite colors. Counting squares along pairs of adjacent sides, we will find $\frac{1}{2}(2^n+2^n)$ black squares on one pair of sides and $\frac{1}{2}(2^n+2^n) - 1$ on the other, so there can be at most $\frac{1}{2}(2^n+2^n) - 1$ bishops on black squares. Same for white.

This puts an upper bound on the number of bishops at
$$2\left(\frac{1}{2}(2^n+2^n) - 1\right)=2^n+2^n−2=2(2^n−1).$$

Hence, how do I formally prove that the total permutations are $\sigma=2^n−1$?

 

[PeroK]

Let $n$ be a positive integer. Initially, a bishop is placed in each square of the top row of a $2n \times 2n$ chessboard; those bishops are numbered from $1$ to $2^n$ from left to right.

Why is that $2^n$ bishops? And not only $2n$?

 

[HighPhy]

Why is that $2^n$ bishops? And not only $2n$?

Sorry, it's a typo. Corrected.

 

[PeroK]

Hence, how do I formally prove that the total permutations are $\sigma=2^n−1$?

Do you have any thoughts? I think I've checked it manually for $n = 1, 2, 3, 4$. Doing that gives me something to go on. Looks tough!

 

[HighPhy]

Do you have any thoughts?

Unfortunately, not yet. I will work on it. However, I hope to count on your help and that of others!

 

[mfb]

You know the number of bishops and half of them stand on white and black squares.

Choose e.g. n=3 and see what jumps are possible. There are not that many options that satisfy all the jump conditions.

What happens if the largest possible jump is done once? What happens if it's not done? See if you can relate either one to a smaller problem.

 

[PeroK]

Hence, how do I formally prove that the total permutations are $\sigma=2^n−1$?

The total should be $2^{n-1}$. Another typo?

 

[HighPhy]

The total should be $2^{n-1}$. Another typo?

Yes, another typo... Sorry again.

 

[PeroK]

Yes, another typo... Sorry again.

Have you had any ideas? Have you studied group theory at all? Products of transpositions or disjoint cycles?

 

[HighPhy]

Have you had any ideas?

The only idea I had was as follows.
Reindex to $0$ through $2^n-1$. Notice that the possible jumps map $k$ to $k\oplus2^m$ and move $2^m$ rows, so $\sigma(k)=k\oplus z$ for all odd $0\leq z<2^n$ by parity, giving a total of $2^{n-1}$ possible $\sigma$.
But this proof isn't formal and doesn't convince me.

 

[PeroK]

The only idea I had was as follows.
Reindex to $0$ through $2^n-1$. Notice that the possible jumps map $k$ to $k\oplus2^m$ and move $2^m$ rows, so $\sigma(k)=k\oplus z$ for all odd $0\leq z<2^n$ by parity, giving a total of $2^{n-1}$ possible $\sigma$.
But this proof isn't formal and doesn't convince me.

It's nothing like that. It's about permutations expressed as a product of disjoint cycles.

 

[HighPhy]

It's nothing like that. It's about permutations expressed as a product of disjoint cycles.

Why is my proof above, though not rigorous, incorrect?

 

[PeroK]

Why is my proof above, though not rigorous, incorrect?

I don't even begin to understand your proof!

 

[PeroK]

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 \ 3)(2 \ 4)(5 \ 7)(6 \ 8)$$$$\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$.

 

[HighPhy]

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?

 

[PeroK]

I'm not sure I have the time to check that. My approach was this. I'll stick with the $\sigma_k$ notation.

Note that $\sigma_1$ swaps bishops within each pair. Note also that each pair of bishops stay together under all the $\sigma_k$.

Also, $\sigma_2$ swaps sets of two bishops. And, $\sigma_3$ swaps sets of four bishops.

Let's look at the only final permutation for $n = 1$:$$P_1 =
\begin{bmatrix}
2& 1
\end{bmatrix}
$$The two final permutations for $n=2$ are:$$P_2 = \begin{bmatrix}

2& 1&4&3\\
4&3&2&1

\end{bmatrix}$$And, the four final permutations for $n =3$ are:
$$P_3 = \begin{bmatrix}
2&1&4&3&6&5&7&8\\
4&3&2&1&8&7&6&5\\
6&5&8&7&2&1&4&3\\
8&7&6&5&4&3&2&1\\
\end{bmatrix}$$And you can see that this has the form:
$$P_3 = \begin{bmatrix}
P_2(1,2,3,4)&P_2(5,6,7,8)\\
P_2(5,6,7,8)&P_2(1,2,3,4)\\
\end{bmatrix}$$And, we can immediately write down the final permutations for $n = 4$:
$$P_4 = \begin{bmatrix}
P_3(1-8)&P_3(9-16)\\
P_3(9-16)&P_3(1-8)\\
\end{bmatrix}$$You can prove that algebraically however you like. Note that, you can apply $\sigma_4$ at most once. If you do not apply $\sigma_4$, you get some permutation from $P_3$ applied to the first 8 bishops and to the second 8 bishops. And, if you apply $\sigma_4$ once, then you simply swap the first and second sets of eight bishops.

Hence, by induction there are twice as many solutions every time you double the size of the board. Or, double the number of bishops, if you prefer.

 

[HighPhy]

I'm not sure I have the time to check that.

Let me know if you read it and what you think of it once you have read it.

You know the number of bishops and half of them stand on white and black squares.

Choose e.g. n=3 and see what jumps are possible. There are not that many options that satisfy all the jump conditions.

What happens if the largest possible jump is done once? What happens if it's not done? See if you can relate either one to a smaller problem.

I would be interested to see this proof if it is different from @PeroK's!

 

[PeroK]

You know the number of bishops and half of them stand on white and black squares.

Choose e.g. n=3 and see what jumps are possible. There are not that many options that satisfy all the jump conditions.

What happens if the largest possible jump is done once? What happens if it's not done? See if you can relate either one to a smaller problem.

This sounds like a precis of my solution!

 

[HighPhy]

@PeroK, @mfb Have you read my solution in post #15? However, I present below another proof on the basis of yours. I hope it is fine.

First, suppose that the bishops can displace by $k$ rows down. Then, it follows that the first $k$ bishops have to displace by $+k$ horizontally, and the next $k$ are consequently forced to displace by $-k$. This gives us a "connected block" of $2k$ bishops: an example with $k=3$ is shown below.

Repeating this on the remaining bishops, we find that $2k \mid 2^n$, or $k \mid 2^{n-1}$. The construction for such $k$ recycles the connected blocks idea.

Using the construction for $k \mid 2^{n-1}$, it is easy to see that the move of displacing by $k$ rows down is equivalent to toggling the $(1 + \log_2 k)$-th digit from the right in the binary representation of the $x$-coordinate of a bishop, where we set the $x$-coordinates to be from $0$ to $2^n-1$.

Thus, we realize that the end permutation corresponds to toggling some of the digits of the binary representations of the numbers. In particular, each end permutation corresponds to some subset of $S$ of $\{2^0, 2^1, \dots, 2^{n-1}\}$ such that there exists a linear combination of the elements of $S$ with odd coefficients that sums to $2^n-1$. We can construct a bijection with such $S$ and the binary representations of all odd positive integers less than or equal to $2^n - 1$, which is $2^{n-1}$.

 

[PeroK]

@PeroK, @mfb Have you read my solution in post #15? However, I present below another proof on the basis of yours. I hope it is fine.

First, suppose that the bishops can displace by $k$ rows down. Then, it follows that the first $k$ bishops have to displace by $+k$ horizontally, and the next $k$ are consequently forced to displace by $-k$. This gives us a "connected block" of $2k$ bishops: an example with $k=3$ is shown below.

View attachment 342544


Repeating this on the remaining bishops, we find that $2k \mid 2^n$, or $k \mid 2^{n-1}$. The construction for such $k$ recycles the connected blocks idea.

Using the construction for $k \mid 2^{n-1}$, it is easy to see that the move of displacing by $k$ rows down is equivalent to toggling the $(1 + \log_2 k)$-th digit from the right in the binary representation of the $x$-coordinate of a bishop, where we set the $x$-coordinates to be from $0$ to $2^n-1$.

Thus, we realize that the end permutation corresponds to toggling some of the digits of the binary representations of the numbers. In particular, each end permutation corresponds to some subset of $S$ of $\{2^0, 2^1, \dots, 2^{n-1}\}$ such that there exists a linear combination of the elements of $S$ with odd coefficients that sums to $2^n-1$. We can construct a bijection with such $S$ and the binary representations of all odd positive integers less than or equal to $2^n - 1$, which is $2^{n-1}$.

The whole proof seems to hinge on one bishop moving $k$ rows. What about the other bishops? What about multiple moves one after the other? That prove doesn't seem to fit with the structure of the problem. It's not convincing. A proof has to convince the reader.

Moreover, the conclusion seems to appear from nowhere. The bit I've underlined. Where did that come from?

 

[berkeman]

Thread closed for Moderation and review of references...

 

[berkeman]

OP has been banned for multiple reasons, so thread is reopened for a bit.

 

[kuruman]

This problem is from a recent UKMT competition and is posted here
https://ukmt.org.uk/wp-content/uploads/2024/03/Hypatia-Problem-March-2024.pdf
with a proposed solution posted here
https://ukmt.org.uk/wp-content/uploads/2024/03/Hypatia-Solution-March-2024-FINAL.pdf

 

[PeroK]

This problem is from a recent UKMT competition and is posted here
https://ukmt.org.uk/wp-content/uploads/2024/03/Hypatia-Problem-March-2024.pdf
with a proposed solution posted here
https://ukmt.org.uk/wp-content/uploads/2024/03/Hypatia-Solution-March-2024-FINAL.pdf

I'm not particularly impressed by that solution. In particular, the solution seems to rely only on the fact that each bishop can finish in $2^{n-1}$ places. But, why can't there be two or more possible permutations with the first bishop ending up in a given position? We have to justify why there is precisely only one possible solution with the first bishop ending up in the second place, for example.

Note that if the number of rows in not $2^n$ then there are multiple such solutions. E.g. for a 6x6 board the permutations $\sigma_1$ and $\sigma_3$ do not commute. This messes up with the proposed solution.

There seems to me a lot that isn't fully justified in that proof.