AoPS - Problem

Source: 2018 Singapore Mathematical Olympiad Senior Q5

Tags: combinatorics

SMOJ

31.03.2020 10:09

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$ .

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).