Punti in 4 dimensioni
Consideriamo un ipercubo (la regione contenuta in esso) definito da $3^4=81$ punti. Tali punti sono disposti regolarmente e la distanza tra quelli adiacenti è unitaria (secondo tutte e $4$ le direzioni caratteristiche). I punti (distinti e adimensionali) sono disposti su file di tre punti. Il nostro scopo è connetterli tutti con una spezzata formata dal minor numero di segmenti possibile (segmenti privi di spessore). Lo spazio esterno a quello definito dai punti in questione è utilizzabile (diciamo che, per i nostri scopi, possa considerarsi pressoché illimitato - facciamo finta che abbia iper-volume pari a $100^4 unità^4$), quindi le linee possono "uscire" dal box immaginario in oggetto!
Domanda: E' possibile unire tutti i punti usando meno di 44 segmenti rettilinei?
Immaginiamo di trovarci in uno spazio quadridimensionale. Non mi interessano soluzioni "fantasiose", regiorni curvilinee e via dicendo. Mi interessa unicamente trovare il minimo del problema in questione.
Nota: Ho dimostrato che non è possibile far ciò usando meno di $41$ linee, ma dubito che tale valore sia minimale
Buon divertimento.
Domanda: E' possibile unire tutti i punti usando meno di 44 segmenti rettilinei?
Immaginiamo di trovarci in uno spazio quadridimensionale. Non mi interessano soluzioni "fantasiose", regiorni curvilinee e via dicendo. Mi interessa unicamente trovare il minimo del problema in questione.
Nota: Ho dimostrato che non è possibile far ciò usando meno di $41$ linee, ma dubito che tale valore sia minimale
Buon divertimento.
Risposte
Nessuna idea?
Reminder: per unire $9$ punti disposti in una griglia regolare $3$x$3$ (con i punti adiacenti equidistanti tra loro) sono necessari almeno $4$ segmenti di retta consecutivi (a formare un'unica spezzata/polilinea con $5$ vertici). Il caso "cubico" $3D$ con $3$x$3$x$3=27$ punti può essere scisso in $3$ griglie $3$x$3$ e sono comunque necessari $14$ "tratti" per collegare tutti i punti...
Reminder: per unire $9$ punti disposti in una griglia regolare $3$x$3$ (con i punti adiacenti equidistanti tra loro) sono necessari almeno $4$ segmenti di retta consecutivi (a formare un'unica spezzata/polilinea con $5$ vertici). Il caso "cubico" $3D$ con $3$x$3$x$3=27$ punti può essere scisso in $3$ griglie $3$x$3$ e sono comunque necessari $14$ "tratti" per collegare tutti i punti...
Ho provato a ragionare un po' sul problema in questione, adottando due approcci indipendenti.
Posto che ho già dimostrato formalmente (il realtivo paper in inglese è quasi pronto) che serve un numero di linee compreso tra $41$ e $44$, ho provato a ridurre il novero delle possibilità.
1° approccio - pratico/geometrico) L'ipercubo $3x3x3x3$ può essere scomposto in $3$ cubi con $3$ punti allineati secondo ciascuna direzione... poiché il minimo di linee necessarie per connettere i punti in un cubo $3x3x3$ è $14$ (ho dimostrato anche questo), posso supporre che, partendo da uno dei cubi esterni e attraversando quello centrale prima di approdare sul cubo antitetico, possa intersecare un punto del cubo centrale (la sua collocazione mi è nota, ma è lungo da spiegare...). Così facendo mi restano da connettere $26$ punti con meno di $14$ linee... però posso iniziare da un punto qualsiasi nello spazio del cubo rimanente (quello con $26$ puntini da connettere). Inizio dalla faccia opposta a quella del punto in questione, ma non cambia nulla.
L'unica possibilità è studiare il caso seguente: risolvo il cubo esterno in modo da terminare in posizione centrale bassa, "taglio" sul cubo antitetico passando per il medesimo punto del cubo centrale. Risolvo il secondo cubo esterno terminando in una delle griglie esterne (in un angolo) e quindi affronto il cubo centrale partendo da una faccia esterna. Con il quinto segmento (riferito al terzo cubo considerato) interseco il punto centrale della griglia centrale e dunque, con il decimo segmento mi porto in uno degli angoli... $3/4$ di giro di spirale e il gioco è fatto: $43$ segmenti consecutivi in tutto!!!
2° approccio - matematico/statistico) Per una griglia $3x3$, scartando il primo segmento, ci vogliono $3$ segmenti consecutivi per connettere 6 punti (i casi particolari non sono utili). Una media di $2$ punti a segmento (il massimo possibile). Per il caso $3x3x3$ ogni segmento successivo al primo può unire al massimo $24/13<6/3$ punti (i casi particolari non sono utili). Ed eccoci al caso 4D: anche ipotizzando che le cose non peggiorino rispetto alla situazione 3D, ci serviranno sempre $\lceil78/(24/13)\rceil=43$ linee. Ooops... è proprio il risultato scaturente dal 1° approccio... vuoi vedere che è proprio la soluzione finale?
Posto che ho già dimostrato formalmente (il realtivo paper in inglese è quasi pronto) che serve un numero di linee compreso tra $41$ e $44$, ho provato a ridurre il novero delle possibilità.
1° approccio - pratico/geometrico) L'ipercubo $3x3x3x3$ può essere scomposto in $3$ cubi con $3$ punti allineati secondo ciascuna direzione... poiché il minimo di linee necessarie per connettere i punti in un cubo $3x3x3$ è $14$ (ho dimostrato anche questo), posso supporre che, partendo da uno dei cubi esterni e attraversando quello centrale prima di approdare sul cubo antitetico, possa intersecare un punto del cubo centrale (la sua collocazione mi è nota, ma è lungo da spiegare...). Così facendo mi restano da connettere $26$ punti con meno di $14$ linee... però posso iniziare da un punto qualsiasi nello spazio del cubo rimanente (quello con $26$ puntini da connettere). Inizio dalla faccia opposta a quella del punto in questione, ma non cambia nulla.
L'unica possibilità è studiare il caso seguente: risolvo il cubo esterno in modo da terminare in posizione centrale bassa, "taglio" sul cubo antitetico passando per il medesimo punto del cubo centrale. Risolvo il secondo cubo esterno terminando in una delle griglie esterne (in un angolo) e quindi affronto il cubo centrale partendo da una faccia esterna. Con il quinto segmento (riferito al terzo cubo considerato) interseco il punto centrale della griglia centrale e dunque, con il decimo segmento mi porto in uno degli angoli... $3/4$ di giro di spirale e il gioco è fatto: $43$ segmenti consecutivi in tutto!!!
2° approccio - matematico/statistico) Per una griglia $3x3$, scartando il primo segmento, ci vogliono $3$ segmenti consecutivi per connettere 6 punti (i casi particolari non sono utili). Una media di $2$ punti a segmento (il massimo possibile). Per il caso $3x3x3$ ogni segmento successivo al primo può unire al massimo $24/13<6/3$ punti (i casi particolari non sono utili). Ed eccoci al caso 4D: anche ipotizzando che le cose non peggiorino rispetto alla situazione 3D, ci serviranno sempre $\lceil78/(24/13)\rceil=43$ linee. Ooops... è proprio il risultato scaturente dal 1° approccio... vuoi vedere che è proprio la soluzione finale?
Qui potete trovare la mia soluzione al problema in 4 dimensioni (3x3x3x3 punti-->43 linee):
http://www.scribd.com/doc/163773094/Bes ... ts-problem
http://www.scribd.com/doc/163773094/Bes ... ts-problem
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo