4
$\begingroup$

Question

I have a sequence of natural numbers $0 = k_0 < k_1 < k_2 < \dots < k_n$ and we want to find the set of numbers which satisfy some property, so we want to find (in function of $n$): $$ \mathcal{A}_n := \{ (k_1,\dots,k_n) \in \mathbb{N}^{n} \mid (k_0,\dots,k_n) \mbox{ satisfy property }A\} $$ The property $A$ we are looking at is the following:

let $\sigma$ be an arbitrary permutation on $\{k_0,\dots,k_n\}$ and $k \in \{k_0,\dots,k_n\}$ be arbitrary, we define: $$ V(\sigma,k) := \sum_{i=0}^{k_n-1} \delta_{\{\sigma^{k_n-i-1}(k) > i\}} $$ where we define $\delta_{\{a > b\}}$ to be zero if $a \leq b$ and one if $a > b$.

We say that $(k_0,\dots,k_n)$ satisfy property $A$ if: $$ \exists \sigma: \forall k,l \in \{k_0,\dots,k_n\}: V(\sigma,k) = V(\sigma,l), $$ i.e. there exists some permutation s.t. $V(\sigma,k)$ doesn't depend on the initial state $k$.

Simplified version

I would already be quite happy if it was possible to show that $\forall n: \mathcal{A}_n \neq \emptyset$.

Lower dimensional example

I have done the calculations for some values of $n$.

$n=1$

We have: $$ \mathcal{A}_n = 2\mathbb{N}, $$ indeed, for the trivial permutation this sum is dependant on $k$ as we have: $$ V(\mbox{id},k) = \begin{cases} k_1 & \mbox{ if } k = k_1\\ 0 & \mbox{ if } k = k_0. \end{cases} $$ and the only other permutation $\sigma$ we have is defined by sending $0$ to $k_1$ and $k_1$ to $0$, the sum then just counts the number of times $\sigma^{k_1-i-1}$, for $k_1$ odd this sum differs by one depending on we start at $k_1$ or not (as we start and end with the same value), whilst for even $k_1$ we start and end with the same value and thus the sum yields the same result in both cases (i.e. starting from $k_1$ or $0$).

$n=2$

In this case the solution is still quite elegant as we have: $$ \mathcal{A}_n = \{(k_1,k_2) \mid k_1,k_2 \mbox{ and } 0 \mbox{ are distinct modulo } 3.\} $$ which can be seen analogously to the 2 dimensional case (except for using other permutations).

$n=3$

Numerically I suspect that $\mathcal{A}_n$ can be characterized by the matrix: $$ M_3 \begin{pmatrix} 1 & 2 & 1\\ 1 & 3 & 0\\ 1 & 0 & 3\\ 1 & 1 & 2\\ 2 & 3 & 3\\ 2 & 0 & 2\\ 2 & 2 & 0\\ 3 & 0 & 1\\ 3 & 1 & 0\\ 3 & 2 & 3\\ 0 & 1 & 3\\ \end{pmatrix} $$ where $(k_1,k_2,k_3)$ is in $\mathcal{A}_n$ if the vector $(\mod(k_1,4),\mod(k_2,4),\mod(k_3,4))$ is a row in the matrix $M_3$. Numerically I can compute these matrices for pretty large $n$ but I would like to have some general expression for it, but I feel like I lack the algebraic insights to do this.

Origin Of The problem

I have a supply process with $n+1$ different lead times (with one equal to $0$) and I cycle through all the different lead times. I wonder if we have for any number of different lead times that we can cycle through these lead times in such a way that the inventory remains the same over time.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.