- #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##?

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: