Problema aperto con i puntini da unire e mia soluzione personale

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 12:18 am

Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » dom lug 21, 2013 12:35 am

Salve,
Sono nuovo del forum... sono un semplice appassionato di matematica ricreativa e problemi aperti.

Di recente mi sono appassionato al problema dei nove punti (quello in cui bisogna unire i punti di una griglia $3x3$ con $4$ segmenti rettilinei consecutivi. Ho esteso il problema a una griglia k-dimensionale del tipo $n_1 X n_2 X ... X n_k$ (con $n_1 <= n_2 <= ... <= n_k$) e ho definito un metodo generale che ritengo molto difficile da migliorare (tranne che per casi molto specifici).

Ho scritto tutto nel seguente articolo (in italiano) che, se per caso interessasse a qualcuno, sarei lieto di mettere a disposizione del sito (mi piacerebbe comunque che ne potesse scaturire una discussione costruttiva sulla soluzione che propongo):

Parte 1: http://www.scribd.com/doc/154199480/Nin ... 6Xn-Points

Parte 2: http://vixra.org/pdf/1307.0095v1.pdf

Chiedo venia per i link, ma sarebbe stato davvero troppo complicato per me riscrivere quelle formule qui.

In sostanza, mi vado a costruire un limite superiore e uno inferiore prima per il caso $nxnxn$, poi per quello $nxnx...xn$ e infine passo al caso più generico in cui ogni dimensione è caratterizzata da un numero indipendente di punti distinti. :)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 961
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da Gianfranco » mar lug 23, 2013 9:10 am

Ciao Marco Ripà e benvenuto nel forum!

W O W ! ! !

Bellissima l'idea di generalizzare questo classico problema non solo a n x n ma addirittura a n x n x n x n x ... punti.
Ho molto apprezzato il tuo articolo ma confesso che, almeno per ora, non sono in grado di seguirti oltre la 2°, massimo 3°, dimensione.
Comunque, se mi confermi un link stabile con il tuo articolo sarò lietissimo di segnalarlo nel sito.

P.S. "viXra" scritto alla rovescia è "arXiv". Puoi dirci qualcosina di più?
Pace e bene a tutti.
Gianfranco

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » mar lug 23, 2013 3:53 pm

Salve Gianfranco,
Grazie 1000 per la risposta.
Credo che la soluzione più pratica sia inviarvi tutto per email in versione PDF o docx. L'ultimissima versione del primo articolo è in realtà su Scribd (ma cambiano giusto un paio di pedici nell'appendice e ho corretto un refuso), fatemi sapere e vedrò di cristallizzare il risultato in uno/due link definitivi.

Riguardo a viXra, si tratta di una versione free/open access di arXiv... gli articoli non sottostanno a un processo di revisione mirato (solo un controllo di tipo morale/legale), quindi vi si possono trovare anche delle sciocchezze enormi.

I risultati del paper che ho scritto sono sicuri (in passato ho anche pubblicato su riviste peer-review di matematica e psicologia cognitiva), ho fatto tutti i test del caso, ecc...

Il succo di ciò che è emerso è che, in generale, la configurazione migliore per risolvere problemi complessi di quel tipo si basa sull'implementazione del metodo della spirale quadrata (estesa nel modo che descrivo in appendice per il caso in cui n_1<n_k), però, per casi particolari (come già si sapeva), possono esistere soluzioni leggermente migliori (in particolare se n e k sono molto piccoli).

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » gio lug 25, 2013 1:03 am

Salve di nuovo,

Se per voi va bene, i link che userei per richiamare la soluzione completa che propongo per il problema dei puntini sono i seguenti:

PARTE 1: http://italian.iqsociety.org/wp-content ... -punti.pdf

Parte 2: http://italian.iqsociety.org/wp-content ... -viXra.pdf


Altrimenti, qualora non andassero bene, non ci sono impedimenti ad usare i link di viXra (l'unica imprecisione riguarda tre pedici a pagina $15$, ovvero $n_{k-2}$, $n_{k-1}$ ed $n_k$ anziché $n_1$, $n_2$ ed $n_3$ - penso comunque che non faccia una gran differenza :D ):

PARTE 1: http://vixra.org/pdf/1307.0021v2.pdf

PARTE 2: http://vixra.org/pdf/1307.0095v1.pdf

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 961
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da Gianfranco » gio lug 25, 2013 8:11 am

Grazie Marco,
userò i primi due che hai scritto li inserirò in una breve comunicazione nella home di BASE Cinque.
Tale comunicazione avrà un tono "ricreativo" e un livello "facile" decisamente inferiore a quello dei tuoi articoli. Questo è lo spirito di BASE Cinque.
I visitatori più preparati e interessati visiteranno il link e potranno approfondire l'argomento leggendo i tuoi articoli.
Pace e bene a tutti.
Gianfranco

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » gio lug 25, 2013 5:02 pm

Ti ringrazio moltissimo. Direi che è perfetto :)

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » gio lug 25, 2013 11:24 pm

Appena visto l'articolo con i link... perfetto! :)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 961
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da Gianfranco » ven lug 26, 2013 2:11 pm

