Ace academy test series question [closed]

Question

Answer 1

Let the A[5] = {2, 4,  5, 1, 3]

If you do the transformation as mentioned to get array B, we will get

B[5] = {4, 1, 5, 2, 3}
B is not sorted so (A) is false.

Option (B) is correct as array B is permutation of array A, Option (D) will be false.

Option (C) is false because if we do the same transformation on array B we will get same array as A.

Comments

Proof for C:

Case 1: When $A[i] = j$ and $A[j] = i$ for any two index of the array then for $B[A[i]] := i,$ we get $B[j] = i$ and $B[i] = j$. So array B is same as array A. Here, It does not matter how many times we perform this operation. Still, we can prove it as let, for first transformation, mapping is $\sigma_1$ and note that $\sigma_1^2 = e$ and suppose, mapping $\sigma_2$ is defined for second transformation which we can get as $\sigma_2= \sigma_1^3 = (\sigma_1^2) \sigma_1 = \sigma_1.$  

Case 2: Consider array A index to array A elements mapping as $\sigma_1$ and array B index to array B elements mapping as $\sigma_2$ then

$\sigma_2 = \sigma_1 (\sigma_1) = \sigma_1^2$

Here, we get $\sigma_2$ after first transformation which I am interpreting as $B[A[i]] = i$

Now, interpreting this transformation twice as $B[A[A[i]]] = i$ and suppose for this transformation, if I use mapping $\sigma_3$ then

$\sigma_3 = \sigma_2 (\sigma_2) = \sigma_2^2 = \sigma_1^4$

As we notice here, $\sigma_1^3 = e,$ (e is an identity mapping) and so,

$\sigma_3 = \sigma_1$

Hence, after, twice transformation, we get the original array.

For example, Consider the array $A[1...4] = [2,3,1,4]$

Consider mapping from array index to array elements.

Now, mapping $\sigma_1$ for array A is defined as: $ 1 \mapsto 2;\ 2 \mapsto 3;\ 3 \mapsto 1;\ 4 \mapsto 4;$

mapping $\sigma_2$ for array B is defined as: $ 1 \mapsto 3;\ 2 \mapsto 1;\ 3 \mapsto 2;\ 4 \mapsto 4;$

Now, mapping $\sigma_3$ after twice transformation will be defined as: $  1 \mapsto 2;\ 2 \mapsto 3;\ 3 \mapsto 1;\ 4 \mapsto 4;$

Here, you can see $\sigma_1^3 = e ; \ \sigma_2 = \sigma_1^2 ;\ \sigma_3 = \sigma_2^2 $

and so, $\sigma_3 = \sigma_1.$

Hence, after, twice transformation, we get the original array.