Pagina 1 di 1

Piccioni viaggiatori

Inviato: ven gen 10, 2014 4:50 pm
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?

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 5:23 pm
da franco
marcokrt ha scritto:.... $n=4$-->$l=7$,...

:?:

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

o forse ho non ho capito il problema :?

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 5:43 pm
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?

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 6:57 pm
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 :)

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 6:58 pm
da marcokrt
(Il percorso minimo è facile da calcolare... $l=n-1$).

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 7:05 pm
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.

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 8:31 pm
da Pasquale
potrebbe essere: $l_{n+1} = l_n+n+MOD(n,2)$

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 8:41 pm
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.

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 11:35 pm
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?)

Re: Piccioni viaggiatori

Inviato: ven gen 10, 2014 11:41 pm
da marcokrt
Sì, infatti.

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