Elucubrazioni tra segmenti consecutivi e punti

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

Moderatori: Gianfranco, Bruno

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » lun apr 26, 2010 4:35 pm

Partendo dal giochino di logica: "Unire nove punti disposti a quadrato come da disegno (qui eseguito con gli smile) con solo quattro segmenti senza mai staccare la penna":
  • 8) 8) 8)
    8) 8) 8)
    8) 8) 8)
di cui la soluzione è ormai arcinota mi sono chiesto quanto doveva essere il numero di segmenti minimo da utilizzare senza mai staccare la penna se invece di nove i punti fossero stati 16 disposti a quadrato come da disegno (sempre eseguiti con gli smiles):
  • :twisted: :twisted: :twisted: :twisted:
    :twisted: :twisted: :twisted: :twisted:
    :twisted: :twisted: :twisted: :twisted:
    :twisted: :twisted: :twisted: :twisted:
Facendo qualche tentativo mi sono accorto che tale numero minimo sembra debba essere sei.

Mi chiedo tuttavia se tale conclusione sia corretta ed in tal caso se si possa riuscire a trovare una formula generale che dato il numero di punti formarti il quadrato permetta di calcolare il numero minimo di segmenti che si possono utilizzare senza staccare la penna (sapendo che nel caso banale per un quadrato costituito da quattro punti bastano tre segmenti di questo tipo).



Potete aiutarmi?

Grazie.

Fabtor
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

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

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da Bruno » mar apr 27, 2010 1:16 am

Ciao, Fabtor :D

