Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

This discussion might give some insight. Let's work in $\mathbb Z_n$, for simplicity. In this setting, we have $x_{i+1}\in\{2x_i,2x_i-1\}$. A mere adaptation of the solution posted there by alekk: construct a graph with $k$ vertices labeled $0,2,\ldots,2(k-1)=n-2$. We draw a directed edge from $2a$ to $2b$ iff $2b\equiv 2(2a-1)\pmod n$ or $2b\equiv 4a\pmod n$ (we allow loops, i.e. edges like $0\to 0$). The edge represents the residue $2a-1$ or $2a$, according to the situation. Each residue $\pmod n$ is represented by exactly one edge, so the problem is reduced to proving that the graph we have described is Eulerian, which is clear because each vertex has $2$ outgoing edges and $2$ incoming edges.

i certainly believe that this is true but how would you prove it: It is always possible to find a directed Hamiltonian circuit in a graph s.t. every edge has 2 outgoing and 2 incoming edges? and grobber, i believe that the thing where you allow loops as edges to be very dodgy. I tried this problem and had a very similar idea, but i didn't think the argument with the loops had much credibility. Suppose we have some directed graph with each vertice having 1 outgoing and 1 incoming edge and loops not allowed; now suppose for each vertice we add in a loop. now each vertex in the graph has 2 outgoing and 2 incoming edges and so a directed Hamiltonian circuit exists whenever each vertex has 1 outgoing vertex and 1 incoming vertex .. which i really doubt is true. Another idea which i believe works when $n$ is not a power of $2$ (btw i don't know why it doesn't work there, it just doesn't work for cases like $n=8$ and $n=16$ and all other cases i've tried): consider an involution $f(i) = n+1-i$. it's easy to see $i$ is connected to $j$ iff $f(i)$ is connected to $f(j)$ for all $n$. Indeed, in any such graph for $n$ not being a power of $2$, i believe that $i$ and $f(i)$ are seperated by exactly $\frac{n}{2} - 1$ vertices in the cycle. suppose it is possible to have one half of the cycle satisfying that property .. then the other proposed half has to work using the fact i cited above: $i$ is connected to $j$ iff $f(i)$ is connected to $f(j)$, so it thus suffices to construct the first half. Another interesting property of this graph is the following: for $k \leq \frac{n}{2}$, $k$ and $k+\frac{n}{2}$ are both connected to the two points $2k-1$ and $2k$. Possibly there might be a way of re-arranging the points so the existence of a Hamiltonian circuit is easy to see. .. but i can't seem to think of one. What's the official solution to this incredibly nice problem?

But it needs to be conected, or am I wrong?

i don't think there necessarily exists a Hamiltonian cycle for a digraph whose vertices have 2 in and 2 out edges. it is true that there must exist a directed cycle but not necessarily a cycle spanning all the vertices. does anyone have a solution to this problem using graph theory?

We may prove: $s_n-2s_{n-1}=s_{n-6}-2s_{n-5}$

first time this problem appeared in the final round of LIV Polish MO (2002/2003). here's solution in Polish: http://archom.ptm.org.pl/?q=node/320 Obviously I don't fancy tranlating this into English

@alkjash: Please say explicitly that $m$ is defined as $n/2$, and please fix the sentence "a set of edges, one from each vertex, that goes through all the vertices exactly once" (this does not make much sense imho). Otherwise, a very nice and well-explained solution! @GoldenFrog1618: nice solution, too. I am pretty sure that DelicateFlower's posting refers to a different problem. Does anybody have an idea which one? Note that this problem generalizes the existence of binary de Bruijn sequences. (In fact, the latter is the particular case when $n=2^t$ and we consider binary strings of length $t$ as elements of $\mathbb Z/n\mathbb Z$. More precisely, we should identify every binary string $b$ of length $t$ with the remainder of $-\left(\text{the number with binary representation }b\right)$ modulo $2^t$.)

Does this work? $1,2$ $1,2,4,3$ $1,2,3,6,5,4$ $1,2,3,4,8,7,6,5$ etc. I think i miss something. edit: latex

You've written down four small examples but you haven't noticed that at least one of them fails.

