$n$ people (with names $1,2,\dots,n$) are around a table. Some of them are friends. At each step 2 friend can change their place. Find a necessary and sufficient condition for friendship relation between them that with these steps we can always reach to all of posiible permutations.
Problem
Source: Iran TST 2002
Tags: induction, group theory, combinatorics proposed, combinatorics
27.09.2006 21:39
In other words, we are looking for necessary and sufficient conditions on a set $\Lambda$ of permutations in $S_{n}$ (the $n$'th symmetric group) so that they generate $S_{n}$. I think a necessary and sufficient condition is the following: Let $G=G(\Lambda)$ be the graph on $n$ vertices obtained by connecting $i,j$ iff the transposition $(i,j)$ belongs to $\Lambda$. Then $\Lambda$ generates $S_{n}$ iff $G$ is connected. First we show that the connectedness of $G$ is necessary. Indeed, the permutations in the group generated by $\Lambda$ cannot interchange two vertices in different connected components. Conversely, we have to show that the connectedness of $G$ is sufficient. Clearly, it suffices to prove that $\Lambda$ generates $S_{n}$ when $G$ is a tree. This is clear for small values on $n$ ($n\le 2$, say), and then we can use induction on $n$. $G$ has at least two terminal vertices, $x,y$, with adjacent edges $xu, yv$ respectiely. If we eliminate the vertex $x$ and the edge $xu$ from $G$, we obtain another tree. This corresponds to eliminating the transposition $(x,u)$ from $\Lambda$. By the induction hypothesis, $\Lambda\setminus\{(x,u)\}$ generates all permutations on the vertices different from $x$. Similarly, $\Lambda\setminus\{(y,v)\}$ generates all permutations on the vertices different from $y$. It's easy to see, for example, that every transposition from $S_{n},n\ge 3$ other than $(x,y)$ is a product of two permutations, one fixing $x$ and the other one fixing $y$, and the conclusion follows easily.
25.09.2021 07:49
Nice problem I analize when the people are in a line.we consider a graph where the vertices are people and the edges are friendship. The answer is for any two vertices there exists a path, i.e. the graph is conex Is necessary because the people in a component conex always be in the positions of the other people that are in the same component conex (just see the invariant when make an operation. Now analize what happen if $(X, Y)$ and $(X, Z)$ are edges of the graph. We can make operations in the following order: between $X$ and $Y$, $X$ and $Z$, $X$ and $Y$. Note that $Y$ and $Z$ have changed their positions. Now we will draw red edges between two people that can change their positions. By the above algorithm, basically we have that if in a triangle there are two red edges then the third edge will be red. Finally is clear that all edges of the graph will be red (because the graph is conex) so the people can change positions to get any permutation. Edit: For the case of the people on a circle is the same but one person can be not connected with any person. But is not possible have two conex component with 2 or more vertexes (is not large to explain it, but it's not interesting)