Problema "semplice": Si consideri il cubo unitario ${0,1}^3$ nel consueto spazio euclideo e si assuma che un "albero" sia una qualsiasi struttura rigida, connessa, formata da segmenti rettilinei tra loro collegati (in pratica, un albero ha la caratteristica che prendendone un qualsiasi ramo e muovendolo, il resto dovrà seguirlo... non possono esserci pezzi staccati, per intenderci).
Domanda "semplice": Si determini la minima lunghezza che possa avere un albero che colleghi tutti gli $8$ vertici del cubo (indizio, la soluzione che ho trovato non è né $7$ e nemmeno qualcosa che sta sopra $6+\frac{2}{3}$).
Generalizzazione "difficile": Si consideri la famiglia degli (iper)cubi $k$ dimensionali ${0,1}^k \subset \mathbb{R}^k$ (con $k=2, 3, 4, \ldots$), sempre assumendo metrica euclidea come sopra... ma questa volta si determini la minima lunghezza (euclidea) per ciascun albero $k$-dimensionale ottimale che unisca tutti i $2^k$ vertici del relativo ipercubo (esempio, se $k=2$, possiamo facilmente concludere che la lunghezza minima è $2 \cdot \sqrt{2}$ che si ottiene unendo i vertici opposti del quadrato unitario... questa tecnica però è poco utile all'aumentare delle dimensioni, perché già per $k=4$ peggioreremmo una qualsiasi soluzione banalmente ottenibile tramite "spanning path" di $2^k-1$ segmenti unitari).
Buon divertimento!
Marco
