How Cheenta works to ensure student success?
Explore the Back-Story
Problems and Solutions from CMI Entrance 2022.  Learn More 

IOQM 2022 Part B Problem 3 I Binary Tree & Recursion

Try this beautiful Recursion Problem based on Binary Tree appeared in IOQM 2022 Part B, Problem 3.

IOQM 2022 Part B I Problem 3


For a positive integer $N$, let $T(N)$

denote the number of arrangements

of the integers $\\$ $1,2, \ldots, N$

into a sequence $a_{1}, a_{2}, \ldots, a_{N}$

such that

$a_{i}>a_{2 i}$ for all $i, 1 \leq i<2 i \leq N \\$

and

$a_{i}>a_{2 i+1}$,

for all $i, 1 \leq i<2 i+1 \leq 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\left(2^{n}-1\right)$,

show that $\\K=$ $2^{n}-n-1$.
(c) Find the largest non-negative

integer

$K$ so that

$2^{K}$ divides $T\left(2^{n}+1\right)$.

Key Concepts


Binary Tree

Recursion Relation

Induction

Suggested Book | Source | Answer


Problem Solving Strategies by Arthur Engel

IOQM 2022

$ (i) 80 $

$ (iii)$ The highest power of $2$ dividing $T\left(2^{n}+1\right)$ is $ 2^{n}-1 $

Try with Hints


Create a Binary Tree with nodes using the given numbers as the following rule:

At each node the root is greater than the child node

Observe a bijection between the these nodes and every possible valid arrangements

Observe that the maximum number will be the root. Now try to find how the subsequent nodes will be formed.

Leave the maximum number for the root. Then we would have \(2^{n}-2\) numbers.
Now they can be grouped into 2 groups of \(2^{n-1}-1\) numbers each.
Try to build a recursion using \(T(N)\).
Then observe
\[
2^{n-2}
{{2^{n}}\choose {2^{n-1}}}
=(2^{n}-1){{2^{n}-2}\choose{2^{n-1}-1}}
\]

Then find the highest power of \(2\) which divides\({{2^n}\choose {2^{n-1}}}.\)

Try to solve this similarly as the second part.

Then try to build a recursive relation of the highest power of 2 dividing $T(N)$ an solve it

Subscribe to Cheenta at Youtube


Try this beautiful Recursion Problem based on Binary Tree appeared in IOQM 2022 Part B, Problem 3.

IOQM 2022 Part B I Problem 3


For a positive integer $N$, let $T(N)$

denote the number of arrangements

of the integers $\\$ $1,2, \ldots, N$

into a sequence $a_{1}, a_{2}, \ldots, a_{N}$

such that

$a_{i}>a_{2 i}$ for all $i, 1 \leq i<2 i \leq N \\$

and

$a_{i}>a_{2 i+1}$,

for all $i, 1 \leq i<2 i+1 \leq 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\left(2^{n}-1\right)$,

show that $\\K=$ $2^{n}-n-1$.
(c) Find the largest non-negative

integer

$K$ so that

$2^{K}$ divides $T\left(2^{n}+1\right)$.

Key Concepts


Binary Tree

Recursion Relation

Induction

Suggested Book | Source | Answer


Problem Solving Strategies by Arthur Engel

IOQM 2022

$ (i) 80 $

$ (iii)$ The highest power of $2$ dividing $T\left(2^{n}+1\right)$ is $ 2^{n}-1 $

Try with Hints


Create a Binary Tree with nodes using the given numbers as the following rule:

At each node the root is greater than the child node

Observe a bijection between the these nodes and every possible valid arrangements

Observe that the maximum number will be the root. Now try to find how the subsequent nodes will be formed.

Leave the maximum number for the root. Then we would have \(2^{n}-2\) numbers.
Now they can be grouped into 2 groups of \(2^{n-1}-1\) numbers each.
Try to build a recursion using \(T(N)\).
Then observe
\[
2^{n-2}
{{2^{n}}\choose {2^{n-1}}}
=(2^{n}-1){{2^{n}-2}\choose{2^{n-1}-1}}
\]

Then find the highest power of \(2\) which divides\({{2^n}\choose {2^{n-1}}}.\)

Try to solve this similarly as the second part.

Then try to build a recursive relation of the highest power of 2 dividing $T(N)$ an solve it

Subscribe to Cheenta at Youtube


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
magic-wand