13. Striscia di carta

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

Re: 13. Striscia di carta

Messaggioda xXStephXx » 19/01/2014, 18:10

Eccolo
Immagine
Nell'immagine di sotto si aggancia meglio con l'hint che ho messo.
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: 13. Striscia di carta

Messaggioda b8dc4 » 21/01/2014, 0:02

Provo ad abbatterlo sfruttando l'hint. :)
Considero i lati che appartengono ad almeno due quadrati; se i quadrati sono [tex]n[/tex] questi saranno [tex]n-1[/tex].
Considero il [tex]k[/tex]-esimo di questi lati. Alla sua sinistra ci sono [tex]k[/tex] quadrati, alla sua destra invece ce ne sono [tex]n-k[/tex].
Se [tex]k<n-k[/tex] allora il lato può essere attraversato al più da [tex]2k[/tex] segmenti (che succede quando entrambi i segmenti di cui ogni quadrato alla sua sinistra è estremo lo attraversano).
Se invece [tex]k>n-k[/tex] allora il lato può essere attraversato al più da [tex]2(n-k)[/tex] segmenti (che succede quando entrambi i segmenti di cui ogni quadrato alla sua destra è estremo lo attraversano).
Quindi il numero totale di attraversamenti, che corrisponde anche alla lunghezza totale del percorso, varrebbe al più, quando [tex]n[/tex] è dispari:
[tex](2+4+...+\displaystyle2\frac{n-1}{2})+(\displaystyle2\frac{n-1}{2}+...+4+2)=4(1+2+...+\displaystyle\frac{n-1}{2})=4\displaystyle\frac{(n-1)(n+1)}{8}=\displaystyle\frac{n^2-1}{2}[/tex]
Tuttavia è impossibile che ogni lato venga attraversato da un numero pari di segmenti, in quanto il segmento di inizio parte da un quadrato diverso da quello in cui arriva quello di fine;
quindi ci deve essere almeno un lato attraversato da un segmento in meno rispetto a quelli previsti. Quindi per [tex]n[/tex] dispari la lunghezza massima risulta pari a
[tex]\displaystyle\frac{n^2-1}{2}-1=[/tex][tex]\displaystyle\frac{n^2-3}{2}[/tex].
Se [tex]n[/tex] è pari bisogna considerare anche il lato "centrale", ovvero il caso [tex]k=n-k[/tex]; questo lato può essere attraversato al massimo da [tex]2k-1=n-1[/tex] segmenti (non [tex]2k[/tex] perché in questo caso si dovrebbero avere entrambi i capi da una parte e quindi [tex]k+1[/tex] quadrati da un parte e [tex]k[/tex] dall'altra, impossibile). Pertanto con [tex]n[/tex] pari la lunghezza massima risulta pari a
[tex](2+4+...+\displaystyle2\frac{n-2}{2})+(n-1)+(\displaystyle2\frac{n-2}{2}+...+4+2)=4(1+2+...+\displaystyle\frac{n-2}{2})+(n-1)=4\displaystyle\frac{(n-2)(n)}{8}+(n-1)=[/tex][tex]\displaystyle\frac{n^2-2}{2}[/tex].
Resta ora da dimostrare che sia effettivamente possibile ottenere configurazioni con questi valori; per farlo si può prendere come partenza il quadrato centrale (o quello a sinistra tra i due centrali), poi tracciare il segmento massimo verso destra, poi il massimo verso sinistra, poi ancora verso destra, continuando ad "oscillare" fino a raggiungere il quadrato all'immediata sinistra di quello di partenza.(potrei chiarire meglio questo punto ma sono stanco :) )
Comunque questo problema mi è piaciuto molto :D
b8dc4
 
Messaggi: 80
Iscritto il: 08/05/2013, 15:33

Re: 13. Striscia di carta

Messaggioda xXStephXx » 21/01/2014, 1:55

b8dc4 ha scritto:Comunque questo problema mi è piaciuto molto :D


L'avevo detto che era bello! :lol: E poi boh, probabilmente provandoci un po', senza rinunciare subito, lo si faceva :D Secondo me non andrebbero trascurati i problemi non immediati (lo scrivo perchè ho visto che in questa sezione o un problema è immediato/facile/standard o viene snobbato xD)


Io avevo considerato i segmenti passanti per le facce dei quadrati anzichè passanti per i lati (che era l'hint) ma parrebbe che è la stessa cosa.

b8dc4 ha scritto:Tuttavia è impossibile che ogni lato venga attraversato da un numero pari di segmenti, in quanto il segmento di inizio parte da un quadrato diverso da quello in cui arriva quello di fine;

Ok, in pratica se un lato è attraversato da un numero pari di segmenti, il segmento di inizio e il segmento di fine devono cadere o alla sua destra o alla sua sinistra, ma se noi prendiamo il lato di un quadrato compreso tra l'origine e la fine (che sono su facce diverse quindi esiste), abbiamo che uno sta a destra e l'altro a sinistra e quello sarà attraversato da un numero dispari di segmenti.

b8dc4 ha scritto:Se [tex]n[/tex] è pari bisogna considerare anche il lato "centrale", ovvero il caso [tex]k=n-k[/tex]; questo lato può essere attraversato al massimo da [tex]2k-1=n-1[/tex] segmenti (non [tex]2k[/tex] perché in questo caso si dovrebbero avere entrambi i capi da una parte e quindi [tex]k+1[/tex] quadrati da un parte e [tex]k[/tex] dall'altra, impossibile).

Detta diversamente: il lato centrale non può essere attraversato da $n$ segmenti, visto che i segmenti sono $n-1$.

Poi vabbè il fatto che è possibile costruirlo in quel modo l'aveva già spiegato nil.

Però secondo me boundare $l$ era più corposo di costruirlo in modo ottimale (forse 4-3 se non 5-2) quindi direi vai col prossimo :D
xXStephXx
 
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Precedente

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti