## BdMO National Higher Secondary 2020 P8

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Higher Secondary 2020 P8
$$1, 2, 3, \cdots , n$$-এর একটা বিন্যাসকে কাওয়ায়ি বলা হবে যদি সেই বিন্যাসে কেবল একটা সংখ্যাই থাকে যেটা সে যে অবস্থানে আছে, তার চেয়ে বড়। যেমন: $$1, 4, 3, 2$$ একটা কাওয়ায়ি বিন্যাস কারণ এতে $$4$$-ই একমাত্র সংখ্যা যেটা সে যে অবস্থানে আছে (অবস্থান $$2$$), তার চেয়ে বড়। যদি $$n=14$$ হয়, তাহলে কতগুলো কাওয়ায়ি বিন্যাস আছে?

We call a permutation of the numbers $$1, 2, 3, \cdots , n$$ kawaii if there is exactly one number that is greater than its position. For example: $$1, 4, 3, 2$$ is a kawaii permutation (when $$n=4$$) because only the number $$4$$ is greater than its position $$2$$. How many kawaii permutations are there if $$n=14$$?
This section is intentionally left blank.

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm

### Re: BdMO National Higher Secondary 2020 P8

The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

tasnim_tamal
Posts:1
Joined:Fri Feb 19, 2021 11:09 am

### Re: BdMO National Higher Secondary 2020 P8

Mehrab4226 wrote:
Wed Feb 10, 2021 10:12 pm
I don't get this part where it says that n+1=24 & n=23
In the question it is given that n=14

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm

### Re: BdMO National Higher Secondary 2020 P8

tasnim_tamal wrote:
Thu Mar 11, 2021 1:24 pm
Mehrab4226 wrote:
Wed Feb 10, 2021 10:12 pm
I don't get this part where it says that n+1=24 & n=23
In the question it is given that n=14
Sorry that's a silly mistake. It should be, $n+1=14,n=13$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Zafar
Posts:10
Joined:Thu Dec 03, 2020 8:57 pm

### Re: BdMO National Higher Secondary 2020 P8

tasnim_tamal wrote:
Thu Mar 11, 2021 1:24 pm
Mehrab4226 wrote:
Wed Feb 10, 2021 10:12 pm
I don't get this part where it says that n+1=24 & n=23
In the question it is given that n=14
what about 3,1,2,4 with your idea of solution ? you didn't count some permutations like 3,1,2,4,5,6,7,8,9,10,11,12,13,14

131033
Posts:2
Joined:Mon Mar 15, 2021 9:43 am

### Re: BdMO National Higher Secondary 2020 P8

I think that is 14.If we take n=3,then numbers are 1,2,3
then , the kayayi sequences are 1,3,2
2,1,3
3,1,2
Again if we take n=4,then the numbers are 1,2,3,4
Then the sequences are ; 1,2,4,3
2,1,3,4
3,1,2,4
4,1,2,3
we can see that every time the kayayi sequece number is equal to n .
that is why , if n=14,
the answer will be 14 .

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm

### Re: BdMO National Higher Secondary 2020 P8

Thank you for catching that bug.
You might ask how did I get the claim, it was a conjecture because it seemed correct for the first few values of n.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

M.R Niloy
Posts:1
Joined:Wed Mar 31, 2021 9:02 am

### Re: BdMO National Higher Secondary 2020 P8

2^n-n-1
=2^14-14-1 (n=14)
=16369

Unknown
Posts:1
Joined:Thu Oct 07, 2021 12:15 am

### Re: BdMO National Higher Secondary 2020 P8

Let $S \rightarrow \{1,2,3,...,n\}, f(n) =$ the number of total permutations satisfying the given condition and $g(x)$ = the number of total possible permutations demoting a number $x \in S$.
We can demote a number $x$ to $x-1$ different positions or swap $x$ with $\{1,2,3,...,x-1\}$ and we can't change position of a number which is greater than $x$.
Assume that we are not demoting $x$ rather we are promoting or changing position of the numbers smaller than $x$. Now for each number smaller than $x$, there are 2 possible results. Either it will be promoted or it will hold its place. But all numbers can't hold its position at the same time. So $g(x) = 2^{x-1} -1$.
As we can demote any number $x \in S$
\begin{align*}
f(n) &= \sum_{x=1}^n g(x)\\
&= 2^{n-1}-1+2^{n-2}-1+...+2^0-1\\
&= \sum_{k=0}^{n-1} 2^k - n
\end{align*}
A very simple induction can prove that $\sum_{k=0}^{n-1} 2^k = 2^n -1$.
So $f(n) = 2^n - n - 1$
For $n=14$, $f(14) = 2^{14} - 14 - 1 = 16369$.