Post by GiovanniE' famosissimo, si tratta di congiungere 9 punti
con una spezzata continua con il monior numero di tratti
possibile.
Grazie per avermi proposto questo stimolantissimo problema che sembra semplice ma non è.
Dunque, per quasi un'ora ho creduto che non ci fosse modo di passare per tutti e 9 punti (non più di una volta) con una spezzata che avesse meno di 5 segmenti, poi.... ho trovato la soluzione con soli 4 segmenti:
https://drive.google.com/file/d/1iuIL3CIn1OtQSSI6jx_nZatnx3BDp7JN/view
Beh, determinare il numero minimo di segmenti della spezzata al variare del numero dei punti e in reticoli con numero arbitrario di dimensioni deve essere una faccenda piuttosto complessa.
Di certo, in N dimensioni, il corrispondente di un reticolo quadrato di 9 punti nel piano, è un reticolo N-ipercubico di 3^N punti. Il numero minimo di segmenti crescerà di conseguenza. L'istinto mi dice che cresce più o meno proporzionalmente al numero di spigoli 1-dimensionali di un ipercubo N-dimensionale che è N*2^(N-1) [si può dimostrare per induzione, vedere sotto].
Proverò a dare un'occhiata ai risultati di Ripà, per ora non ti so rispondere.
Ciao.
--
Gino Di Ruberto, IK8QQM
(american callsign K8QQM),
ID DMR: 2228273
____________________________
Proviamo che un ipercubo N-dimensionale ha N*2^(N-1) spigoli 1-dimensionali.
In una dimensione,
N=1, il segmento è esso stesso l'unico spigolo 1-dimensionale di sè stesso, se possiamo dire così.
A N=2, come otteniamo un quadrato?
Basta prendere 2 segmenti e poi considerare anche i 2 segmenti ottenuti congiungendo ognuno dei 2 punti che delimita un segmento con il corrispondente dell'altro segmento, così otteniamo
2+2 = 4 lati, ossia 4 spigoli 1-dimensionali.
A N=3, come possiamo ottenere un cubo?
Basta prendere 2 quadrati, ognuno dei quali ha 4 spigoli 1-dimensionali, e considerare anche i 2^2=4 segmenti ottenuti congiungendo ognuno dei 2^2 vertici di un quadrato con il corrispondente dell'altro quadrato, ottenendo in totale
2*4 + 2^2 = 12 spigoli 1-dimensionali.
A N=4, come facciamo a ottenere un'ipercubo 4-dimensionale?
Basta prendere 2 cubi, ognuno dei quali ha 12 spigoli 1-dimensionali e considerare anche i 2^3 segmenti ottenuti congiungendo ognuno dei 2^3 vertici di un cubo con il corrispondente dell'altro cubo, ottenendo in totale
2*12 + 2^3 = 32 spigoli 1-dimensionali.
Con ragionamenti analoghi comprendiamo che,
se un ipercubo N-dimensionale ha S spigoli 1-dimensionali,
allora un ipercubo (N+1)-dimensionale ha
2*S + 2^N spigoli 1-dimensionali.
Se è vero che
un ipercubo N-dimensionale ha
S= N* 2^(N-1) spigoli 1-dimensionali ,
allora un ipercubo (N+1)-dimensionale deve avere
2*S + 2^N =
2* N*(2^N-1) + 2^N =
N*2^N + 2^N =
(N+1)*2^N spigoli 1-dimensionali
che è lo stesso risultato ottenuto dal precedente sostituendo N+1 a N, quindi abbiamo dimostrato la nostra formula per induzione.
Scommetto che esistono dimostrazioni molto più eleganti e sintetiche, ma a me è venuta questa. :-)