Circuite hamiltoniene in hipercubul din R^n

[Filip Chindea]

Etichetam cele \( 2^N \) varfuri ale hipercubului \( \{0, 1\}^N \) prin

\( v(\mathbf{x}) := \sum_{k=1}^N x_k2^{k-1} \),

pentru \( \mathbf{x} = (x_1, ..., x_n) \). Determinati intregii pozitivi \( n \), \( 2 \le n \le 2^N \), astfel incat setul varfurilor etichetate cu numerele \( 0, ..., n - 1 \) induce in hipercubul unitate un subgraf ce poseda un circuit hamiltonian \( \line(1,0){25} \) astfel, muchiile admisibile apar intre doua varfuri ce difera in exact o coordonata.

[ Stelele Matematicii 2008 - Problema 2 ]