Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 8.0 Shortlist Prove it Romania

Let nn be a positive integer. Initially, a bishop is placed in each square of the top row of a 2n×2n2^n \times 2^n chessboard; those bishops are numbered from 1 to 2n2^n, from left to right. A jump is a simultaneous move made by all bishops such that the following conditions are satisfied:
* 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, 2n2^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 σ(1),σ(2),,σ(2n)\sigma(1), \sigma(2), \ldots, \sigma(2^n), from left to right.

Solutions — 3

Solution 1

First solution. The required number is 2n12^{n-1}. On a jump, every bishop moves the same number of rows up or down; call this number of rows the length of the jump.

Step 1. We show that the length of any jump is of the form 2d2^d for some integer dn1d \le n-1. Assign each bishop the number of the column it is situated on before the jump. Let kk be the length of the jump; then each bishop's column number either increases by kk, or decreases by kk in the jump.
Thus, bishops 1, 2, \ldots, kk should move to columns k+1k+1, k+2k+2, \ldots, 2k2k, as they cannot move leftwards. On the other hand, after the jump columns 1, 2, \ldots, kk should be filled by the bishops k+1k+1, k+2k+2, \ldots, 2k2k. So the leftmost 2k2k bishops still fill the columns 1, 2, \ldots, 2k2k after the jump.

Repeating the argument shows that the next kk bishops move rightwards, and the next kk bishops beyond move leftwards, and so on and so forth. Finally, the bishops all split into contiguous groups of length 2k2k, and in each group the leftmost kk bishops move rightwards, whereas the rightmost kk bishops move leftwards. Hence 2k2n2k \mid 2^n, so kk is indeed of the form 2d2^d with dn1d \le n-1.

Step 2. To make a more explicit description of the column change during the jump, assign each column the nn-digit binary expansion of less 1 its number, augmented with zeroes leftwards if necessary. It is then easily seen that a jump of length 2d2^d just switches the dd-th digit from the left, 0 to 1 and vice versa.
Thus, the resulting permutation also has the following form: For every d=0,1,,n1d = 0, 1, \dots, n-1, the dd-th digit is either swapped for all bishops, or it is preserved for them all.
Moreover, notice that the total length of all jumps is odd, so there will be an odd number of jumps of length 1. Hence the 0-th (the rightmost) digit will be switched anyway. This leaves the room for 2n12^{n-1} possible permutations.

Step 3. It remains to show that all 2n12^{n-1} permutations are indeed possible. Let us show how to reach any of them.
Start by getting to the bottom row by downward jumps of lengths 1, 2, 4, ..., 2n12^{n-1} that will switch all nn digits.
Now, if we want to switch the ii-th digit back, 1in11 \le i \le n-1, make two upward jumps of length 2i12^{i-1}, followed by a downward jump of length 2i2^i. Combine such modifications for all possible digit combinations to get all desired permutations.

Solution 2

