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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.