I think the Eulerian cycle idea from a previous post can be saved, just not easily. Convert to mod $n$ and graphs as in previous posts. However, the graph we construct will have $n/2$ vertices instead. Each vertex $v_{2k}$ represents the pair of numbers $2k-1, 2k$ for $k = 1,2,\ldots,n/2$. As for the edges, take a vertex $v_{2k}$. Notice that from $2k-1$, we must go to the pair of numbers given by $v_{4k-2}$, and similarly $2k$ must go to the pair of numbers given by $v_{4k}$ (all indices mod $n$). So we draw two edges going out of $v_{2k}$: one to $v_{4k-2}$ and one to $v_{4k}$, and we label these two edges $2k-1$ and $2k$ respectively. Each time we use an edge, its label is the number we add to our permutation. The problem is equivalent to the existence of an Eulerian cycle on this graph. The degree conditions are fine (2 in, 2 out for each vertex), so it remains to verify that the graph is connected. This can be done by inducting on the statement that after $i$ moves from a number $j$, we can be on any of the numbers $2^i j, 2^i j - 1, 2^i j -2, \ldots, 2^i j - (2^i - 1)$, all taken mod $n$.

I have a different approach Construct a graph with $n/2$ vertices and there is an edge from $i$ to $j$ if we can go from $i$ or $(n/2)+i$ to $j$ or $(n/2)+j$ in our permutation. All otudegrees and indegrees are 2, so there's an eulerian cycle. If we follow the eulerian cycle, the permutation results!

Let $n=2m$. Let there be a directed graph, with $m$ vertices, namely $v_1, v_2, \cdots v_m$. If $i \le \frac{m}{2}$, let there be a edge from $v_i$ to $v_{2i-1}, v_{2i}$, then write down $2i-1, 2i$ on these two rays. We can see that the edges towards $v_i$ has $i, i+m$ written on them. The indegree and outdegree is $2$, and it suffices to show that there is a eulerian cycle. Theorem: A directed graph has an eulerian cycle if and only if (i) It is connected. (ii) Each vertex has the same in-degree as out-degree. The proof of this theorem is left as an exercise to the reader. Now it suffices to show that this directed graph is connected. Claim 1: $\forall i$, there exists a path from $v_1$ to $v_i$. Proof of Claim 1: Trivial by strong induction on $i$. $\blacksquare$ Claim 2: If $a_0 = i$, for each $n$, define $a_{n+1} = 2a_n$ or $2a_n -1$. If we choose well, $\exists t$ such that $a_t \equiv 1 \pmod {m}$ Proof of Claim 2: Define $a_{n+1} = 2a_n - s_n$. We have that $a_n = 2^ni- \sum_{k=0}^{n-1} 2^ks_{n-k-1}$. Let $t$ be the number of digits in the binary form of $m$. Then, divide $2^ti-1$ by $m$ and let the remainder be $r$. Write $r$ as $\overline{(r_{t-1}\cdots r_2r_1)}_2$. Let $s_k = r_{t-1-k}$. We are immediately done. $\blacksquare$. Claim 2 shows that $\forall i$, there exists a path from $v_i$ to $v_1$. Therefore, we have that this directed graph is connected. We are done. $\blacksquare$

Nice problem. I have found a solution that does not use graph theory at all. Can someone check it? Let $n=2m$, and work in $\mathbb{Z}/n\mathbb{Z}$. Clearly, we want $x_{i+1}=2x_i$ or $x_{i+1}=2x_i-1$. Let a sequence $a_1,a_2,\ldots,a_k$ of distinct numbers have property $*$ if $a_{i+1}=2a_i$ or $a_{i+1}=2a_i-1$ for all $1\leq i\leq k-1$ and let a sequence with property $*$ have property $**$ if additionally $a_1=2a_k$ or $a_1=2a_k-1$. Lemma 1: Let $a_1,a_2,\ldots,a_k$ have property $*$. If $2a_k$ and $2a_k-1$ both appear in the sequence, then the sequence also has property $**$. Proof: Suppose that $a_i=2a_k$ and $a_j=2a_k-1$, where $i,j>1$. Note that both $a_{i-1}$ and $a_{j-1}$ must be either $a_k$ or $a_k+m$. But this is a contradiction, as all terms of the sequence are distinct. This means that given a sequence $a_1,a_2,\ldots,a_j$ with property $*$, we can extend the sequence to $a_1,a_2,\ldots,a_k$ with $j\leq k$ with property $**$. Lemma 2: If such a sequence $a_1,a_2,\ldots,a_k$ has property $**$ and has the property that $i$ appears in the sequence implies that $i+m$ appears in the sequence, then all numbers appear in the sequence. Proof: Suppose that $a_p=i$ and $a_q=i+m$. Then, $\{a_{p+1},a_{q+1}\}=\{2i,2i-1\}$, where we take indices mod $k$ if necessary. This means that $i$ appearing in the sequence implies that $2i$ and $2i-1$ appear in the sequence. This in turn implies that $4i$, $4i-1$, $4i-2$, and $4i-3$ appear in the sequence and in general $2^a\cdot i, 2^a\cdot i-1, 2^a\cdot i-2, \ldots,2^a\cdot i-2^a+1$ appear in the sequence. Taking $a$ to be sufficiently large gives that all numbers appear in the sequence, as desired. Now, take an arbitrary sequence $a_1,a_2,\ldots,a_k$ with property $**$. If all numbers appear in the sequence, then we make this our permutation and are done. Suppose that not all numbers appear in this sequence. Then, by Lemma 2 there exists a term $a_i$ such that $a_i+m$ does not appear in the sequence. Since we can shift the sequence, WLOG $i=1$. Now, consider the sequence $a_1+m,a_2,\ldots,a_k,a_1$. This sequence still satisfies property $*$, so by Lemma 1 we can extend it to a sequence that satisfies property $**$. Furthermore, this process increases the number of numbers in the sequence. We can repeat this process until the sequence contains all numbers, and then we obtain our permutation $x_1,x_2,\ldots,x_n$ as desired.

