Question

Given integers $v_0,\dots,v_{n-1} \in \mathbb{N}$, I want to find an integer $t>0$, a map $f:\mathbb{N} \times \{0,1,\dots,n-1\} \to \mathbb{N}^t$, and a well-founded order $>_t$ on $\mathbb{N}^t$ such that

$$f(m,i) >_t f(m+v_i,i+_n 1)$$

holds for all $i,m$, where $+_n$ is the addition modulo $n$. I am promised that $v_0+\dots+v_{n-1}<0$. Is there an efficient algorithm to do that?

Explanation and motivation

Let's assume a chain $0 \stackrel{v_0}\to 1 \stackrel{v_2}\to \ldots \stackrel{v_{n-2}}\to n-1 \stackrel{v_{n-1}}\to 0$.

The directed weighted graph above describes how a magnitude $m \in \mathbb{N}$ varies. That is, for transition $i \stackrel{v}{\to} j$, $m$ gets updated with $m+v$. It must hold that $\sum_{i = 1}^n v_i < 0$. Consider the following problem:

Give an assignment of values in $\mathbb{N}^t$ to nodes and an order that decreases at each transition.

That is, if $\text{nodes} = \{0,\ldots,n-1\}$, then f I want to build a map $f:\mathbb{N} \times \text{nodes} \to \mathbb{N}^t$ with $t > 0$ satisfying that:

For each $i \in \text{nodes}$, we have $f(m,i) >_t f(m+v_i, i +_n 1)$

where $>_t$ is a well-founded order on $\mathbb{N}^t$ and $+_n$ is the addition modulo $n$.

Is there an algorithm that can built such an $f$ and $<_t$?

Example (my try):

Assume you have the following chain is given:

$1 \stackrel{+3}{\to} 2 \stackrel{-2}{\to} 3 \stackrel{-2}{\to} 1$

In this case, $+3-2-2 = -1 < 0$.

Let's start at 1.

Since $m$ increases, I will annotate measure $(2,m)$ in $1$ and measure $(1,m)$ in $2$ so that lexicographic order decreases.

At $2$, measure $m$ decreases so I can leave annotation $(1,m)$ as it was.

At $3$, measure $m$ decreases so I can copy annotation $(1,m)$ from $2$.

Coming back to $1$, I have a problem, since I had annotated $(2,m)$ before, but now I have annotated $(1,m)$ and these are clearly different measures.

Can you help me out of this problem?

Note on the meaning of the specification

Just to make sure the specification matches my needs, the problem tries to model how some quatity $m$ varies in a loop of successive function applications. The functions form a loop that ends at $0$. It is guaranteed that when traversing the whole loop, quantity $m$ decreases (according to the variations $v_i$). In each function one have to check that in the next call certain measure $f$ (depending on the parameter $m$) decreases.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top