Piccioni viaggiatori

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

Piccioni viaggiatori

Messaggio da marcokrt »

Ecco a voi un problemino che mi sono inventato in questi giorni e che ho scoperto essere più complesso di quanto immaginassi:

Sia data una striscia di carta suddivisa in $n$ caselle quadrate ($n$ naturale positivo $>1$). La distanza tra due caselle contigue è per definizione unitaria. Tutte le caselle sono numerate progressivamente, da $1$ ad $n$.

Il gioco è il seguente, massimizzare la lunghezza aggregata ($l$) degli $n-1$ segmenti che congiungono i centri di tutte le $n$ caselle, partendo da uno di essi a piacere e tracciando il segmento che termina in un'altra casella, considerare dunque quest'ultima casa come punto di partenza per il secondo segmento e farlo terminare in una delle restanti $22$ caselle ancora libere. Il gioco termina i centri di tutte le case sono stati origine e/o punto terminale di un segmento.

Esempio: $n=2$-->$l=1$, $n=3$-->$l=3$, $n=4$-->$l=7$,...


Qual'è la regola generale?

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Piccioni viaggiatori

Messaggio da franco »

marcokrt ha scritto:.... $n=4$-->$l=7$,...

:?:

io avrei detto $n=4$-->$l=6$.

o forse ho non ho capito il problema :?
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Piccioni viaggiatori

Messaggio da delfo52 »

in effetti il testo è alquanto oscuro.
il termine "striscia" fa pensare a elementi in fila
il termine "suddivisa" fa pensare ad una partizione del piano che non lasci spazi tra le caselle, ma
si parla di "distanza tra caselle contigue", nel senso che contigue significa "attaccate", o solo "vicine" ?
si può passare più volte nello stesso punto centrale?
si può intersecare il percorso?
davvero si cerca il percorso più lungo?, o il più corto?
Enrico

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

Re: Piccioni viaggiatori

Messaggio da marcokrt »

Ciao Enrico,
Grazie del commento... passo subito alle risposte chiarificatrici:

1 2 3 4 5 6 ... n-3 n-2 n-1 n

La situazione di partenza è quella che ho scritto sopra. Ogni cella può essere considerata un numero naturale da 1 a n; la lunghezza di un segmento è pertanto data dal valore assoluto della differenza tra il punto di partenza e quello di arrivo (insomma, il valore della cella in cui cade l'estremo più a destra.
Siamo in un contesto "monodimensionale", quindi sì... toccherà passare per forza (n>2) sulla stessa cella più volte, ma una volta che un estremo si colloca su una data cella, essa non può più essere usata come punto di arrivo per un segmento successivo (essa costituirà solo il punto di partenza per il successivo segmento e poi verrà "cancellata"). L'ultima cella sarà chiaramente solo un punto di arrivo e il gioco terminerà lì.

Si cerca il percorso più lungo :)

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

Re: Piccioni viaggiatori

Messaggio da marcokrt »

(Il percorso minimo è facile da calcolare... $l=n-1$).

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

Re: Piccioni viaggiatori

Messaggio da marcokrt »

franco ha scritto:
marcokrt ha scritto:.... $n=4$-->$l=7$,...

:?:

io avrei detto $n=4$-->$l=6$.

o forse ho non ho capito il problema :?

Credo tu abbia capito bene... questa è la strategia che ho utilizzato io per il problema dei nove punti esteso... eppure (per n>=4) si può fare di meglio... esempio pratico: n=6-->l=17 (anziché 15).


1 2 3 4 5 6

Segmento 1: 3-->5 (lunghezza=2)
Segmento 2: 5-->1 (lunghezza=4)
Segmento 3: 1-->6 (lunghezza=5)
Segmento 4: 6-->2 (lunghezza=4)
Segmento 5: 2-->4 (lunghezza=2)

Lunghezza totale=17.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Piccioni viaggiatori

Messaggio da Pasquale »

potrebbe essere: $l_{n+1} = l_n+n+MOD(n,2)$
_________________

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

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

Re: Piccioni viaggiatori

Messaggio da marcokrt »

Va beh... direi che più o meno ci dovremmo essere.

La mia soluzione è $floor(n^2/2)-1$... può essere scritta anche come l(n) = l(n-1)+n-1+(n-1 mod 2), per ogni n>2.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Piccioni viaggiatori

Messaggio da Pasquale »

si, è uguale: MOD(n,2) = (n mod 2) e se:
n=n+1, dalla tua si passa alla mia; la tua funzione però è più pratica essendo solo funzione di n (FLOOR = INT giusto?)
Ultima modifica di Pasquale il ven gen 10, 2014 11:41 pm, modificato 1 volta in totale.
_________________

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

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

Re: Piccioni viaggiatori

Messaggio da marcokrt »

Sì, infatti.

Con "Floor" indico l'operatore "arrotonda all'intero precedente" (esempio, Floor(4)=4 e Floor(3.98=3)).

Rispondi