Starting with any $n$-tuple $R_0$, $n\ge 1$, of symbols from $A,B,C$, we define a sequence $R_0, R_1, R_2,\ldots,$ according to the following rule: If $R_j= (x_1,x_2,\ldots,x_n)$, then $R_{j+1}= (y_1,y_2,\ldots,y_n)$, where $y_i=x_i$ if $x_i=x_{i+1}$ (taking $x_{n+1}=x_1$) and $y_i$ is the symbol other than $x_i, x_{i+1}$ if $x_i\neq x_{i+1}$. Find all positive integers $n>1$ for which there exists some integer $m>0$ such that $R_m=R_0$.
Problem
Source: 2018 Singapore Mathematical Olympiad Senior Q5
Tags: combinatorics
akasht
15.06.2020 10:02
1) Prove all even $n$ fails by using a counter example
2) Prove that for all $n$- tuples $R$ where $n$ is odd, there is a unique $n$-tuple $Q$ such that under this operation, $Q$ transforms to $R$ (This is essentially stating that this operation is injective for odd $n$)
3) Conclude the proof using Pigeonhole Principle
JG666
20.02.2022 14:45
akasht wrote: 2) Prove that for all $n$- tuples $R$ where $n$ is odd, there is a unique $n$-tuple $Q$ such that under this operation, $Q$ transforms to $R$ (This is essentially stating that this operation is injective for odd $n$) Anyone may enlighten me how I can prove this?
akasht
20.03.2022 08:34
Hmm I also forgot how I did it - maybe it was a fakesolve oops.
akasht
20.03.2022 08:34
In fact I’m not even sure whether (2) is true or not
Infinity_Integral
18.01.2024 05:38
akasht wrote: In fact I’m not even sure whether (2) is true or not You can quite easily prove each possible term in the sequence has at most 1 possible previous term by the following. For a term in the sequence, suppose its previous term (unique) start with A. Then it is easy to prove that the previous term when written repeatedly is the pattern BCBCBCBC... with some letters B and C replaced with A. In that case for the 1st, n+1th, 2n+1th etc (n is odd) letters to coincide (so the previous term is actually possible since its first letter have a unique value) we need them to all be replaced with A (so the first letter of the previous term is A). After determining the first letter of the previous term, it is easy to see that the remaining letters are uniquely determined, thus only 1 unique previous term can exist, which verifys the sub conclusion. This version also solve the qn when used with your (1) and (3), and your (2) follows from this combined with (3).