4
$\begingroup$

We start from the string $abcdef$ and We can edit it with the following rules:

1.$abcdef \Rightarrow adbecf$

2.$abcdef \Rightarrow daebfc$

Which string can't be accessed?

1.dbafec

2.fcbeda

3.cabefd

4.efdcab

5.fedcba

In these kind of problems we usually look for a common thing in every change of the the string.Which I can't do here.Also the answer in the book is string $5$.

Puzzling SE copy:https://puzzling.stackexchange.com/questions/55399/which-string-cant-accessed

$\endgroup$

2 Answers 2

8
+100
$\begingroup$

You can write the six letters on the six faces of a dice, with a opposed to f, b opposed to e and c opposed to d. Then the first move A corresponds to rotate the dice 90° around the axis through the centers of a and f. The second move B corresponds to rotate the dice 120° around the the axis through the common corner abd and the common corner cef. However, the 5th option is the mirror image of the dice, which cannot be reached by rotations of the dice (which are rigid rotations of the 3-dim space).

enter image description here

You can accept this geometric solution, or you can write the vectors of the center of the faces and the matrices corresponding to the moves: $$ a=\begin{pmatrix}1\\ 0\\ 0 \end{pmatrix},\quad b=\begin{pmatrix}0\\ 1\\ 0 \end{pmatrix},\quad c=\begin{pmatrix}0\\ 0\\ 1 \end{pmatrix},\quad d=\begin{pmatrix}0\\ 0\\ -1 \end{pmatrix},\quad e=\begin{pmatrix}0\\ -1\\ 0 \end{pmatrix},\quad f=\begin{pmatrix}-1\\ 0\\ 0 \end{pmatrix},\quad $$ The first move is $A=\begin{pmatrix}1&0&0\\ 0&0&-1\\ 0&1&0 \end{pmatrix}$ and the second move is $B=\begin{pmatrix}0&0&-1\\ 1&0&0\\ 0&-1&0 \end{pmatrix}$.

Note that $\det(A)=\det(B)=1$.

Then the first option corresponds to $\begin{pmatrix}0&0&-1\\ 0&1&0\\ 1&0&0 \end{pmatrix}$ and $\det\begin{pmatrix}0&0&-1\\ 0&1&0\\ 1&0&0 \end{pmatrix}=1$.

The second option corresponds to $\begin{pmatrix}-1&0&0\\ 0&0&1\\ 0&1&0 \end{pmatrix}$ and $\det\begin{pmatrix}-1&0&0\\ 0&0&1\\ 0&1&0 \end{pmatrix}=1$.

The third option corresponds to $\begin{pmatrix}0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}$ and $\det\begin{pmatrix}0&0&1\\ 1&0&0\\ 0&1&0 \end{pmatrix}=1$.

The fourth option corresponds to $\begin{pmatrix}0&-1&0\\ -1&0&0\\ 0&0&-1 \end{pmatrix}$ and $\det\begin{pmatrix}0&-1&0\\ -1&0&0\\ 0&0&-1 \end{pmatrix}=1$.

Finally, the fifth option corresponds to $\begin{pmatrix}-1&0&0\\ 0&-1&0\\ 0&0&-1 \end{pmatrix}$, but $\det\begin{pmatrix}-1&0&0\\ 0&-1&0\\ 0&0&-1 \end{pmatrix}=-1$.

So definitely the fifth option is not possible. It is not difficult to see that A and B generate all possible positions of the dice, hence the first four options (which correspond each to a certain position of the dice), can be generated by A and B. In particular, the first option is AB, the second option is BABA$^2$, the third option is BA$^2$ and the fourth option is A$^2$BA.

${\bf EDIT:}$

The invariant asked for in the OP is the determinant. You can compute it without knowing about matrices (but it is much more complicated). The invariant $\det$ is determined by two functions $F_1$ and $F_2$. There are three pairs of letters: $\{a,f\}$, $\{b,e\}$, $\{c,d\}$. The first function $F_1$ is the parity of the number of letters $a$, $b$ or $c$ that are in the second half of the string. For example, the first move has only the letter $c$ in the second half, so $F_1=(-1)^1 =-1$. Then we interchange the letters in the pairs, so that $a$, $b$ and $c$ are in the first half. Finally we compute the parity of the resulting permutation of $a$, $b$ and $c$. In the first move the resulting permutation is $(acb)$ so it has parity $F_2=(-1)^1=-1$. Finally, $\det=F_1 F_2$, so in the first move it is $\det=(-1)(-1)=1$.

