$3n$ people forming $n$ families of a mother, a father and a child, stand in a circle. Every two neighbours can exchange places except the case when a parent exchanges places with his/her child (this is forbidden). For what $n$ is it possible to obtain every arrangement of those people by such exchanges? The arrangements differing by a circular shift are considered distinct.
Problem
Source: Tuymaada 2023 Junior P7
Tags: combinatorics, Tuymaada
07.07.2023 19:36
10.07.2023 14:13
This is Junior P7, not the Senior one.
12.07.2023 11:42
this one is Junior P7, the senior P7 is the one with hexagonal pieces. (source= i'm a senior league contestant in this year's contest). Edit: it's already fixed
14.07.2023 17:44
This solution is similar to one of the contestants'. But he received 0 points with no reasonable explanation. Can you check it? Answer: no such $n$. Suppose true for $n=k>1$. Let's choose one family and color them in red. We have some sequence of moves to get from any configuration $A$ to any configuration $B$. Now we will delete the red family and get configurations $A'$ and $B'$. Any move involving a member of the red family in our sequence of moves we will skip. Then using this sequence of moves we can get from configuration $A'$ to configuration $B'$. Since $A$ and $B$ are any configuration of $k$ families same is true for $A'$ and $B'$ but for {k-1} families. Therefore it is true for $n=k-1$. We will repeat this process till we reach $n=1$ but it is obviously false for $n=1$, contradiction. Hence such $k>1$ doesn't exist. Q.E.D.
17.07.2023 23:30
FIOTN wrote: But he received 0 points with no reasonable explanation. This statement is disturbing, the coordination was supposed to go on, and apparently went on, until all the participants were given (at least some) explanations. So if the situation was indeed so bad, I advise you to provide more details so that I can take appropriate action. However, the argument in your post is not even clearly stated. The places occupied by the people in this problem are in fact numbered by residues modulo $3k$. When you make configuration $A'$ from $A$ the places in $A'$ are numbered by residues modulo $3(k-1)$, and, until you say what these numbers are, $A'$ is not defined. I spent some time during the olympiad trying to save this argument, unsuccesfully. Of course, I had not too much time, but this means at least that the task is not obvious.
18.07.2023 10:03
guas wrote: until all the participants were given (at least some) explanations. Sorry for any misunderstandings. I probably exaggerated little bit. I got more details after speaking with contestant. He said that there was only vague explanations and jury didn't give him exact answer on his mistake. Sorry for this again.