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 $\sigma$ 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. Israel
Problem
Source: RMM 2024 Problem 1
Tags: RMM, combinatorics, Bishop, chess, permutations, Process
29.02.2024 23:33
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 $\boxed{2^{n-1}}$ possible $\sigma$.
01.03.2024 00:24
Number the columns $0$ thru $2^n-1$. It's easy to see by induction or whatnot that the "bishop moving" process is equivalent to picking a place value $i$ from $0$ to $n-1$, and toggling the $i$th binary digit of each bishop's column number. Define the value of a move as $i$, if it toggles the $i$th binary digit in the column number of each bishop. Moves of the same value that appear twice will cancel each other out, so the final permutation of our bishops is just determined by whether we make an even or odd number of moves of each value. We must make an odd number of moves of value $1$, since the bishops traverse an odd number of rows, but otherwise, the other $n-1$ parities can be anything. It follows that the answer is $2^{n-1}$.
01.03.2024 17:40
02.03.2024 06:27
04.03.2024 22:34
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 $\boxed{2^{n-1}}$. Done.
10.03.2024 04:02
Let the size of a jump be the number of rows down it moves the bishops. It's easy to see that we can only make jumps of size $2^k$ for $k < n$. A jump of size $2^k$ swaps adjacent groups of $2^k$ bishops, so the order of the jumps doesn't matter. Two jumps of the same size cancel each other out, so we can replace any jump of size $2^k$ with two jumps of size $2^{k-1}$, effectively deleting the jump. $2^n = 2^{n-1} + \dots + 1$, so we can choose whether to include a jump of size $2^k$ for each of $1 \leq k \leq n-1$. Therefore, the answer is $2^{n-1}$.
05.09.2024 18:37
Thought process is extremely important for this question, i like it. Fitst of all why do we have $2^n$ here?, try to perform a move from a row to a row that is a distance that contains an odd prime factor of row's ahead . You will notice that you really can't do this from a forcing algorithm to perform such move (i.e. looking where bishop $1$ goes, then $2$ then $3$ and so on) it must satisfy to cover the entire row so in fact the distance tells the movement of the bishops in "chunks", and since it has an odd prime factor it can't divide $2^n$ so you can only move $2^m$ rows ahead for some non-negative $m \le n-1$ (you can't achieve $m=n$ directly because of the bishops in the middle). The following observation that you can permute the process, is key and this is true because you can check by the "chunks" where each bishop is assigned so you can swap two processes that are next to each other and thus do that to swap any two. And also note that performing a move an even number of times is basically not performing a move at all (from this observation). The reason why this is so important is because then by a chessboard coloring a bishop keeps it's square color invariant so it only has $2^{n-1}$ possibilities in the otherside, but when we pick any of them the rest of the bishop movements are fixed because the sequence of moves can be permuted and that will change nothing in the end result!, so we can put the ones with the bigger moves at the start and check using the "chunks" for each move to realice that in the back-tracking there was only one way (after performing an optimization of repeating a move the least possible number of times (by transferring the repetitions to moves that move "the farest away" possible)) to get a bishop from a certain square to another, therefore there exists only $2^{n-1}$ possible permutations that can be achieved thus we are done .