Elucubrazioni tra segmenti consecutivi e punti

[Pasquale]

Si, ma intanto direi che per n=2 abbiamo 3 soluzioni diverse:

[bautz]

Ri-buongiorno a tutti.
Una soluzione con 6 segmenti senza ripassare 2 volte su un punto può essere questa.

my.jpg (10.84 KiB) Visto 55636 volte

[Bruno]

Bautz che piacere rivederti!

Ho visto adesso la limitazione di Pasquale:
bravo, Bautz

[Pasquale]

Bravo Bautz, mi hai preceduto rispetto a queste altre mie soluzioni con le stesse limitazioni:

[bautz]

Ciao!
E' un piacere anche per me tornare sul forum.

Sembra che con le limitazioni date il numero minimo di segmenti su una maglia 4x4 sia 6, e su una maglia 5x5 sia 8

[Pasquale]

Si, ma anche senza la limitazione di non ripassare sullo stesso punto; anzi in questo caso è anche accertato che in qualsiasi quadrato nxn il problema è sembpre risolvibile con 2n-2 segmenti; partendo ad esempio dal disegno della mia soluzione 4x4, precisamente dalla coda in basso, aggiungendo 5 punti sulla verticale e poi altri 4 in orizzontale, si costruisce un quadrato 5x5 per la cui risoluzione è sufficiente tracciare 2 segmenti; così procedendo a spirale, di possono costruire tutti i quadrati, ogni volta risolvibili con l'aggiunta di 2 segmenti; per cui saranno sufficienti sempre 2n-2 segmenti.

Se il quadrato da 4 fosse stato risolto con 5 segmenti anzicché 6, allora avremmo trovato il sistema di risolvere i quadrati con 2n-3 segmenti, ma questo non è e non so se sia sufficiente per dimostrare che il minimo di 2n-2 non è superabile (forse è solo intuibile).

[fabtor]

Dunque, vediamo di "far quadrare il cerchio":

• 1)Abbiamo visto che la soluzione S=2n-2 è sufficiente
  
  2)Abbiamo costatato che per passare da un quadrato NxN al sucessivo (N+1)x(N+1) occorre aggiungere di fatto due linee di punti fra loro ortogonali
  
  3)Abbiamo osservato inoltre che aggiungendo queste due linee di punti il numero minimo di segmenti (formanti una spezzata) che coprono queste due linee è perforza due. (Pasquale ed altri più implicitamente)
  
  4)E' possibile osservare che dalla soluzione minima di NxN applicando il modello della greca si arriva ad una "soluzione sufficiente" per i casi (N+K)x(N+K) pari a S= 2(N+K) -2
  
  5)Sempre Pasquale ha messo in evidenza che: "Se il quadrato da 4 fosse stato risolto con 5 segmenti anzicché 6, allora avremmo trovato il sistema di risolvere i quadrati con 2n-3 segmenti, [...]".

A questo punto mi sento di aggiungere che poichè la soluzione del 4x4 è possibile ottenerla anche partendo da una soluzione 3x3 applicandole il punto 4 si potrebbe ottenere una soluzione < 6 per il caso 4x4 se e solo se ci fosse una soluzione del 3x3 del tipo S=2N-3, tuttavia questo vorrebbe dire aver per il caso 3x3 S=3 cioè S=N, ma ciò è impossibile poichè non vi sono combinazioni di 3 segmenti consecutivi che possano coprire i 3x3=9 punti quindi mi pare di non sbagliare se a questo punto possiamo dire che S=2N-2 sia anche necessaria oltre che sufficiente e che quindi S=2N-2 è la soluzione minima.

Siete d'accordo?

[Pasquale]