Second solution. Proceed until the end of Step 1 just like in the first solution. Then extend the board to a vertical strip of width 2n2^n, this will not affect the result, as it will be seen at the end of the proof.
We will show that any two jumps commute. Consider two jumps of length pp and qq with p<qp < q, and call them the pp-jump and the qq-jump. As described in the first step, the bishops will be split in contiguous groups. For the pp-jump, we look at groups of length pp, call these pp-groups; for the qq-jump, we look at groups of length qq, call these qq-groups.
Since 2p2p divides qq, any pp-group is fully contained in a single qq-group, and a qq-group contains an even number of pp-groups. First, let's look at the first two qq-groups, and denote by g1,,g2kg_1, \dots, g_{2k} the pp-groups contained in the first qq-group, and g1,,g2kg'_1, \dots, g'_{2k} the pp-groups contained in the second qq-group, where 2k=q/p2k = q/p. The pp-jump will swap g2i1g_{2i-1} with g2ig_{2i}, and same for their gg' counterparts, whereas a qq-jump will swap gjg_j with gjg'_j. When putting these together, it follows that applying both jumps in either order gives the same result: g2i1g_{2i-1} is swapped with g2ig'_{2i} and g2ig_{2i} is swapped with g2i1g'_{2i-1}.
Repeat now the same argument for the next two qq-groups, and so on and so forth, until the entire row will be accounted for.
We will now establish a bijection from the odd numbers between 1 and 2n12^n - 1 to the desired permutations. Let x=2kakx = \sum 2^k a_k be an odd number between 1 and 2n12^n - 1, where each aka_k is either 0 or 1, in particular a0=1a_0 = 1. Perform aka_k jumps of length 2k2^k in increasing order of kk, then perform 2n1x2^n - 1 - x additional jumps of length 1 in order to reach the final row. This will result in a permutation σ\sigma, and set f(x)=σf(x) = \sigma. This provides a well defined function ff.
To prove ff injective, it suffices to look at bishop numbered 1 and show that it will end up in position x+1x+1. For any of jump of length 2k2^k, this bishop will move rightwards, as its position just before the jump was 1+a0+2a1+...+2k1ak12k1+a_0+2a_1+...+2^{k-1}a_{k-1} \le 2^k. Therefore, before the additional jumps of length 1, this bishop will reach position x+1x+1. Any two jumps of same length cancel each other out, and there is an even number of additional jumps of length 1, so the final position will also be x+1x+1. Consequently, ff is injective.
To prove ff surjective, consider a σ\sigma with the desired property, let bkb_k be the number of jumps of length 2k2^k, and let aka_k be the remainder of bkb_k modulo 2. Since the total length of all jumps is odd, there has to be an odd number of jumps of length 1, so a0=1a_0 = 1. Let x=2kakx = \sum 2^k a_k, and note that this is an odd number between 1 and 2n12^n - 1. From Step 2 in Solution 1, the order of the jumps does not matter. Since two consecutive jumps of same length cancel each other out, performing aka_k jumps of length 2k2^k is the same as performing bkb_k jumps of length 2k2^k. So f(x)=σf(x) = \sigma, as the 2n1x2^n - 1 - x additional jumps of length 1 at the end also cancel each other out.

Solution 3

Third solution. Run again Step 1 through in Solution 1.
Look at the two halves 1,,2n11, \dots, 2^{n-1} and 2n1+1,,2n2^{n-1}+1, \dots, 2^n and let h(i)=i±2n1h(i) = i \pm 2^{n-1} be the counterpart of ii in the other half, where the sign is chosen appropriately. A jump of length 2n12^{n-1} will swap the halves between themselves, so ii will be swapped with h(i)h(i). From Step 1, it follows that any shorter jump will only perform swaps inside a single half, and will act the same way on the other half; specifically, if a jump swaps ii with jj, it will also swap h(i)h(i) with h(j)h(j).
Furthermore, applying two jumps of 2n12^{n-1} will just cancel each other out, regardless of any other jumps in between, because we swapped ii with h(i)h(i) twice, and the inner configuration of each half is changed in the same way.
Induct now on nn. There are 2n22^{n-2} possible permutations for the 2n1×2n12^{n-1} \times 2^{n-1} board. Performing jumps of the same length on a 2n×2n2^n \times 2^n board gives the same configuration in each of the two halves. Now we can either apply a jump of length 2n12^{n-1}, which will swap the halves, or we can apply two jumps of length 2n22^{n-2}, which will cancel each other. This provides a construction for 2n12^{n-1} permutations in the 2n×2n2^n \times 2^n board.
To show that these are the only ones, consider now a valid permutation for the 2n×2n2^n \times 2^n board which is obtained from some jumps. First, discard the jumps of length 2n12^{n-1}, then attempt to apply the rest on the 2n1×2n12^{n-1} \times 2^{n-1} board. If a jump would exit the board, then make the jump of the same length in the opposite direction instead, which will stay on the board because its length is at most 2n22^{n-2}. Since the length is the same, the resulting bishop configuration is also the same. Since the total length of the moves executed so far is odd, we can make an even number of moves of length 1 in order to reach the final row of the 2n1×2n12^{n-1} \times 2^{n-1} board, and this will not change the configuration in the end. Therefore, we obtain a corresponding permutation for the n1n-1 case which describes the configuration in each of the halves. From there, the only variations are whether the halves are swapped or not, depending on whether the number of jumps of length 2n12^{n-1} was odd or even. So this valid permutation corresponds to one constructed in the earlier paragraph, which completes the induction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.