Se riesco provo a ragionare sul tuo quesito, trovo che sia proprio
interessante!
(In effetti, di primo acchito anch'io confermerei i tuoi sei tratti.)

Adesso vorrei solo scriverti una cosa di tipo organizzativo, direi
così.
Di solito i nuovi problemi vengono prima proposti nel "Forum" e
non in "Quesiti irrisolti". In questa sezione infatti finiscono quegli
argomenti che per qualche ragione non sono stati risolti dopo la
loro presentazione nel Forum o in qualche altra parte del sito.
Il Forum è senz'altro più frequentato, lì sei più visibile, e in questo
modo evitiamo inoltre che Pietro (l'Admin) ti sposti ogni volta :wink:

Grazie a te e a presto,


Bruno
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » mar apr 27, 2010 9:19 am

Bruno ha scritto:Ciao, Fabtor :D

Se riesco provo a ragionare sul tuo quesito, trovo che sia proprio
interessante!
(In effetti, di primo acchito anch'io confermerei i tuoi sei tratti.)

Adesso vorrei solo scriverti una cosa di tipo organizzativo, direi
così.
Di solito i nuovi problemi vengono prima proposti nel "Forum" e
non in "Quesiti irrisolti". In questa sezione infatti finiscono quegli
argomenti che per qualche ragione non sono stati risolti dopo la
loro presentazione nel Forum o in qualche altra parte del sito.
Il Forum è senz'altro più frequentato, lì sei più visibile, e in questo
modo evitiamo inoltre che Pietro (l'Admin) ti sposti ogni volta :wink:

Grazie a te e a presto,


Bruno
Ah, ok scusate avevo inteso la distinzione forum / quesiti irrisolti, in altro modo:avevo inteso il forum come una sorta di archivio di quanto è stato risolto per cui pensavo che un quesito quando entra va negli irrisolti per definizione poichè appunto da risolvere per poi venire trasferito una volta risolto.

Per quanto riguarda la tua soluzione appena possibile cerco di mettere anche la mia, poichè ad occhio hai trovato una configurazione di segmenti differente dalla mia nel senso che, a diferenza del caso più semplice del quadrato 3x3 che ha sì quattro soluzioni ma tra loro simmetriche, le "nostre" due ad occhio mi pare che siano proprio del tutto differenti il che potrebbe aprire una finestra anche sul mondo del calcolo combinatorio per l'individuazione di quante soluzioni alternative a numero di segmenti minimo vi sono per un quadrato nxn... la cosa si fa interessante ;).
Ultima modifica di fabtor il mar apr 27, 2010 9:47 am, modificato 1 volta in totale.
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » mar apr 27, 2010 9:44 am

Ogni promessa è debito ecco la mia soluzione grafica per 6 segmenti.

(Scusatemi, ma l'ho dovuta allegare zippata... non ho saputo fare di meglio :roll: )
Allegati
griglia punti segmenti 4x4.zip
(4.96 KiB) Scaricato 430 volte
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

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

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da Bruno » mar apr 27, 2010 10:00 am

Fabtor, non riesci a salvarla come immagine gif, jpg o png?

Se poi clicchi qui

Immagine

si apre questa finestra

Immagine

in cui puoi caricare l'immagine dal tuo pc e così ottieni
la stringa da riportare nel tuo messaggio:

Immagine

Naturalmente l'immagine dev'essere preliminarmente
ridotta se è troppo grande.

Purtroppo io non riesco a vedere il tuo documento :|
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » ven apr 30, 2010 2:01 pm

Per comodità avevo fatto il disegno prima in pdf e poi con gip 2, ma ora che ho avuto un po' di tempo l'ho rifatto con paint, eccolo (non è precisissimo come piace a me, ma il tempo che ho è quello che è... cmq direi che può andare) :

Immagine
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » ven apr 30, 2010 9:27 pm

Piccolo aggiornamento ho fatto un po' di tentativi con il 5x5 e (anche se un po' meno) con il 6x6 è ho notato le seguenti cose:

1) sembra che il numero minore di segmenti per coprire tutti i punti dei 2 quadrati sia interno ad esso e non esterno come nei casi del 3x3 e 4x4
2) inoltre se non ho commesso errori il numero minimo per il 5x5 è otto mentre per il 6x6 è 11

Il Primo punto mi porta ad ipotizzare che dato un quadrato NxN se N>=5 il numero minimo di segmenti S per coprire tutti gli NxN punti lo si ottiene non uscendo dai margini del quadrato NxN.

Il secondo punto mi fa congetturare che il legamen tra S (numero minimo di segmenti consecutivi che coprono tutti i punti del quadrato ed il lato N del quadrato sia:

S = N + F(N-1) con F(N-1) = all'N-1nesimo numero della serie di Fibonacci.

Naturalmente queste sono solo congetture, tuttavia sono abbastanza confidente che qualche matematico serio (cosa che io non sono) lavorandoci sopra possa riuscire a dimostrarle o a confutarle (la cosa è decisamente aldisopra della mia portata).

Curiosità: sempre nell'ipotesi che io non abbia commesso errori la soluzione del 5x5 che ho trovato è "figlia" di quella del 3x3 mentre le due soluzioni trovate per il 6x6 sono "figlie" della 3x3 e della "mia" 4x4 rispettivamente (non ho ancora testato quella di Bruno).
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

panurgo
Livello 8
Livello 8
Messaggi: 1204
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da panurgo » sab mag 01, 2010 9:25 am

Evidentemente è sempre possibile collegare i punti di una griglia n\/\times\/n con 2n\/-\/1 tratti: n tratti orizzontali collegati da n\/-\/1 tratti verticali.
Sembra che ciò che cerchiamo sia un modo sistematico per farlo con 2n\/-\/2 tratti...
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » sab mag 01, 2010 3:00 pm

panurgo ha scritto:Evidentemente è sempre possibile collegare i punti di una griglia n\/\times\/n con 2n\/-\/1 tratti: n tratti orizzontali collegati da n\/-\/1 tratti verticali.
Sembra che ciò che cerchiamo sia un modo sistematico per farlo con 2n\/-\/2 tratti...
Non credo di aver capito bene quello che hai scritto... :( sei sicuro del 2n-2 o è una supposizione? (almeno nei due casi banali per n = 1 e N = 2 mi sembra che non sia possibile :| ).

Cmq Fibonacci non centra nulla: la serie cresce troppo in fretta...
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 785
Iscritto il: mer apr 20, 2005 2:47 pm
Località: Benevento

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da Admin » dom mag 02, 2010 11:34 am

Ciao,
ho spostato il topic dalla sezione "irrisolti" a quella "principale".

Bruno, ti ringrazio per il tuo puntuale aiuto.

Ciao
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Pasquale
Livello 11
Livello 11
Messaggi: 2385
Iscritto il: mer mag 25, 2005 1:14 am

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da Pasquale » lun mag 03, 2010 12:06 am

Scusate, forse ricordo male, ma in questo tipo di gioco non c'era anche la condizione che consentiva il passaggio su ogni punto per una sola volta?
In tal caso, aggiungendo anche la condizione di non fuoriuscire dal perimetro, per ogni quadrato di n punti di lato, certamente con 2n-1 segmenti il gioco si risolve sempre, come annunciato anche da Pan, il quakle credo voglia intendere che 2n-2 sarebbe la soluzione da ricercare per fare meglio: probabilmente si potrà anche fare, ma senza le limitazioni sopra annunciate
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » mar mag 04, 2010 8:59 am

Inizio col rispondere a Pasquale:

La risposta è no, l'ulteriore l'imitazione del non ripassare su punti già coperti non è presente nel testo originale.
Infatti il gioco del 3x3 era nato per testare la capacità di rispettare la consegna iniziale senza aggiungersi degli autovincoli mentali: Il testo infatti non vincola ne a non ripassare sugli stessi punti ne a non uscire dal "quadrato" delimitato dai punti e ciò nonostante molti di coloro che inizialmente si approcciano per le prime volte ad un tentativo di soluzione rimangono "al palo" proprio perchè incosciamente si pongono inconsciamente dei limiti più stringenti di quelli dati dal problema.

Detto questo ritornarno a studiare la risposta di Panurgo ho fatto le seguenti considerazioni:
Fra le tante possibili soluzioni del problema per un quadrato nxn del tipo S = 2n-1 (che esistono sempre) c'è sempre la configurazione "a spirale quadrata" - che chiamerò "a greca" d'ora in poi quando capiterà di citarla - (ho provato a disegnarla ma anche l'immagine più semplice mi dice che è troppo pesante per inserirla :? )

Il passaggio sucessivo è stato quello di trovare una soluzione per il 4x4 s=2n-2 che contenesse il motivo della soluzione 3x3 2n-2 (esiste ed è una terza soluzione distinta rispetto a quelle trovate precedentemente da me e da Bruno).

Come precedentemente indicato sia la soluzione 5x5 sia una delle soluzioni del 6x6 per s= 2n-2
contenevano già il motivo della soluzione 3x3.
Di fatto si può osservare che queste soluzioni sono una "fusione" del motivo 3x3 e della soluzione "a greca", che chiamerò soluzioni "grecoidi", che permettono di risparmiare un segmento rispetto alle soluzioni "a greca" sopra citate.
E' possibile osservare inoltre che quando n>2 per n dispari il motivo 3x3 è sempre centrato rispetto al quadrato nxn mentre per n pari tale motivo è sempre leggermente eccentrico. tuttavia per tutti i casi che ho analizzato (cioè fino a n = 9) adottando queste configurazioni "a grecoide" è sempre possibile trovare una soluzione s=2n-2.

Inoltre per tutti i quadrati a n dispari con n>2 tali soluzioni "a grecoide", poichè la soluzione 3x3 è sempre centrata, sono sempre banalmente individuabili (per quelle a n pari con n>2, la cosa è operativamente leggermente più complicata per via del fatto che va individuata correttamente la posizione eccentrica della configurazione 3x3 nello schema, ma basta in realtà posizionarla in modo tale che essa non vada ad incrociarsi/sovrapporsi con lo schema a "greca" che parte dal 5 segmento in avanti ed il gioco è fatto).

Da queste osservazioni si può dedurre/ipotizzare che, per le condizioni iniziali poste, con n>2 è sempre possibile trovare per il quadrato nxn una soluzione s = 2n-2.

Questo tuttavia non risolve il nostro problema, infatti come non esistono soluzioni s = 2n-2 per n<3 non è assolutamente detto a priori che non esista un n sufficientemente grande tale che la soluzione s = 2n-2 (pur essendo sempre esistente per n>2) sia quella a minor numero di segmenti s.

Quindi a mio modo di vedere ora ci si trova di fronte a questo bivio:

1) O si riesce a dimostrare che non vi sono soluzioni migliori delle soluzioni s=2n-2 per qualunque n>2 e quindi abbiamo dimostrato che si hanno 2 soluzioni minime una per n>2 e una per n<3 con n intero

2) Oppure si scopre che esiste una "famiglia di n di cofine" i cui elementi permettono di individuare classi di quadrati nxn che ammettono soluzioni minime s= 2n-k con K dipendente dall'n minimo di classe.

Ora poichè devo lasciarvi vi ripasso "la palla".

Ciao
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

panurgo
Livello 8
Livello 8
Messaggi: 1204
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da panurgo » mar mag 04, 2010 11:30 am

E' esattamente il ragionamento che ho fatto io

Immagine

Immagine

Immagine

Resta da dimostrare che 2n\/-\/2 segmenti siano anche necessari
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Pasquale
Livello 11
Livello 11
Messaggi: 2385
Iscritto il: mer mag 25, 2005 1:14 am

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da Pasquale » mar mag 04, 2010 3:15 pm

Si, la spirale o anche lo zigzag danno la stessa soluzione 2n-1.

Limitandosi alla sola condizione di non staccare mai la penna, al momento resterebbe da cercare una soluzione 2n-3 per dimostrare (solo e non altro) che 2n-2 non è il massimo che si può fare, anche se non non trovandola non sarebbe stato dimostrato nulla; tuttavia, trovandola, si sarebbe fatto un piccolo passo avanti per stimolare la ricerca.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

fabtor
Livello 5
Livello 5
Messaggi: 226
Iscritto il: mar nov 17, 2009 3:59 pm

Re: Elucubrazioni tra segmenti consecutivi e punti

Messaggio da fabtor » mar mag 04, 2010 7:45 pm

beh se si trovasse una soluzione s = 2n-3 ed il relativo n minimo per cui vale tale soluzione si in comincerebbero ad avere già tre valori di n minimi legati alle soluzioni di s e chissà magari questi n minimi potrebbero essere disposti in modo tale da trovare facilmente tutta la sequenza corretta degli n min e magari dei k(n min) (non è detto che procedano in sequenza) di una più generale formula s= 2n -k(n min)... 8)

Naturalmente bisogna ancora rispondere alla seconda questione relativa a questo "pastice" cioè: dato un quadrato nxn quante soluzioni s minime tra loro alternative e non simmetriche l'una rispetto all'altra ci sono. (al momento siamo per n=2--> 2 per n=3 --> 1 e per n = 4 --> almeno 3)
Ah, se i portieri avessero sulla maglia: |e^{-i\pi}|...

Pongo y = x^{2} quindi y=\frac {x^{2}}{pongo}
[tratto da un compito in classe di uno studente di prima superiore]

Il vero gnomone aureo: http://thumbs.dreamstime.com/z/gnomo-de ... 526933.jpg

Rispondi