The parity of a permutation of three elements is (-1) if it is a transposition (only two elements are interchanged) and is equal to 1 if it is the identity or the cyclic permutation of three elements. So $F_2(abc)=F_2(bca)=F_2(cab)=1$ and $F_2(acb)=F_2(bac)=F_2(cba)=-1$. Note that there is a standard notation for the the permutations, codifying them by numbers. So $(abc)$ corresponds to the identity, $(bca)$ corresponds to $(123)$ and $(cab)$ corresponds to $(132)$. Similarly $(acb)$ corresponds to $(23)$, $(bac)$ corresponds to $(12)$ and $(cba)$ corresponds to $(13)$.

For the second move $F_1=(-1)^2$, since there are two elements ($b$ and $c$) in the second half of the string. The resulting permutation after ordering the pairs is $(cab)$ (in the standard notation it is $(123)$), a cyclic permutation of three elements, so $F_2=1$. Hence $\det=F_1F_2=1$.

For the first option we have only $c$ in the second half, so $F_1=-1$. The resulting permutation after ordering the pairs is $(cba)$ (in the standard notation it is $(13)$), a transposition, so $F_2=-1$. Hence $\det=F_1F_2=1$.

For the second option we have only $a$ in the second half, so $F_1=-1$. The resulting permutation after ordering the pairs is $(acb)$ (in the standard notation it is $(23)$), a transposition, so $F_2=-1$. Hence $\det=F_1F_2=1$.

For the third option all elements $a$, $b$ and $c$ are in the first half, so $F_1=1$. The resulting permutation after ordering the pairs (in this case it is already ordered) is $(cab)$ (in the standard notation it is $(123)$), a cyclic permutation of three elements, so $F_2=1$. Hence $\det=F_1F_2=1$.

For the fourth option we the three elements are in the second half, so $F_1=(-1)^3=-1$. The resulting permutation after ordering the pairs is $(bac)$ (in the standard notation it is $(12)$), a transpostion, so $F_2=-1$. Hence $\det=F_1F_2=1$.

Now, for the fifth option the three elements are in the second half, so $F_1=(-1)^3=-1$. The resulting permutation after ordering the pairs is $(abc)$ (in the standard notation it is the identity), so $F_2=1$. Hence $\det=F_1F_2=-1$.

However, the determinat $\det$ is multiplicative, so the fifth option cannot be reached by composing the first and the second move.

$\endgroup$
3
  • $\begingroup$ Could you upload the image another where?My computer can't open pictures in SE sites. $\endgroup$ Sep 29, 2017 at 15:39
  • $\begingroup$ This question was written to find Invariant so I prefer showing me that Invariant and also we didn't start matrix so Your first option seems nice but It would be better if you do them in the string not in a dice! $\endgroup$ Sep 29, 2017 at 15:50
  • $\begingroup$ The invariant you asked for is the determinant. However, computing it without using matrices, is way more complicated. I added the computations.I suggest you learn about matrices and determinants, because they are nearly omnipresent in mathematics. If you want to use only strings, you have to learn about permutation groups.The geometric picture is simpler. I can send you a pdf file with the picture. $\endgroup$
    – san
    Sep 29, 2017 at 20:03
6
$\begingroup$

If you are acquainted with group theory, this problem seems tailor-made for permutation groups.

Your first rule correspond to the element $(2453)\in S_6$, while the second rule correspond to $(142)(356)$. Denote $G$ be the subgroup generated by these two elements. Some computations shows $|G|=24$, and no element of $G$ is a disjoint product of a $2$-cycle and $4$-cycle.

The 1st option corresponds to $(1463)$

2nd: $(16)(23)(45)$

3rd: $(132)(456)$

4th: $(15)(26)(34)$

5th: $(16)(2543)$

Therefore the 5th option cannot be reached.

In fact, it is not difficult to show $G\cong S_4$, but this seems irrelevant.

$\endgroup$
4
  • $\begingroup$ What do you mean by numbers? $\endgroup$ Sep 25, 2017 at 18:28
  • $\begingroup$ You can treat $a=1$, $b=2$ etc. But the numbers are more like action done on the string rather the string itself. $\endgroup$
    – pisco
    Sep 25, 2017 at 18:32
  • $\begingroup$ This is a olympiad first round problem I don't think it needs sth more than elementry combinatorics. $\endgroup$ Sep 25, 2017 at 18:35
  • $\begingroup$ I would like to see more elementary solution too. You only get $24$ different strings from these two rules, so it is possible to enumerate them all, but I doubt this will be the only method. $\endgroup$
    – pisco
    Sep 25, 2017 at 18:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .