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

$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)!}\]

(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:

I got $T(2^n-1)=\binom{2^n-1}{2^{n-1}-1}(T(2^{n-1}-1})^2$ iirc

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

T(7) is 80 and thats all i know ;-; and i fakesolved (b) i think smh

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:

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$$

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

N1RAV wrote: Expanding the factorials is soo JEE-like Is this a personal attack?

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.

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

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

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

Aarth wrote: N1RAV wrote: Expanding the factorials is soo JEE-like Is this a personal attack? Yes mental and emotional attack ((

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.

Btw, if my INMO paper is checked, will I be exempted from IOQM 2023 or PRMO 2023 if they decide to follow that pattern?

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$

Interesting.

its pretty easy as compared to other two question

Anybody has any idea about the marks distribution for part (a),(b) and (c)?

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 $