Ni, anche se malamente io stesso ho forzato la medesima conclusione.
Infatti, vorrei avanzare ancora un dubbio:
per il quadrato più piccolo possibile esiste solo la soluzione 2n-1 e se avessimo voluto procedere con la spirale da quella soluzione, a quest'ora diremmo che il minimo è 2n-1;
poi abbiamo visto che già nel quadrato 3x3 le cose migliorano e perché non dovrebbero migliorare con il quadrato 77x77? In fondo era il tuo stesso dubbio iniziale.
Abbiamo poi visto che è stato possibile trovare delle soluzioni passando per ogni punto una sola volta e che questi tipi di soluzione non necessariamente si sviluppano attraverso spirali; dunque chi mi dice che in un nxn di ordine superiore non sia possibile trovare una soluzione di questo tipo con 2n-3 segmenti?
Anche qui vado ad intuito, ma credo che toccare più volte uno stesso punto sia uno svantaggio, perché restano più punti non toccati durante il percorso, che richiederanno quindi più segmenti del necessario, rispetto ad una soluzione con un solo passaggio.
E' evidente che più cresce l'ordine di n, più è difficile districarsi nel labirinto dei vari percorsi, senza un meccanismo come quello della spirale; purtroppo, dal momento che si avvia una spirale, anche partendo da una prima soluzione "pulita", si va a ricadere nella problematica dei punti toccati più volte (almeno 2).
Forse bisognerebbe tentare una strategia di calcolo.
In definitiva, il fatto che in un piccolo quadrato non si riesca ad ottenere una soluzione minore di 2n-2, non per incapacità, ma per oggettiva semplicità del problema a quel livello, ci dice che non è possibile pervenire alla soluzione 2n-3 per nessun quadrato d'ordine superiore, costruito sulla base della prima soluzione, ma perché non è possibile una soluzione con schemi di percorso diversi, che non dipendano dalle soluzioni degli ordini inferiori ? Come si è visto nelle soluzioni "pulite", esistono strategie che permettono di raggiungere gli obiettivi, fuoriuscendo dal perimetro di poco, ma certamente anche di più se il quadrato cresce, con vari zig-zag (presuppongo che sia sempre possibile, anche se difficile).
Che tipo di ragionamento dovrebbe essere posto alla base del calcolo auspicato?
Penso ad un qualcosa del genere, che è facile intravvedere in un piccolo quadrato, diciamo un 4x4.
In tale quadrato, ci sono 16 punti e se fosse possibile una soluzione di 2n-3=5 segmenti, la lunghezza di tali segmenti potrebbe essere la seguente:

4, 3 ed a questo punto resterebbe da coprire 9 punti con 3 segmenti, dovendosi toccare in media 3 punti; questo non è possibile, perché dopo il primo 4-3, resta un solo 3 da poter realizzare, dopodiché si scende a 2 e si perde la media.
Allora possiamo pensare che le prime mosse 4,3 debbano essere riformulate: diciamo 3,3 e restano allora 10 punti da coprire con una media maggiore di 3 che non è possibile mantenere...insomma si vede che non è possibile; d'altra parte, più semplicemente, 16/5=3 con l'avanzo di 1, che richiede una sequenza del tipo 4,3,3,3,3 topologicamente non realizzabile.
In fondo si tratta di un problema più topologico che matematico puro.
Estendere questi abbozzi di ragionamento ad un grande quadrato diventa arduo e sinceramente non saprei proprio come districarmi.
Per me è giusta la risposta 2n-2, ma a livello intuitivo, perché forse non ho capito a fondo la tua sistemazione....chissà cosa ne pensano gli altri e chissà cosa direbbe Gaspero?

[fabtor]

Ma guarda, tutto quello che posso aggiungere al tuo discorso è che per n=2 il minimo di segmenti è 2n-1 perchè tale quadrato è ottenibile da un quadrato 1x1 (dove si può dire che basta un segmento) al quale sono stati cmq aggiunti una linea orizzontale e una verticale e quindi i punti aggiunti sono copribili sempre con non meno di due segmenti forzando la soluzione finale a s = 3 cioè proprio s= 2n-1 (inoltre per n=2 si ha un quadrato senza punti centrali a meno di non considerare tutto il quadrato centro di se stesso).

Per quanto riguarda il fatto che sia uno svantaggio ripassare su un punto già coperto io invece ho qualche dubbio:
è vero che passando dove si è già passati c'è il rischio di avere dei segmenti meno coprenti i punti restanti (ma secondo me è un rischio tutto da dimostrare), ma è vero anche che il non poterci passare implica che in qualche modo il punto già coperto vada aggirato ed avendo a disposizione solo segmenti se dobbiamo aggirare un punto coperto tra due scoperti mi pare (ma anche questo bisognerebbe verificarlo formalmente) che si debba usare un segmento in più e quindi le due strategie dovrebbero essere equivalenti (ed almeno per il momento sembrano esserlo: indipendentemente da quale si è usata non si è trovata una soluzione migliore di 2n-2 per n>2).
Inoltre in realtà ogni volta che incrociamo due segmenti di fatto ripassiamo su uno stesso punto anche se non è un punto evidenziato e per n=3 mi pare che sia assodato che non ci possano essere soluzioni s=2n-2 che non ripassino su di un punto indicato.

