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: 1033
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: 1033
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: 1033
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
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).

valeriob
Nuovo utente
Nuovo utente
Messaggi: 3
Iscritto il: ven nov 15, 2019 7:11 am

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

Messaggio da valeriob » ven nov 15, 2019 8:17 am

Buongiorno a tutti. Scusate se posto in un argomento di 6 anni fa… mi sono appena iscritto e non conosco ancora le regole. Sono un grande appassionato di test di logica con un livello medio di abilità matematiche (possiedo solo un diploma di liceo con votazione mediocre).
Se a qualcuno può interessare, sono riuscito a trovare un algoritmo generale per il problema leggermente più performante di quello proposto da marcokrt, sfuttando tre differenti "path" bidimensionali in base al caso.
Ecco l'articolo (chiedo perdono per il link, ma sono ben 28 pagine di conti…):
http://pdfhost.io/v/ZXoE2OJEd_n_1_X_n_2 ... alepdf.pdf
Trovare un algoritmo generale migliore credo sia qualcosa di sovrumano, ma non si sa mai :-)
Se vi interessa, sarei lieto di metterlo a disposizione del sito. Fatemi sapere.

Bruno
Livello 8
Livello 8
Messaggi: 1128
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

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

Messaggio da Bruno » ven nov 15, 2019 9:22 am

Benvenuto, Valerio :D
A una prima occhiata mi sembra interessante il tuo lavoro, grazie per avercelo sottoposto.
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

valeriob
Nuovo utente
Nuovo utente
Messaggi: 3
Iscritto il: ven nov 15, 2019 7:11 am

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

Messaggio da valeriob » ven nov 15, 2019 10:19 am

Salve Bruno,
Grazie per la risposta. Sono contento che vi sia piaciuto.
Mi sono imbattuto in questo problema nel 2017 grazie a un video pubblico di Marco Ripà in cui chiedeva di risolvere il 5X5X5 in meno di 41 linee. Non ho potuto partecipare alla sfida, avendo visto il video in ritardo, ma ho deciso comunque di dare un contributo utile agli appassionati del problema, riuscendo a risolvere il 5×5×5 in 40 linee e, contemporaneamente, abbassando molti altri "upper bound" per il caso n×n×n. Assieme a Marco Ripà, che mi ha molto aiutato, ho pubblicato il tutto su viXra e, successivamente, sono riuscito a estendere l'algoritmo a n_1×n_2×…×n_k.

In pratica, si costruiscono dei "path" bidimensionali in cui si utilizzano il minimo numero di linee possibili (2×n_2-1 se n_1=n_2=2 o n_1>n_2, e 2×n_2-2 se n_1=n_2>2) e nei quali il numero di punti per linea è massimizzato nelle prime linee (esterne) tracciate, in maniera tale da poter sfruttare al meglio un algoritmo per le griglie tridimensionali (proposto da Ripà nel 2016) che consiste nel ripetere parzialmente il "path" bidimensionale su ogni faccia bidimensionale della griglia fino a l_i linee, lasciando p punti (interni) allineati per cui si passerà successivamente con un semplice "path" rettilineo (una banale "serpentina").
In questa maniera, si riescono a ottenere dei risultati leggermente migliori di quelli dell'algoritmo proposto da Ripà nel 2013.
C'è da dire che, se si risolvono singolarmente i vari problemi, senza un algoritmo "fisso" generale, come Ripà ha fatto per 6>n_1≥n_2≥n_3, si ottengono risultati nettamente migliori (per esempio, 36 linee il 5×5×5). Per un problema così complesso, penso che la strategia giusta per ottenere risultati ottimali sia proprio quella.

valeriob
Nuovo utente
Nuovo utente
Messaggi: 3
Iscritto il: ven nov 15, 2019 7:11 am

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

Messaggio da valeriob » lun nov 18, 2019 12:18 pm

Buongiorno di nuovo,
vista la data dell'ultimo post, vedo che state lavorando parecchio sul mio lavoro :-)
Se avete domande su qualche passaggio, sono tranquillamente a vostra disposizione (è abbastanza lungo e complesso).

Penso sarebbe interessante se qualcuno provasse anche a migliorare ulteriormente il risultato: la differenza tra "upper bound" e "lower bound" è ancora alta per la maggior parte dei casi.
I problemi ancora da risolvere possono essere sintetizzati in due:
-il limite superiore si discosta ancora molto dal limite inferiore, e la differenza aumenta aumentando il valore di n_k.
-anche il limite inferiore non è perfetto: per n_k=2, spesso è più basso della soluzione esatta al problema. Di conseguenza, potrebbero esserci dei limiti superiori trovati coincidenti con la soluzione esatta ma non coincidenti con il limite inferiore.
Il problema è ancora aperto!!

Rispondi