Cycles modulo $2^n$
Suppose for any $n$, WLOG, you have a directed graph $G$ with $2^n$ nodes (label them $0$ through $2^{n-1}$). Suppose $(i, j) \in G$ iff $2i+1 \equiv j \pmod{2^n}$ or $2i \equiv j \pmod{2^n}$.
Prove that $G$ has a Hamiltonian cycle.
As bonus, count how many such cycles there are. Show that all Hamiltonian paths are necessarily cycles, too. Generalize to $k^n$, where $(i, j) \in G$ iff $ki+p \equiv j \pmod{k^n}$ for any $0 \leq p < k$.