Bishops and permutations on chessboard

In summary, the concept of bishops and permutations on a chessboard explores the unique movements and placements of bishops, which can only traverse diagonally. This leads to various arrangements and combinations of bishops on the board, highlighting the mathematical principles of permutations. The study emphasizes the strategic implications of bishop placement in chess, particularly in relation to controlling squares and influencing the game.
  • #1
HighPhy
89
8
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##?
 
Last edited:
Physics news on Phys.org
  • #2
HighPhy said:
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##?
 
  • Like
Likes BvU
  • #3
PeroK said:
Why is that ##2^n## bishops? And not only ##2n##?
Sorry, it's a typo. Corrected.
 
  • #4
HighPhy said:
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!
 
  • #5
PeroK said:
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!
 
  • #6
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.
 
  • Like
Likes PeroK
  • #7
HighPhy said:
Hence, how do I formally prove that the total permutations are ##\sigma=2^n−1##?
The total should be ##2^{n-1}##. Another typo?
 
  • #8
PeroK said:
The total should be ##2^{n-1}##. Another typo?
Yes, another typo... Sorry again.
 
  • #9
HighPhy said:
Yes, another typo... Sorry again.
Have you had any ideas? Have you studied group theory at all? Products of transpositions or disjoint cycles?
 
  • #10
PeroK said:
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.
 
  • #11
HighPhy said:
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.
 
  • #12
PeroK said:
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?
 
  • #13
HighPhy said:
Why is my proof above, though not rigorous, incorrect?
I don't even begin to understand your proof!
 
  • Like
Likes Vanadium 50
  • #14
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##.
 
Last edited:
  • #15
Poster has been reminded not to use AI chatbots to generate content for the technical PF forums.
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?
 
Last edited:
  • Wow
Likes PeroK
  • #16
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.
 
Last edited:
  • #17
PeroK said:
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.
mfb said:
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!
 
  • #18
mfb said:
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!
 
  • #19
@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.

67f4c6237b6b91b6f78d43586d32f44e43fb4ff7.png



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}##.
 
Last edited:
  • #20
HighPhy said:
@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?
 
  • #21
Thread closed for Moderation and review of references...
 
  • #22
OP has been banned for multiple reasons, so thread is reopened for a bit.
 
  • #24
kuruman said:
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.
 
  • Informative
  • Like
Likes kuruman and mfb

Similar threads

Replies
25
Views
3K
2
Replies
61
Views
7K
2
Replies
42
Views
8K
3
Replies
100
Views
9K
2
Replies
69
Views
6K
2
Replies
48
Views
10K
3
Replies
80
Views
7K
3
Replies
86
Views
11K
2
Replies
61
Views
9K
Back
Top