Sequence arrangement and operation (combinatorics)

144 Views Asked by At

Consider a sequence $\langle x_1,x_2,x_3, \cdots, x_n\rangle $ such that $x_i> 0~ \forall 1\leq i\leq n$ and $x_i\geq x_j$ if $i\geq j$. An operation on the sequence will make it $\langle n, x_1-1, \cdots , x_n-1\rangle $ (not arranged) such that they are arranged in non-increasing order and if any element results into $0$ it will be removed. For the $n^\text{th}$ sequence, the $n+1^\text{th}$ sequence will have one element which is the count of the number of elements in the $n^\text{th}$ sequence followed by the reduction of each term by $1$. If any of the terms result into a $0$, we will remove it. For example, $\langle 4211\rangle \to \langle 431\rangle \to \langle 332\rangle \to \langle 3221\rangle \to \langle 4211\rangle \to \langle 431\rangle \to \cdots$. (Once there's a repetition, it's clear that the the cycle will continue)

  1. Find all possible sequences that will yield a $1-$cycle after sometime. For example, $\langle 532\rangle \to \langle 4321\rangle \to \langle 4321\rangle \to \cdots$ is a 1-cycle. I'm not exactly sure how to find all possible 1-cycles. But it's apparent and can be proven easily that a sequence of the form $\langle x,x-1, \cdots, 1\rangle $ is the only possible cycle. But I cant find all possible sequences that will result into this.

  2. Will every sequence enter a cycle at some point of time? If so, why and when? If not, for which cases? I just have an intuition that every sequence will, but I couldn't think of a proper solution

1

There are 1 best solutions below

0
On

I am not sure how to do 1, but I can help you prove that each sequence enters a cycle.

Say that a sequence $\langle x_1,\cdots,x_n\rangle $ is bounded by a sequence $\langle y_1,\cdots,y_k\rangle $ if $\exists k_1,\cdots, k_n$ strictly increasing such that $x_1 \leq y_{k_1} \cdots x_n \leq y_{k_n}$. Clearly, $\langle y_1,\cdots,y_k\rangle $ must be longer than $\langle x_1,\cdots,x_n\rangle $ for this definition to work. Also, notice that when applying the operation on the sequences, we will get that $\langle n,x_1-1,\cdots,x_n-1\rangle $ is bounded by $\langle k,y_1-1,\cdots,y_k-1\rangle $ (using that $k\geq n$). So, if $\langle y_1,\cdots,y_k\rangle $ enters a cycle, then there is an upper bound for the length of the sequences that follow it, so there is an upper bound on the length of the sequences that follow $\langle x_1,\cdots,x_n\rangle $. It would follow that $\langle x_1,\cdots,x_n\rangle $ would enter a cycle. Clearly, any sequence is bounded by some one-cycle $\langle k,\cdots,1\rangle $