determine whether there exists $(x_1,\cdots, x_n)$ so that $x_{i+1} \in \{2x_i, 2x_i - 1, 2x_i - n, 2x_i - n-1\}\,\forall i$ 
Let $n$ be an even positive integer. Determine whether there exists a permutation $(x_1,\cdots, x_n)$ of $\{1,\cdots, n\}$ so that $x_{i+1} \in \{2x_i, 2x_i - 1, 2x_i - n, 2x_i - n-1\}\,\forall i$ (here $x_{n+1} = x_1$).

It may be useful to find an Eulerian circuit in a directed multigraph, which is guaranteed provided the indegree of each vertex equals its outdegree. But I'm not sure how to find this multigraph. Write $n = 2m$. We label the edges of the graph as $1,\cdots, 2m$ and the vertices as $1,\cdots, m$. We want to ensure each edge appears in the Eulerian circuit exactly once. I think one should be able to let $x_i$ be the label of the $i$th edge in the Eulerian circuit once the graph is defined properly.
It seems in the answer below that there are two outgoing arcs from each vertex, because there's always two values that are "in range." For instance, if $1\leq v\leq m/2$, then $2v-m < 1$, so only $2v$ and $2v-1$ are between $1$ and $n=2m$. If $v>m/2 + 1,$ then $2v-m$ and $2v-m-1$ are in range. If $v=(m+1)/2, 2v - 1 = m$ and $2v-m$ are in range.

Edit: I have several questions about the answer posted below:


*

*If the indegree equals the outdegree for each vertex and the graph is connected, doesn't the graph have an Eulerian cycle? Also, how would one prove this (e.g. by induction on the number of edges perhaps).

*Why are the incoming arcs to vertex $v$ precisely $(\lfloor (v+1)/2 \rfloor , v), (\lfloor (v+m+1)/2\rfloor, v)$? From my understanding, for an incoming arc $(w,v)$, we need $2w =v, 2w - 1 = v, 2w - m = v$ or $2v - m-1=v$. If $v$ is odd, then we must have $2w-1=v$ or one of $2v-m-1=v, 2v - m = v$, depending on whether $m$ is odd or not.

*Doesn't one require the digraph to be (weakly) connected for all m? And to prove this, perhaps one could show all vertices are reachable from vertex $(1,1+m)$?

*To restore a permutation from the Eulerian cycle, when exactly do we take the number $v$ and when do we take the number $v+m$? A small example might help (e.g. $m=3, n=6$).


Also, just for additional info, I've added a proof of the weak connectivity of the graph (which I'm pretty sure should work regardless of the parity of m). We'll prove the weak connectivity by induction on the vertex number. Let the vertices be $v_1,\cdots, v_m$, where $v_i$ represents the pair $(i,i+m)$. We'll prove that $v_1$ can reach all vertices. For clarity, we let vertex $v_i$ be connected to vertex $v_{2i-1}, v_{2i}, v_{2i-m-1}, v_{2i-m},$ depending on which indices are in range. $v_1$ is connected to $v_1$ by definition. Assume the result holds for all smaller indices. We want to show it holds for $v_j$ where $1<j\leq m$. Note that $v_j$ has in-neighbours $v_{\lfloor (j+1)/2\rfloor}$ and $v_{\lfloor (j+m+1)/2\rfloor}$. $v_{\lfloor (j+1)/2\rfloor}$ is connected (by a directed path) to $v_1$ by the inductive hypothesis as $\lfloor (j+1)/2\rfloor \leq (j+1)/2 < j$, and so $v_j$ is also reachable from $v_1$, as required.

 A: I see the other graph (pseudograph) for the case of $n = 2m$. Note that given $x_i$ you have exactly two options for each $x_{i + 1}$. Also for each $1 \le v \le m$ for $x_i = v$ and $x_i = v + m$ we have that $x_{i + 1} \in \{\,2v, 2v - 1\,\}$, because if $2v - n < 1$ and $2v + 2m - 1 > 2m = n$.