Ciao Marco,
ho una domanda da farti.
Praticamente esistono due formulazioni del problema.
Prendiamo per esempio la griglia 4x4.
9punti.png
9punti.png (6.61 KiB) Visto 1048 volte
Se ammettiamo (come nella tua formulazione) che la linea spezzata possa incrociarsi una volta in corrispondenza di uno dei punti della griglia allora il minimo numero di segmenti necessari è 6.
(Esempio B, una delle tue soluzioni)

Se invece stabiliamo che la linea spezzata debba attraversare una sola volta ciascun punto della griglia, allora il minimo numero di segmenti necessari è 7.
(Esempio A)

Vero o falso che il minimo è 7?
Pace e bene a tutti.
Gianfranco

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » ven lug 26, 2013 3:01 pm

Ciao Gianfranco,
Rispodo molto volentieri... però sono costretto fare una noiosa premessa.

L'articolo scaturisce da idee mie, poi chiesi a questo amico se gli andasse di darmi una mano a tradurre tutto in inglese, sistemare meglio le figure, ecc. Così lui tradusse alcuni miei appunti e modificò l'ordine di altri appunti in inglese che avevo "uppato" su Scribd.

Cercando di definire meglio il problema, aggiunse la storia dell'intersezione tra linee (che nel problema originario non credo sia presente), ma lui intendeva che il vincolo fosse limitato all'esempio n=3. Ora dovrei rileggere il paper (magari lo farò questa notte), però le formule che ho trovato/dedotto non si curano delle interesezioni... il vincolo viene "riesumato" solo quando propongo le soluzioni della spirale quadrata/rettangolare pura (in quel caso hai zero intersezioni).

La cosa più interessante comunque è che, per k>=3 ed n>=42, puoi ottenere il risultato migliore che sia stato trovato fino ad oggi con zero intersezioni (anche per il caso di n_1<n_k, ovvero spirale rettangolare).

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » ven lug 26, 2013 3:05 pm

Faccio anche notare che, usando 2n-1 linee, puoi risolvere qualsiasi griglia quadrata/rettangolare con zero intersezioni (di qualsiasi natura)... puoi fare lo stesso procedendo con lo schema che ho visto nell'articolo che introduce il paper che ho proposto (una specie di serpentone gigante... questa soluzione però non è altrettanto buona per k>2). :mrgreen:
Inoltre, con il metodo della spirale quadrata pura, è possibile intersecare linee e/o punti il numero di volte che si vuole (zero, una, due o anche più di "n" volte), utilizzando sempre 2n-1 linee: basta infatti prolungare la terzultima linea (iniziando a contare dall'esterno) un altro po' e poi intersecare gli altri punti nel solito ordine, ma prolungando anche queste ultime linee nella misura necessaria per ottenere il numero voluto diintersezioni (provare per fugare eventuali dubbi).

P.S.
Leggendo attentamente l'appendice del primo paper (quella in cui tratto il caso di schemi con valori di "n" potenzialmente diversi), ti imbatterai in un passaggio nel quale dico appunto che con la spirale rettangolare (quadrata) puoi connettere tutti i punti senza intersezioni, rimanendo "inside the box", visitando ogni punto una e una sola volta, con 2*n_1-1 linee (n_1 è il valore minimo dei vari n_i). Adesso notiamo che, aggiungendo un'altra linea, è sempre possibile tornare al punto di partenza! In pratica, si otterranno sempre soluzioni della forma "cammino chiuso", inside the box, senza punti toccati più di una volta, ecc... con 2*n_1 linee totali.
Lo stesso dicasi (usando le opportune formule del paper e aggiungendo al risultato un'unità) per k>=3.
Ultima modifica di marcokrt il sab lug 27, 2013 1:01 am, modificato 1 volta in totale.

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

Re: Problema aperto con i puntini da unire e mia soluzione personale

Messaggio da marcokrt » ven lug 26, 2013 3:36 pm

Domanda: questa nuovo segmento di collegamento, usando il metodo della spirale rettangolare/quadrata, passerà per almeno un punto già "visitato" da altri segmenti? E se le dimensioni diventassero tre? E se fossero k>3?
Io dico di no (in due dimensioni è molto facile da verificare), ma a patto di tracciare la spirale rettangolare partendo dall'angolo "giusto", insomma, avendo la possibilità di decidere da quale angolo iniziare... lascio a voi il divertimento di dimostrarlo :D

1) Per essere brevi, la mia ipotesi/congettura è che, per k>1, usando la spirale rettangolare nel modo che descrivo nel paper, per tornare al punto di partenza con il 2n_1esimo segmento (di retta), non intersecherai mai alcun punto (immagina di fermarti appena prima di ricongiungerti al primo segmento tracciato).

2) Congettura bis (di questa sono un po' meno sicuro): immaginando che i punti su ogni direttrice corrispondano agli interi positivi 1,2,3,4,...,n_i, questa linea di collegamento (per ogni k>1), intersecherà ciascuna semiretta definita dalle varie file di punti in corrispondenza di valori razionali (per k=2,3 sono abbastanza convinto, ma non riesco a visualizzare cosa accadrebbe per k>3).

Rispondi