Problemi aperti sui puntini (in 2 e 4 dimensioni)

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
marcokrt
Livello 3
Livello 3
Messaggi: 64
Iscritto il: dom lug 21, 2013 1:18 am

Problemi aperti sui puntini (in 2 e 4 dimensioni)

Messaggio da marcokrt »

Presento un paio di interessanti problemi aperti riguardanti i "soliti" puntini da unire con segmenti rettilinei collegati tra loro (insomma, con "$h$" tratti che formano un'unica spezzata).

Problema 1 ($2$ dimensioni): E' possibile unire tutti i punti di una griglia $n$ x $m$ (con $1 < n < m$) con segmenti rettilinei usando meno di $2n-1$ tratti?

Problema 2 ($4$ dimensioni): E' possibile unire tutti i punti di una griglia $n$ x $m$ x $k$ x $q$ (con $n=m=k=q=3$) con meno di $44$ segmenti rettilinei?
Nota: Il limite inferiore che sono stato in grado di provare è $41$ mentre, se $n=m=k=q=2$, la soluzione (problema banale) è $15$ segmenti.

marcokrt
Livello 3
Livello 3
Messaggi: 64
Iscritto il: dom lug 21, 2013 1:18 am

Re: Problemi aperti sui puntini (in 2 e 4 dimensioni)

Messaggio da marcokrt »

Ho provato a ragionare un po' sul problema in 4 dimensioni, adottando due approcci indipendenti.

Posto che ho 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!! 8)

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?


Per il problema delle griglie rettangolari 2D, lascio la palla a chi vorrà provare a raccoglierla :mrgreen:

marcokrt
Livello 3
Livello 3
Messaggi: 64
Iscritto il: dom lug 21, 2013 1:18 am

Re: Problemi aperti sui puntini (in 2 e 4 dimensioni)

Messaggio da marcokrt »

Qui potete trovare la mia soluzione al problema in 4 dimensioni (3x3x3x3 punti-->43 linee):

http://www.scribd.com/doc/163773094/Bes ... ts-problem


Volendo, è possibile risolvere il problema con 43 linee partendo da un qualsiasi punto dell'iper-box quadridimensionale (invertendo la dine con l'inizio e componendo opportunamente i vari pattern 2D e le linee di collegamento) :)

Rispondi