Now let vertices $1, 2, \ldots, m$ correspond to pairs of number $(1, 1 + m), (2, 2 + m), \ldots, (m, 2m)$. Let graph have all available arcs from $\{\,(v, 2v), (v, 2v - 1), (v, 2v - m), (v, 2v - m - 1) \forall v \mid 1 \le v \le m\,\}$. Case $m = 1$ is trivial, so let $m > 1$. For a similar reason as above there are exactly two outgoing arcs from each vertex. Also for each vertex $v$ there are two incoming arcs $(\left\lfloor\frac{v + 1}{2}\right\rfloor, v)$ and $(\left\lfloor\frac{v + m + 1}{2}\right\rfloor, v)$. Therefore the indegree equals to the outdegree for each vertex. So an Eulerian cycle exists if and only if the digraph is weak. It is easy to show that the graph is weak if and only if $m$ is odd (i. e. $n$ is not divisible by $4$) or $m = 2$.
Restoring a permutation from the Eulerian cycle is pretty easy. Each vertex $v$ appears twice in the cycle. For the first appearance take number $v$, for the second appearance take $v + m$ or vice versa.
The case $n = 2m + 1$ is much more easy.
More details

*

*Digraph can't be just connected. It can be weakly connected or strongly connected. When we talk about Eulerian cycle, then weak connectivity is enough (and it implies strong connectivity if each indegree equals to corresponding outdegree). Existence of an Eulerian cycle can be proved by cyclic decomposition. If each indegree equals to the outdegree then we can match each incoming arc to an outgoing arc for each vertex. After that starting from any vertex $s$ we can build a cycle, because when we come to a vertex other than $s$ it has corresponding outgoing arc that is not used. When we come to the vertex $s$ we finish a cycle. Let's delete arcs of this cycle. If there is at least one more arc we can build one more cycle, because for each vertex we deleted the same number of incoming and outgoing arcs. At the end we have set of cycles. If two cycles share a vertex we can unite these cycles into a bigger one (and remove two smaller ones). If in our cycle decomposition there are at least two cycles then there is at least one pair of cycles that share at least one vertex since the graph is weakly connected. Therefore we can unite pairs cycles until the only will remain. It will be an Eulerian cycle. (It is a well known proof, even if I didn't explain it well.)


*If $v$ is odd then there is an arc $(\frac{v + 1}{2}, v)$. If $v$ is even then there is an arc $(\frac{v}{2}, v) = (\frac{v + 1}{2} - \frac{1}{2}, v)$. To unite these cases I use floor function: in any case there is an arc $(\left\lfloor\frac{v + 1}{2}\right\rfloor, v)$. The same with $(\left\lfloor\frac{v + m + 1}{2}\right\rfloor, v)$.


*Weakly connected digraph and weak digraph are the same terms. It means that replacing each arc (directed edge) by an edge we get a connected non-directed grpah. Yes, you may show it's connectivity as reachability of each vertex from a selected one.


*For $n = 6$ we have $3$ vertices $1, 2, 3$ corresponding to pairs of numbers $\{\,1, 4\,\}, \{\,2, 5\,\}, \{\,3, 6\,\}$. Let Eulerian cycle be $1, 2, 3, 3, 2, 1, 1$. (There may be serveral Eulerican cycles and we can consider any of them.) It can be transfromed to a sequence $1, 2, 3, 6, 5, 4, 1$. There was no ambiguity which number we should select, except for the first one, because both $v$ and $v + m$ would produce the same numbers $2v$ and $2v - 1$, but selection between two these numbers is done by choosing Eulerian cycle. The first number is the last one too, so it can be also determined well.
For $n = 10$ there are $3$ Eulerian cycles:
$$1, 1, 2, 3, 5, 5, 4, 2, 4, 3, 1;\\
1, 1, 2, 4, 2, 3, 5, 5, 4, 3, 1;\\
1, 1, 2, 4, 3, 5, 5, 4, 2, 3, 1.$$
Corresponding sequences are:
$$6, 1, 2, 3, 5, 10, 9, 7, 4, 8, 6;\\
6, 1, 2, 4, 7, 3, 5, 10, 9, 8, 6;\\
6, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6.$$
