INMO 2022 Problem 3

For a positive integer $N$ , let $T(N)$ denote the number of arrangements of the integers $1, 2, \cdots N$ into a sequence $a_1, a_2, \cdots a_N$ such that $a_i > a_{2i}$ for all $i$ , $1 \le i < 2i \le N$ and $a_i > a_{2i+1}$ for all $i$ , $1 \le i < 2i+1 \le N$ . For example, $T(3)$ is $2$ , since the possible arrangements are $321$ and $312$ (a) Find $T(7)$ (b) If $K$ is the largest non-negative integer so that $2^K$ divides $T(2^n - 1)$ , show that $K = 2^n - n - 1$ . (c) Find the largest non-negative integer $K$ so that $2^K$ divides $T(2^n + 1)$