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)$
Problem
Source: INMO 2022 P3
Tags: INMO 2022, Arrangements
06.03.2022 11:56
Legendre Formula , and Counting works... I am not sure that my solution works , but I got a general formula for $\nu _{2} ( T(2k+1))$ .. ( and this was the only problem I could solve in Test
06.03.2022 11:56
$T(7)=80$. Could not formally write the complete proof of second part but it required to be deal with powers. @below I did the same thing for the part 2 but handling the combinatorial calculations was kinda the tricky part. How did you proceed after it like \[\frac{2^n(2^n-3)(2^n-5)\cdots}{(2^{n-1}-1)!}\]
06.03.2022 12:06
(a) $T(7) = 80$ (b) For $T(2^n -1)$, Observe that $a_1$ has to be $2^n - 1$ and then divide the remaining $2^n - 2$ elements into two groups, each group has $2^{n-1} - 1$ and you can induct. (c) I'm not sure for this part but you can make 2 subtree like things, the one starting with $a_2$ has $2^{n-1} + 1$ elements and the one starting with $a_3$ has $2^{n-1} - 1$ elements and you can recurse the formula for $v_2(T(2^n + 1))$
Attachments:

06.03.2022 12:08
I got $T(2^n-1)=\binom{2^n-1}{2^{n-1}-1}(T(2^{n-1}-1})^2$ iirc
06.03.2022 12:31
Even I had the same subtree logic, got the same recurrence , unfortunately was unable to write it in a detailed manner because I got the idea in the last 5 minutes
06.03.2022 12:32
T(7) is 80 and thats all i know ;-; and i fakesolved (b) i think smh
06.03.2022 12:37
I lose. I could only get parts (a) and (b). What I did was this: draw a digraph with vertices $a_1,\ldots, a_N$ and draw an edge $a_i\to a_j$ if $j=2i$ or $j=2i+1$. Then note that all the vertices in the new layer are different. Using the self-repeating structure of the diagraph. I argued \[T(2^{n+1}-1)=\binom{2^{n+1}-2}{2^n-1}T(2^n-1)^2\]
Attachments:

06.03.2022 12:41
I used induction to prove (b). Basically, the same as above. I utilized the perfect binary tree structure for (b) to prove the recurrence. The largest value had to be at the root of the tree and the two subtrees are independent of each other. Problem (c) involved using (b) Here is my recurrence formula for (c): $$g(n) = \binom{2 ^ n}{2 ^ {n - 1} + 1} \cdot g(n - 1) \cdot f(n - 1)$$where $f(n) = T(2 ^ n - 1)$ and $g(n) = T(2 ^ n + 1)$. Now use legendre's (just like (b)) and you get the difference of two adjacent elements. Let $h(x)$ denote the maximal power of $2$ dividing $x$ $$h(g(n)) = h(\binom{2 ^ n}{2 ^ {n - 1} + 1}) + h(g(n - 1)) + h(f(n - 1))$$ We now get $$h(g(n)) - h(g(n - 1)) = h((2 ^ n)!) - h((2 ^ {n - 1} - 1)!) - h((2 ^ {n - 1} + 1)!) + h(f(n - 1))$$ $$h(g(n)) - h(g(n - 1)) = 2 ^ {n - 1}$$$$h(g(n)) - (h(g(n - 2)) + 2 ^ {n - 2} - 1) = 2 ^ {n - 1} $$$$h(g(n)) - h(g(n - 2)) = 2 ^ {n - 2} + 2 ^ {n - 1}$$$$h(g(n)) - h(g(1)) = 2 ^ {1} + \cdots + 2 ^ {n - 1}$$$$h(g(n)) - h(g(1)) = 2 ^ n - 2$$$$h(g(n)) = 2 ^ n - 1$$
06.03.2022 12:44
Ninjasolver0201 wrote: $T(7)=80$. Could not formally write the complete proof of second part but it required to be deal with powers. @below I did the same thing for the part 2 but handling the combinatorial calculations was kinda the tricky part. How did you proceed after it like \[\frac{2^n(2^n-3)(2^n-5)\cdots}{(2^{n-1}-1)!}\] Use Legendre's formula for maximal power of 2 which divides the numerator and denominator, no need to expand the factorials. Expanding the factorials is soo JEE-like
06.03.2022 12:52
N1RAV wrote: Expanding the factorials is soo JEE-like Is this a personal attack?
06.03.2022 13:29
I am getting the same recursion but $2^n-1$ instead of $2^n-n$ for c) If $f(n)=\nu_2(T(2^n+1))$ then from $T(2^n+1)=\binom{2^n}{2^{n-1}-1} T(2^{n-1}-1)T(2^{n-1}+1)$ we get $f(n)=n+f(n-1)+(2^{n-1}-n)$, so $f(n)-f(n-1)=2^{n-1}$ I manually checked $n=2$ and think I am right.
06.03.2022 13:37
CANBANKAN wrote: I am getting the same recursion but $2^n-1$ instead of $2^n-n$ for c) If $f(n)=\nu_2(T(2^n+1))$ then from $T(2^n+1)=\binom{2^n}{2^{n-1}-1} T(2^{n-1}-1)T(2^{n-1}+1)$ we get $f(n)=n+f(n-1)+(2^{n-1}-n)$, so $f(n)-f(n-1)=2^{n-1}$ I manually checked $n=2$ and think I am right. I also got 2^n - 1 for part c
06.03.2022 13:45
CANBANKAN wrote: I am getting the same recursion but $2^n-1$ instead of $2^n-n$ for c) If $f(n)=\nu_2(T(2^n+1))$ then from $T(2^n+1)=\binom{2^n}{2^{n-1}-1} T(2^{n-1}-1)T(2^{n-1}+1)$ we get $f(n)=n+f(n-1)+(2^{n-1}-n)$, so $f(n)-f(n-1)=2^{n-1}$ I manually checked $n=2$ and think I am right. Sorry if i made a calculation mistake. Let me just recheck and edit. Sorry it was a calculation mistake
06.03.2022 13:53
hellomath010118 wrote: I lose. I could only get parts (a) and (b). What I did was this: draw a digraph with vertices $a_1,\ldots, a_N$ and draw an edge $a_i\to a_j$ if $j=2i$ or $j=2i+1$. Then note that all the vertices in the new layer are different. Using the self-repeating structure of the diagraph. I argued \[T(2^{n+1}-1)=\binom{2^{n+1}-2}{2^n-1}T(2^n-1)^2\] i did the same
06.03.2022 14:14
Aarth wrote: N1RAV wrote: Expanding the factorials is soo JEE-like Is this a personal attack? Yes mental and emotional attack ((
07.03.2022 13:37
I did this by Binary representation, recurrence and Legendre formula $T(7)$ is easy enough to find. Now let us find $T(2^n-1)$ $a_1$ should be $2^n-1$ ${a_2,a_3,.... a_{2^n-1}}$ can be divided into sets $A_{10}$ and $A_{11}$ where $A_{10}$ contains numbers whose binary begins with a 10. Now there are $T(2^{n-1}-1)$ ways to arrange $A_{10}$ and similarly $A_{11}$ so we get $T(2^n-1) = \binom{2^n-2}{2^{n-1}-1}\cdot {T(2^{n-1}-1)}^2$ and induct. Even I couldnt do part 3, but I did understand the tree solution.
07.03.2022 13:53
Btw, if my INMO paper is checked, will I be exempted from IOQM 2023 or PRMO 2023 if they decide to follow that pattern?
08.03.2022 07:35
For the sake of completeness, here's a full solution. Consider a graph with vertices as $1,2,\cdots,N$ and draw an arrow $i \rightarrow j$ if $j = 2i$ or $j = 2i+1$. For $N = 2^n - 1$, this actually is a binary tree with $n-1$ levels with all numbers in the range $[2^k, 2^{k+1})$ on the $k$th level. Clearly, we must have $a_1$ to be greater than any of the others and so $a_1 = 2^n - 1$. Note that to arrange the $a_i$, only the relative order matters, and not the fact that the numbers are $1,2,\cdots, N$. So we choose $2^{n-1} - 1$ numbers for each subtree, which can be done in $\binom{2^n - 2}{2^{n-1} - 1}$ ways. Now, each the numbers of each subtree can be arranged in $T(2^{n-1} - 1)$ ways, so we have the recurrence $$\boxed{T(2^n - 1) = \binom{2^n - 2}{2^{n-1} - 1}T(2^{n-1} - 1)^2}$$Let $v(N) = v_2(T(N))$, so we have $v(2^n - 1) = 2v(2^{n-1} -1) + v_2 \left(\binom{2^n - 2}{2^{n-1} - 1} \right)$ But we have $v_2(N!) = N - s_2(N)$ so the second term is just $2s_2(2^{n-1} - 1) - s_2(2^n - 2) = 2(n-1) - (n-1) = n-1$, so we have $v(2^n - 1) = 2v(2^{n-1} - 1) + n-1 = 2(2^{n-1} - (n-1) - 1) + n-2 = 2^n - n - 1$, by induction (base case being $n = 2$), so part (b) done. Now consider $N = 2^n +1$, this is the same as the previous case except we have two edges extra on one subtree, but the subtrees have sizes $2^{n-1} - 1$ and $2^{n-1} + 1$ so recursing again seems like it would work. In this case, once again, $a_1 = N$ and we choose numbers in $\binom{2^n}{2^{n-1} - 1}$ ways and arrange them in $T(2^{n-1}-1)$ and $T(2^{n-1}+1)$ ways respectively, so we have $$\boxed{T(2^n + 1) = \binom{2^n}{2^{n-1}-1} T(2^{n-1} -1)T(2^{n-1}+1)}$$ We have $v_2$ of the binomial in this case is $s_2(2^{n-1}+1) + s(2^{n-1}-1) - s(2^n) = 2 + n-1 - 1 = n$ and using the previous result we had, we have $v(2^n + 1) = n + (2^{n-1} - (n-1) - 1) + T(2^{n-1} + 1) = 2^{n-1} + T(2^{n-1} + 1)$, I claim $T(2^n +1) = 2^n - 1$ and this just follows by induction with base case $n = 1$ and using the previous line., that finishes part (c). Finally for part (a), we have $T(7) = \binom{6}{3} T(3)^2 = 20(2)^2 = 80$, done. $\blacksquare$
09.03.2022 12:54
Interesting.
18.03.2022 06:48
its pretty easy as compared to other two question
21.03.2022 11:45
Anybody has any idea about the marks distribution for part (a),(b) and (c)?
07.01.2024 11:24
My solution is same as (19) a)80 b)It is trivial by Induction. c)Here you get this recursion $$\boxed{T(2^n + 1) = \binom{2^n}{2^{n-1}-1} T(2^{n-1} -1)T(2^{n-1}+1)}$$Therefore $T(2^n + 1)$ = $2^n -1 $