Let $n=2k$. Let $G$ be a directed graph with vertices labeled $1,2,\ldots,k$. Let the edges of $G$ be from $i$ to $2i-1$ and $2i$ (taken modulo $k$) for all $i\leq k$, where the edge from $i$ to $2i-1$ is labeled $2i-1$ and the edge from $i$ to $2i$ is labeled $2i$ (the edges have labels $1,2,\ldots,n$). (Note that there are loops at vertices $1$ and $k$.) Also observe that $G$ is weakly connected. Since $d^+(v)=d^-(v)=2$ for all $v\in V$, there exists an eulerian circuit. The order of the edges of this eulerian circuit correspond to a good permutation of $(1,2,\ldots,n)$.

Let $m=n/2$. Do everything modulo $n$, so we want the term after $i$ to be $2i$ or $2i-1$. Color $1$ through $m$ with either red or blue arbitrarily, and then color $m+1$ through $2m$ such that $i$ and $i+m$ are always opposite colors. Then draw a directed graph $G$ on the vertices $\{1,\ldots,2m\}$ such that $i$ points to $2i$ if $i$ is colored red, and $2i-1$ otherwise. It is clear that every vertex has indegree exactly $1$, hence $G$ is the union of disjoint cycles. If there exists some $i$ such that $i$ and $i+m$ are in different cycles, then it is clear that swapping the colors of $i$ and $i+m$ and updating $G$ accordingly will join the two cycles. Therefore, repeat this operation until $i$ and $i+m$ are in the same cycle for all $i$. I claim that this cycle must contain all of the vertices. Indeed, by strong induction, I will prove that element $k$, where $1 \leq k \leq m$ are in the same cycle as $1$, with the base case of $k=1$ being trivial. Then, suppose $1, \ldots, k-1$ are all in the same cycle as $1$. The element preceding $k$ in its cycle is either $\lceil \tfrac{k}{2}\rceil$ or $\lceil \tfrac{k}{2}\rceil+m$. Since $\lceil \tfrac{k}{2}\rceil \leq k-1$, it follows that $\lceil \tfrac{k}{2}\rceil$ is in the same cycle as $1$, hence $\lceil \tfrac{k}{2}\rceil+m$ is too, hence $k$ must be as well, completing the induction. From this, it follows that all the elements are in the same cycle as $1$, as desired. Finally, given this cycle passing through all the vertices of $G$, we may clearly extract a valid permutation by listing the vertices of the cycle in order. $\blacksquare$ Remark: Committing to coloring $i$ and $i+m$ differently is an important part of the solution, which imparts a large amount of structure on the problem, but it is also not a leap of faith. In fact, it's exactly the opposite: this "constraint" is necessary in any permutation, else we get repeated terms.

KevinYang2.71 wrote: Let $n=2k$. Let $G$ be a directed graph with vertices labeled $1,2,\ldots,k$. Let the edges of $G$ be from $i$ to $2i-1$ and $2i$ (taken modulo $k$) for all $i\leq k$, where the edge from $i$ to $2i-1$ is labeled $2i-1$ and the edge from $i$ to $2i$ is labeled $2i$ (the edges have labels $1,2,\ldots,n$). (Note that there are loops at vertices $1$ and $k$.) Also observe that $G$ is weakly connected. Since $d^+(v)=d^-(v)=2$ for all $v\in V$, there exists an eulerian circuit. The order of the edges of this eulerian circuit correspond to a good permutation of $(1,2,\ldots,n)$. For completeness, can anyone please supply a proof that if $G$ is a weakly connected directed graph with equal in and out degrees, then it has an Euler Circuit?