2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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 $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.