D'altro canto questa strada credo che possa sollevare più dubbi che soluzioni, infatti abbiamo che:

per n<= 2 sono necessarie 2n-1 segmenti
per n=3 bastano 2n-2 segmentii, ma ripassando cmq su almeno un punto già coperto
per n=4 (e forse >4) segmenti 2n-2 soluzioni anche senza ripassare su punti già coperti
...
Seguendo questo percorso diventa apparentemente lecito ipotizzare che per n=k abbastanza grande possano bastare 2k-3 e magari anche che per un n=h ancora più grande possano bastare 2h-w con w>2(e di 3) tuttavia, per quanto detto nel mio post precedente, mi pare proprio che vi siano dei vincoli strutturali (si passa da un quadrato al sucessivo aggiungendo sempre due righe tra loro ortogonali) che impediscono valori di w>2, beh almeno su una superfice planare...

[Pasquale]

Si, si, non dico che sia inesatto il tuo argomentare, ma solo non sono convinto del tutto sull'intera faccenda.
Anche quanto affermi nel tuo periodo finale è vero, se ti riferisci alla costruzione di un quadrato maggiore partendo dal quadrato minore già risolto: il mio dubbio sta soltanto nell'ipotizzare una possibile soluzione non dipendente da una precedente; in sostanza, sappiamo che la soluzione più semplice è quella del tipo 2n-1, ma abbiamo toccato con mano che con dei percorsi particolari si riesce con 2n-2; in qualche modo si risparmia un segmento rispetto a 2n-1 ed allora non potrebbe esistere un particolare percorso che ne faccia risparmiare uno in una parte del percorso ed un'altro nella restante parte? Chissà? Magari in un quadrato molto grande, in cui siano ipotizzabili percorsi che si allontanino anche molto dal perimetro.......difficile da verificare.
Intanto, è possibile un 2n-2, toccando i punti una sola volta, in un quadrato 6x6?

[Bruno]

Intanto, è possibile un 2n-2, toccando i punti una sola volta, in un quadrato 6x6?

Al volo...

Se non ho perso qualche pezzo, Pasquale,
direi senz'altro di sì








Una via risolutiva ce l'hai messa sotto
gli occhi proprio tu

[fabtor]

Potreste dirmi con che programma fate i disegni? Io mi devo sempre arrabattare con paint ottenendo risultati piuttosto penosi.

Quello che posso osservare "a naso" è che nelle soluzioni proposte per la soluzione degli nxn con s=2n-2 senza ripassare su di uno stesso punto i segmenti inclinati con angolo diverso da 45° non coprono mai più di due punti. Questa è una limitazione di tipo strutturale o frutto di una strategia risolutiva? Nel primo caso sarebbe potenzialmente un vincolo che potrebbe avvalorare il fatto che non si possono ottenere soluzioni migliori di s=2n-2, mentre nel secondo si avrebbe una indicazione su dove andare a cercare eventuali strategie alternative migliori.

[Pasquale]

Grande Bruno, lo sapevo che avresti elaborato il concetto: in realtà siamo in presenza di due spirali che invertono il senso di rotazione, quasi simmetriche; per questo fatto, non so perché, si passa dal 2n-1 della spirale normale a 2n-2. Man mano che cresce nxn, si allontanano i fuori-perimetro e, come osserva fabtor, finisce che si vanno a toccare sempre due punti e dunque il minimo di 2n-2 non si può superare.
Siamo autorizzati a dire sempre? Boh!

Per quanto riguarda i disegnini, io li ho fatti proprio con Paint, immettendo prima un reticolato preso da Excel, poi lavorando con pennello e linee.
Si potrebbe anche lavorare tutto su Excel e poi utilizzare Paint solo per generare un file jpg, come forse fa Bruno, ma questo ce lo dirà lui.
Si potrebbe, ancora, lavorare su Excel con quadratini grandi, copiare su Word per ridurre le dimensioni e poi su Paint per salvare in jpg.
Oppure fai un disegno su carta, lo acquisisci con lo scanner e lo salvi su Paint.
Insomma, io utilizzo gli strumenti di cui dispongo; altri utilizzano strumenti migliori che non ho e che non mi va neanche di apprendere, per evitare di intasare il computer e di impegnare i pochi neuroni che mi restano ancora liberi.

A proposito di niente di quanto detto adesso, la mano sotto che fa ciao, ciao non è la mia, perché mi servivano due mani per fare la ripresa con la telecamera.