Bishops and permutations

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Bishops and permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: RMM 2024 Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1220 posts

#1 h Feb 29, 2024, 7:57 PM • 2 Y

Y by Phorphyrion, Zfn.nom-_nom

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

This post has been edited 1 time. Last edited by Assassino9931, Mar 4, 2024, 10:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7326 posts

DottedCaculator

#2 h Feb 29, 2024, 8:33 PM • 1 Y

Y by khina

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3441 posts

#3 h Feb 29, 2024, 9:24 PM • 1 Y

Y by ATGY

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}$ .

This post has been edited 2 times. Last edited by ihatemath123, Mar 1, 2024, 2:50 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1386 posts

#4 h Mar 1, 2024, 2:40 PM

Y by

Solution

This post has been edited 15 times. Last edited by VicKmath7, Mar 2, 2024, 3:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3787 posts

vsamc

#5 h Mar 2, 2024, 3:27 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#7 h Mar 4, 2024, 7:34 PM • 2 Y

Y by TheBlackPuzzle913, Radmandookheh

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.

https://cdn.discordapp.com/attachments/1069403895304040531/1214294379540385852/Screen_Shot_2024-03-04_at_11.32.18_AM.png?ex=65f896c4&is=65e621c4&hm=997671dfdfdd13deb23c574978cdd1d5f5a3e1a69bf11e49bda9322e586b1943&

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

120 posts

#8 h Mar 10, 2024, 1:02 AM

Y by

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1471 posts

#10 h Sep 5, 2024, 3:37 PM • 1 Y

Y by dolphinday

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 :cool:

:cool:

.

This post has been edited 2 times. Last edited by MathLuis, Sep 5, 2024, 3:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1687 posts

awesomeming327.

#11 h Mar 30, 2025, 11:56 PM

Y by

We can represent each jump by a bijective function
$f:\{1,2,\dots,2^n\}\to\{1,2,\dots,2^n\}$ such that the bishop that is on the $i$ th column goes to the $f(i)$ th column. A bishop move satisfies: $|f(i)-i|$ is the same as number of rows that the bishop traveled, so there exists a positive integer $c\le 2^n-1$ such that $|f(i)-i|=c$ .

Claim 1: The function $f$ exists if and only if $c\in \{1,2,4,8,\dots, 2^{n-1}\}$ , and this function is unique when it exists.

Note that $|f(c)-c|=c$ means that $f(c)=2c$ . In order for $2c$ to be in the range we must have $c\le 2^{n-1}$ .

When $i\le c$ , $f(i)$ can equal $i-c$ or $i+c$ . Since $i-c$ is not in the range, $f(i)=i+c$ . The same can be said for the inverse: $f^{-1}(i)=i+c$ . This implies that $f(\{1,2,\dots,2c\})=\{1,2,\dots,2c\}$ Therefore, when we remove the values from $1$ to $2c$ , $f$ is still a bijection. We can therefore apply the same logic inductively to get that we must be able to partition the domain of $f$ in to sets of size $2c$ , which means $2c\mid 2^n$ , or $c$ is a power of two. In each of these sets, the behavior of $f$ is determined. The claim is proved.

Let the functions that result from the previous claim be $f_i$ for $i=0$ , $1$ , $\dots$ , $n-1$ , where $f_i$ has $c=2^i$ . Each of these functions, when considering disjoint cycle form of the permutation, is in reality $2^{n-1}$ different cycles of size $2$ .

Claim 2: For any two functions $f_i$ and $f_j$ with $i\neq j$ , we have $f_i\circ f_j=f_j\circ f_i$ .

We will consider the behavior of each individual element. Suppose $i<j$ . Let $x$ and $x+2^i$ be mapped to each other. Then $f_j(x)\equiv x\pmod {2^{i+1}}$ so the behavior of $f_j(x)$ and $x$ should be the same under $f_i(x)$ , as should $f_j(x+2^i)$ and $x+2^i$ . That is,
$f_i(f_j(x+2^i))=f_j(x)=f_j(f_i(x+2^i))$ and less obviously,
$f_i(f_j(x))=f_j(x)+2^i=f_j(x+2^i)=f_j(f_i(x))$ where the second equality of the second line is from the fact that $x$ and $x+2^i$ are in the same half of the $2c$ -set of $f_j$ , so their behavior should be the same.

Since after all our bishop jumps, we must end up an odd number of rows away, so $f_0$ is used an odd number of times. Since $f_i\circ f_i=\text{id}$ for all $i$ , and since composition is commutative, we can view $\sigma$ as the composition of zero or one of the $f_i$ s for positive integer $i$ , and then $f_0$ .

Note that there are $2^{n-1}$ of these functions. To prove that they are all different, simply note that the first bishop is in a different location each time because if we order the functions in increasing order of index, we note that the first bishop is always in the first half of the first $2c$ -set, so it simply adds $2^i$ for each used $f_i$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a