MathDB

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

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 Statement