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\)?
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
 Location:Dhaka, Bangladesh
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é
Henri Poincaré

 Posts:1
 Joined:Fri Feb 19, 2021 11:09 am
Re: BdMO National Higher Secondary 2020 P8
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
 Location:Dhaka, Bangladesh
Re: BdMO National Higher Secondary 2020 P8
Sorry that's a silly mistake. It should be, $n+1=14,n=13$tasnim_tamal wrote: ↑Thu Mar 11, 2021 1:24 pmI don't get this part where it says that n+1=24 & n=23
In the question it is given that n=14
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é
Henri Poincaré
Re: BdMO National Higher Secondary 2020 P8
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,14tasnim_tamal wrote: ↑Thu Mar 11, 2021 1:24 pmI don't get this part where it says that n+1=24 & n=23
In the question it is given that n=14
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 .
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
 Location:Dhaka, Bangladesh
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é
Henri Poincaré
Re: BdMO National Higher Secondary 2020 P8
2^nn1
=2^14141 (n=14)
=16369
=2^14141 (n=14)
=16369
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 $x1$ different positions or swap $x$ with $\{1,2,3,...,x1\}$ 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^{x1} 1$.
As we can demote any number $x \in S$
\begin{align*}
f(n) &= \sum_{x=1}^n g(x)\\
&= 2^{n1}1+2^{n2}1+...+2^01\\
&= \sum_{k=0}^{n1} 2^k  n
\end{align*}
A very simple induction can prove that $\sum_{k=0}^{n1} 2^k = 2^n 1$.
So $f(n) = 2^n  n  1$
For $n=14$, $f(14) = 2^{14}  14  1 = 16369$.
We can demote a number $x$ to $x1$ different positions or swap $x$ with $\{1,2,3,...,x1\}$ 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^{x1} 1$.
As we can demote any number $x \in S$
\begin{align*}
f(n) &= \sum_{x=1}^n g(x)\\
&= 2^{n1}1+2^{n2}1+...+2^01\\
&= \sum_{k=0}^{n1} 2^k  n
\end{align*}
A very simple induction can prove that $\sum_{k=0}^{n1} 2^k = 2^n 1$.
So $f(n) = 2^n  n  1$
For $n=14$, $f(14) = 2^{14}  14  1 = 16369$.