Circuite hamiltoniene in hipercubul din R^n
Posted: Sat Dec 06, 2008 10:35 pm
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 ]
\( 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 ]