Problem

Source: RMM 2024 Problem 1

Tags: RMM, combinatorics, Bishop, chess, permutations, Process



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