BdMO National Higher Secondary 2020 P8

[Mursalin]

\(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\)?

[Mehrab4226]

Let us try to count the number of kawaii permutations in $1,2,3,4, \cdots (n+1)$

Now let us take a choose any number(When in ascending order). Then we can find a kawaii permutation by exchanging it with any number less than itself. All the other numbers must stay in their same position or else we won't get a kawaii permutation. Now if the number we take is k then there are k-1 numbers we can exchange it with. Thus getting k-1 permutations. If we start by taking numbers $1,2,3, \cdots (n+1)$ and we will get $(1+2+3+ \cdots n)$ kawaii permutations. Thus the total number of kawaii permutations in an $(n+1)$ case is $\frac{n(n+1)}{2}$

Now $n+1 = 24, n = 23$
So, the total number of kawaii permutations $= \frac{23 \times 24}{2} = 276$ (ans)

[tasnim_tamal]

Let us try to count the number of kawaii permutations in $1,2,3,4, \cdots (n+1)$

Now let us take a choose any number(When in ascending order). Then we can find a kawaii permutation by exchanging it with any number less than itself. All the other numbers must stay in their same position or else we won't get a kawaii permutation. Now if the number we take is k then there are k-1 numbers we can exchange it with. Thus getting k-1 permutations. If we start by taking numbers $1,2,3, \cdots (n+1)$ and we will get $(1+2+3+ \cdots n)$ kawaii permutations. Thus the total number of kawaii permutations in an $(n+1)$ case is $\frac{n(n+1)}{2}$

Now $n+1 = 24, n = 23$
So, the total number of kawaii permutations $= \frac{23 \times 24}{2} = 276$ (ans)

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]

Let us try to count the number of kawaii permutations in $1,2,3,4, \cdots (n+1)$

Now let us take a choose any number(When in ascending order). Then we can find a kawaii permutation by exchanging it with any number less than itself. All the other numbers must stay in their same position or else we won't get a kawaii permutation. Now if the number we take is k then there are k-1 numbers we can exchange it with. Thus getting k-1 permutations. If we start by taking numbers $1,2,3, \cdots (n+1)$ and we will get $(1+2+3+ \cdots n)$ kawaii permutations. Thus the total number of kawaii permutations in an $(n+1)$ case is $\frac{n(n+1)}{2}$

Now $n+1 = 24, n = 23$
So, the total number of kawaii permutations $= \frac{23 \times 24}{2} = 276$ (ans)

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$

[Zafar]

Let us try to count the number of kawaii permutations in $1,2,3,4, \cdots (n+1)$

Now let us take a choose any number(When in ascending order). Then we can find a kawaii permutation by exchanging it with any number less than itself. All the other numbers must stay in their same position or else we won't get a kawaii permutation. Now if the number we take is k then there are k-1 numbers we can exchange it with. Thus getting k-1 permutations. If we start by taking numbers $1,2,3, \cdots (n+1)$ and we will get $(1+2+3+ \cdots n)$ kawaii permutations. Thus the total number of kawaii permutations in an $(n+1)$ case is $\frac{n(n+1)}{2}$

Now $n+1 = 24, n = 23$
So, the total number of kawaii permutations $= \frac{23 \times 24}{2} = 276$ (ans)

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]

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]

Thank you for catching that bug.

We, claim that the number of kawaii permutation of a set $\{1,2,3,\cdots n\} $ is $2^n-(n+1)$
Proof:
It is easy to see for the case $n = 1,2,3$
Let,
we have a set,$\{1,2,3, \cdots n\}$ the number of kawaii permutation is as we said earlier.
let us take another set, $\{1,2,3, \cdots n+1\}$ when $(n+1)$ is in $(n+1)^{th}$ position the number of kawaii permutations are $2^n-(n+1)$.Now we only have to think about when $(n+1)$ is in a smaller position than itself. Now if we change $(n+1)$ and n there are only $1=2^0$ kawaii permutations. Again if we change $(n+1)$ with $(n-1)$ then $(n-1)$ and $n$ has $2=2^1$ places to valid meaning $2^1$ kawaii permutations. You may have seen where we are going but we are going to do the same for a value $k$ to generalize things,

let us exchange $(n+1)$ with $k$,
so in the right of $n+1$ there are the numbers $k$ to $n$, a total of $n-k+1$Now, $n$ has $2$ valid positions. one is $(n+1)^{th}$ position the other is $n^{th}$ position. Similarly, $n-1$ has $2$ valid positions too because he can be in $(n-1),n,(n+1)$ but one of them is occupied by $n$. This process continues until we get to the $k+1. k+1$ will have $2$ valid positions too but the position of $k$ becomes fixed. So we have the number of valid kawaii permutation is $= 2 \times 2 \times \cdots (n-k)$ times $=2^{n-k}$
This process will continue until we change $n+1$ with $1$, then we will have $2^{n-1}$ valid kawaii.
So the total number of permutations $=2^0+2^1+2^2+ \cdots 2^{n-1}+2^{n}-(n+1)$
But, $2^0+2^1+2^2+cdots 2^n = 2^{n+1}-1$
So, total number of permutations $=2^{n+1}-n-1-1=2^{n+1}-(n+2)$ which is what we wanted.
So for $n=14$ the number of kawaii permutations is $2^{14}-15=16369$

You might ask how did I get the claim, it was a conjecture because it seemed correct for the first few values of n.

[M.R Niloy]

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

[Unknown]

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