13. Striscia di carta

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

13. Striscia di carta

Messaggioda xXStephXx » 14/01/2014, 19:39

Si ha a disposizione una striscia di carta lunga $n$ quadretti.
Si vuole massimizzare la lunghezza totale $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 caselle ancora libere. Il gioco termina quando i centri di tutte le caselle sono stati origine o punto terminale di un segmento.

(Per "caselle ancora libere" si intende caselle che non siano già state origine o fine di un altro segmento)

Per aiutare nella comprensione:
con $n=2$ si ha $l=1$ con $n=3$ si ha $l=3$ e con $n=4$ si ha $l=7$.
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda sall96 » 15/01/2014, 5:54

non capisco perche' con $n=4$ hai $l=7$... A me viene 6, e se e' giusto mi indirizzerei verso
Testo nascosto:
somma di naturali consecutivi :D

ma se $l=7$ ... :?
sall96
 
Messaggi: 156
Iscritto il: 16/05/2013, 19:12

Re: 13. Striscia di carta

Messaggioda nil » 15/01/2014, 14:38

Metti che hai 4 quadretti : inizi dal secondo da sinistra fino all'ultimo, e sono $2$ , poi dall'ultimo al primo , e sono $3$, poi da lì al terzo, e sono $2$... quindi $2+3+2=7$
nil
 
Messaggi: 316
Iscritto il: 23/06/2013, 18:48

Re: 13. Striscia di carta

Messaggioda xXStephXx » 15/01/2014, 14:56

5:54 ! LOL


Comunque sì, si può anche fare un percorso di lunghezza $7$.

|-|-|-| |
|-|-|-|-|
| |-|-|-|

[edit] ok xD
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda sall96 » 15/01/2014, 19:19

si scusate, che errore stupido :D
PS: comunque per l"orario io sono 7 ore indietro all'italia :) da me erano quasi le 23
sall96
 
Messaggi: 156
Iscritto il: 16/05/2013, 19:12

Re: 13. Striscia di carta

Messaggioda xXStephXx » 17/01/2014, 11:49

Forse è meglio dare qualche hint. Ma giusto perchè c'è moltissima attività in questo periodo e il fatto che non sia stato provato in $2$ giorni è segno che forse non verrà provato mai xD
Testo nascosto:
Per ora dico solo che basta una sola considerazione per capire tutto il meccanismo.
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda nil » 17/01/2014, 21:48

Testo nascosto:
Dividiamo i casi in cui $n$ è pari e quelli in cui è dispari.
Se $n$ è dispari:
Partendo dal centro , si hanno due vie speculari , ed ogni linea comunque passa o tra il quadretto al centro e quello alla sua sinistra o a quello alla sua destra , ed è lì che posizioniamo il quadretto in più per massimizzare $n+1$ , aumentando la lunghezza di $n-1+2=n+1$ : infatti abbiamo che il punto finale ha distanza $2$ dal quadretto che posizioniamo in più, e che settiamo come nuovo punto finale.
Se $n$ è pari:
Partiamo dal punto finale trovato con $n$ dispari.Abbiamo che la distanza dal centro del punto finale e di quello iniziale è la stessa , e ogni linea passa per il centro , perciò per massimizzare $n+1$ posizioniamo il quadretto in più al centro , così da aumentare in ogni caso la lunghezza di $n-1+1=n$ e lo poniamo poi come punto di inizio di $n+1$.

(Vorrei mettere dei diagrammi per spiegare meglio perché infatti è scritto un po' male però sarebbe complicato farli con latex penso :lol: )

Questi accorgimenti valgono per induzione avendo come passi base i casi in cui i quadretti sono $2$ e $3$.
Perciò la sequenza dovrebbe essere tale che $S(2n) = S(2n-1) + n +1$ e $S(2n+1) = S(2n)+n$.
Dimmi (ditemi) se è giusta prima così vedo se trovare la forma chiusa
nil
 
Messaggi: 316
Iscritto il: 23/06/2013, 18:48

Re: 13. Striscia di carta

Messaggioda xXStephXx » 17/01/2014, 23:13

Le relazioni sono giuste xD Cioè in realtà:
$S(2n)=S(2n-1)+2n+1$ e $S(2n+1)=S(2n)+2n$ (ciò è dovuto al fatto che le lunghezze sono $2n$ e $2n+1$ non $n$ ed $n+1$).

E comunque in questo problema non penso che (rigorosamente) per massimizzare $n+1$ bisogna partire dalla configurazione che massimizza $n$. D'altronde non si ha la certezza che il percorso che massimizza $n$ sia valido anche per massimizzare $n+1$. In fondo chi ti assicura che per massimizzare $n+1$ gli altri segmenti devono essere messi nel modo in cui massimizzavano $n$? In teoria può anche essere che nel caso $n+1$, mettendo i primi $n-1$ segmenti in modo diverso da come stavano per massimizzare $n$, ottieni una lunghezza totale minore da quegli $n-1$ segmenti, ma poi piazzando l'$n-esimo$ segmento (quello in più) ottieni una lunghezza maggiore di $2$ che ti bilancia quello che hai perso prima.

Diciamo che hai trovato un modo valido per tracciare i segmenti, ma manca da dimostrare che non si può far di meglio.
E per dimostrare che non si può far di meglio, penso che ti conviene cambiare approccio, osservando che c'è una limitazione che non può essere MAI superata a prescindere da come vengono tracciati i segmenti. Se trovi una limitazione del genere hai concluso.

Testo nascosto:
E questa condizione necessaria può essere trovata facendo considerazioni d'altro tipo, senza appoggio ai casi precedenti.
Ed è forse la parte più bella del problema. Io in realtà prima di trovare il modo che massimizza ho trovato la condizione necessaria, e una volta trovata quella è quasi naturale tracciare i segmenti in modo ottimale.


(Non vorrei sembrare pignolo eh :D ma quando ti appoggi al caso precedente per fare il successivo devi dimostrare rigorosamente per quale motivo la configurazione già fatta resta valida, specie se si tratta di massimizzare, cosa che in questo caso non è evidente (per le motivazioni di prima))
Normalmente il passaggio che hai fatto lo puoi fare solo se ciò che fai al passaggio $n+1$ è indipendente da ciò che hai fatto prima.
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda xXStephXx » 19/01/2014, 16:45

Vabbè dai metto un hint, da quel che ho capito si preferiscono sempre i problemi algebrici/aritmetici e questi vengono odiati da tutti :lol:
Forse ho gusti strani xDDD
Testo nascosto:
Le due caselle ai bordi possono essere attraversate da massimo $2$ segmenti. E quelle ad esse adiacenti da quanti? E poi andando via via verso quelle centrali? xD
A questo punto basta solo provarci per riuscire a risolverlo xD
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda aetwaf » 19/01/2014, 16:59

Non mi è chiaro il tuo percorso di $7$ per $n=4$
aetwaf
 
Messaggi: 433
Iscritto il: 11/12/2013, 18:54

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite