Find the number of permutations of $\{1,2,...,n\}$ like $\{a_1,...,a_n\}$ st for each $1 \leq i \leq n$: $$a_i | 2i$$
Problem
Source: Iran MO 2023 3rd round , Combinatorics exam P2
Tags: combinatorics
19.08.2023 13:34
I found the answer is $2^{\lfloor \frac{n}{2} \rfloor}$. Is it true?
19.08.2023 14:50
Yeah,you are right.
19.08.2023 15:25
For each odd $i$ with $1 \leq i \leq n$ consider the numbers $\{2^k \cdot i, : k \geq 0\} \cap \mathbb{Z}_{\leq n}$ It is easy to see that any permutation satisfying the conditions must permute the numbers within each group as well. To see this note that the group with the largest odd part must closed under the permutation, and then look at the group with the next smallest odd part (which then must also be fixed), and so forth. But if there are $m$ numbers in some group then there are $2^{m-1}$ ways to permute them. To see this, note that we must have disjoint cycles of the form $(2^{m-1} \cdot i \to 2^{m-2} \cdot i \to \cdots \to 2^{l} \cdot i \to 2^{m-1} \cdot i), (2^{l-1} \cdot i \to 2^{l-2} \cdot i \to \cdots \to 2^{l-1} \cdot i) , \cdots$ which is equivalent to splitting up the row of $m$ items into contiugous blocks, ie. placing dividers between the numbers, so there are $2^{m-1}$ ways to do so. Each group's ordering maybe assigned independently and there are $\lceil n/2 \rceil$ groups so in total there are $2^{n - \lceil n/2 \rceil} = 2^{\lfloor n/2 \rfloor}$ permutations.
29.06.2024 21:47
Answer: $2^{\lfloor \frac{n}{2}\rfloor}$ Define $f(x)$ to be the largest odd divisor of $x$. We claim that in a valid permutation we must have $f(a_i)=f(i)$ for all $i$. If not, then there must exist an $i$ for which $f(i)<f(a_i)$, a contradiction. Now we can separate our focus to each value of $f(x)$. Consider all values of $x$ at most $n$ for which $f(x)=l$. This set will take the form of $l,2l,2^2l,\dots,2^kl$ and must be mapped to itself. Starting from the top $a_{2^kl}$ can take on $2$ values and after it is assigned the next term can take on two values and so on until you reach $a_l$ which is forced. Thus there are $2^{k-1}$ possible permutations amongst this set. This is equivalent though to the number of even numbers that were in our set. Multiplying over all such sets we get that the answer is $2$ to the power of the number of even numbers at most $n$, as desired.