Constructing sequences

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Constructing sequences

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2018 Singapore Mathematical Olympiad Senior Q5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2663 posts

SMOJ

#1 h Mar 31, 2020, 7:09 AM • 1 Y

Y by akasht

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

84 posts

akasht

#3 h Jun 15, 2020, 7:02 AM

Y by

Hint

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

287 posts

JG666

#4 h Feb 20, 2022, 11:45 AM

Y by

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? :oops_sign:

:oops_sign:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

84 posts

akasht

#5 h Mar 20, 2022, 5:34 AM

Y by

Hmm I also forgot how I did it - maybe it was a fakesolve oops.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

84 posts

akasht

#6 h Mar 20, 2022, 5:34 AM

Y by

In fact I’m not even sure whether (2) is true or not

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Infinity_Integral

306 posts

Infinity_Integral

#7 h Jan 18, 2024, 2:38 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#9 h Apr 18, 2025, 2:49 PM

Y by

We claim that the only solution is for all odd $n$ , which clearly works.

Proof
Consider modulo 3, where we express $A, B, C$ as $0, 1, 2$ respectively. Let $\mathrm{R}_j = (x_1, x_2, \dots, x_n)$ , and $\mathrm{R}_{j+1} = (y_1, y_2, \dots, y_n)$ . Then for $1 \leq i \leq n$ , it is always true that $y_i \equiv -(x_i + x_{i+1}) \pmod 3$

If $n$ is even, take $\mathrm{R}_0 = (1, 2, 1, 2, \dots, 1, 2)$ . Then for any $m \geq 1$ , it is always true that $\mathrm{R}_m = (0, 0, \dots, 0, 0)$ . Clearly, there cannot exist any positive integer to satisfy the requirements. If $n$ is odd, since there are at most $3^n$ distinct $n$ -element number arrays in the form of $(x_1, x_2, \dots, x_n)$ , then for any $\mathrm{R}_0$ , there exists $m_{\mathrm{R}_0} \in \mathbb{N}$ , and $k \in \mathbb{N}$ such that $\mathrm{R}_k = \mathrm{R}_{m_{\mathrm{R}_0} + k-1}$ . We then aim to show that if $k \geq 1$ , then $\mathrm{R}_{k-1} = \mathrm{R}_{m_{R_0} + k-1}$ (likewise we get $\mathrm{R}_0 = \mathrm{R}_{m_{\mathrm{R}_0}}$ )

Now suppose that $\mathrm{R}_{k-1} = (x_1, x_2, \dots, x_n)$ , $\mathrm{R}_{m_{\mathrm{R}_0} + k-1} = (y_1, \dots, y_n)$ , then from equality we get $-(x_i + x_{i+1}) \equiv -(y_i + y_{i+1}) \pmod 3$ . So $\sum_{j=1}^n (-1)^j(x_j + x_{j+1}) \equiv \sum_{j=1}^n (-1)^j(y_j + y_{j+1}) \pmod 3$

Concerning also $n$ is odd, we know that $-x_1 + (-1)^nx_{n+1} \equiv -y_1 + (-1)^ny_{n=1} \pmod 3$ , i.e. $-2x_1 \equiv -2y_1 \pmod 3$ , $x_1 \equiv y_1 \pmod 3$ , so $x_1 = y_1$ . By the same reasoning, we can prove that for $i \in \{2, \dots, n\}$ , it is always true that $x_i = y_i$ , so $\mathrm{R}_{k-1} = \mathrm{R}_{m_{\mathrm{R}_0} + k-1}$

By above we know that there exists an $m_{\mathrm{R}_0}$ such that $\mathrm{R}_0 = \mathrm{R}_{m_{\mathrm{R}_0}}$ . Then, while $\mathrm{R}_0$ changes, we take the LCM $m$ of all $m_{\mathrm{R_0}}$ . Then for any $\mathrm{R}_0$ , it is always true that $\mathrm{R}_0 = \mathrm{R}_m$ $\quad \blacksquare$

This post has been edited 2 times. Last edited by lightsynth123, Apr 19, 2025, 9:26 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a