24. Ciancica: la donna in carriera (staffetta)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 11 giu 2011, 11:36

Ciancica è una giovane donna in carriera che adora le scarpe. Ne ha la bellezza di 2011 paia differenti. Oggi è stata assunta in un'azienda, in cui deve lavorare ogni santo giorno, Domenica compresa, e vorrebbe arrivare ai vertici di questa mantenendo sempre però un certo stile, quindi segue qualche regola d'eleganza fin da subito:
  • Non indosserà mai 2 giorni di seguito lo stesso paia di scarpe.
  • Dati $0<a<b<c<d$ se Ciancica indossa le stesse scarpe nell' $a-$esimo giorno di lavoro e nel $c-$esimo e anche le stesse scarpe nel $b-$esimo e nel $d-$esimo allora nei giorni $a,b,c,d$ indossa sempre lo stesso paio di scarpe! (naturale esigenza di stile :D )
In quanti modi può decidere di indossare le scarpe Ciancica per poter far carriera il più a lungo possibile mantenendo comunque il suo stile?

p.s. è semi-own (quindi non ho la certezza riguardo l'esattezza della mia soluzione... ) e secondo me è pure figo :)
p.p.s. forse il testo non è chiarissimo, se non si capisce chiedete ;)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da paga92aren » 11 giu 2011, 11:56

dario2994 ha scritto: allora nei giorni $a,b,c,d$ indossa sempre lo stesso paio di scarpe! (naturale esigenza di stile :D )
Non ho capito questa frase...cosa intendi con $a,b,c,d$?

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 11 giu 2011, 11:58

paga92aren ha scritto:
dario2994 ha scritto: allora nei giorni $a,b,c,d$ indossa sempre lo stesso paio di scarpe! (naturale esigenza di stile :D )
Non ho capito questa frase...cosa intendi con $a,b,c,d$?
Numeri interi positivi, insomma negli $a,b,c,d$-esimi giorni di lavoro indossa lo stesso paio di scarpe.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da paga92aren » 11 giu 2011, 12:04

Quello lo davo per scontato, comunque rileggendo bene il testo ho capito.

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da paga92aren » 11 giu 2011, 12:28

Se la soluzione è 2012! allora la posto.

EDIT: completamente cannato
Ultima modifica di paga92aren il 11 giu 2011, 15:33, modificato 1 volta in totale.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 11 giu 2011, 12:32

paga92aren ha scritto:Se la soluzione è 2012! allora la posto.
Bon... a me viene diverso... ma non mi ci giocherei un braccio. Se vuoi piazzala, al più mi diverto a scovare chi ha segato :D
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da Nonno Bassotto » 11 giu 2011, 13:02

Non ho capito bene la seconda condizione. Stai dicendo che non può mai alternare due paia di scarpe diverse?
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 11 giu 2011, 13:08

Nonno Bassotto ha scritto:Non ho capito bene la seconda condizione. Stai dicendo che non può mai alternare due paia di scarpe diverse?
Sì (anche in giorni non consecutivi)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

ileo83
Messaggi: 69
Iscritto il: 03 giu 2011, 23:44
Località: pisa

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da ileo83 » 11 giu 2011, 15:47

e in giorni consecutivi? lo puoi fare, in giorni consecutivi? o nno?
Il vecchio conio OO

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 11 giu 2011, 17:59

ileo83 ha scritto:e in giorni consecutivi? lo puoi fare, in giorni consecutivi? o nno?
No
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

ileo83
Messaggi: 69
Iscritto il: 03 giu 2011, 23:44
Località: pisa

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da ileo83 » 12 giu 2011, 01:26

e perche'? ma soprattutto, perche'?
Il vecchio conio OO

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 12 giu 2011, 09:43

ileo83 ha scritto:e perche'? ma soprattutto, perche'?
Mi pareva che fosse implicito nel testo, ma forse è il caso di chiarirlo: nel periodo tra il 400 e il 300 dopo Cristo le donne acquisirono coscienza delle potenzialità di imprinting che costernavano, Ciancica non è certo da meno!
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da Anér » 12 giu 2011, 09:58

dario2994 ha scritto:nel periodo tra il 400 e il 300 dopo Cristo le donne acquisirono coscienza delle potenzialità di imprinting che costernavano, Ciancica non è certo da meno!
Ohiboh, di che periodo stiamo parlando? E le potenzialità di imprinting di cui si acquisì la coscienza, chi costernavano? Comunque non è bello da parte tua mettere solo ora tutte queste informazioni!
Sono il cuoco della nazionale!

Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da Sonner » 13 giu 2011, 22:26

Bon ci provo (ho svolto il problema per n generico mentre il problema chiede solo n=2011, tanto è uguale).

Parte 1: con n scarpe Ciancica dura 2n-1 giorni di lavoro.
Dimostrazione: per induzione su n. n=1 è banale, suppongo che la tesi valga per tutti i numeri da 1 a n-1 e la dimostro per n. Chiamo A il primo paio di scarpe che usa Ciancica e A-giorno un giorno in cui questo viene indossato.
Osservazione 1: A sarà indossato anche l'ultimo giorno (non può violare la seconda condizione e se non ci fosse la sequenza non sarebbe massima, visto che potrei sempre aggiungerlo).
Osservazione 2: dal momento che A compare almeno due volte, consideriamo la seconda volta in cui viene usato. Le scarpe nell'intervallo tra il primo e il secondo A-giorno non potranno essere usate all'infuori di quell'intervallo per la condizione, e così le scarpe tra l'i-esimo A-giorno e l'(i+1)-esimo.
Osservazione 3: in questi intervalli Ciancica indossa un numero di paia di scarpe minore di n (non usa A), quindi posso applicare l'ipotesi induttiva (e questo tra l'altro implica che gli A-giorni sono tutti giorni dispari) visto che per massimizzare la carriera con n scarpe devo necessariamente massimizzare l'intervallo (visto che sono tutti indipendenti).
Ora faccio il conto. Chiamo $k_i$ (con $1\geq i\geq a-1$ dove a è il numero di A-giorni) il numero di scarpe usate (contandole una sola volta) nell'i-esimo intervallo (nota: gli intervalli sono chiaramente a-1 e non a), quindi $\sum_{i=1}^{a-1} k_i=n-1$. Applicando l'ipotesi induttiva ottengo che la lunghezza totale degli intervalli è $\sum_{i=1}^{a-1} 2k_i-1=2(\sum_{i=1}^{a-1}k_i)-n+1=2n-a-1$ a cui devo aggiungere ancora gli a A-giorni per ottenere la tesi.

Parte 2: ci sono $C_{n-1}\cdot n!$ modi di raggiungere il massimo, dove $C_m$ è l'm-esimo numero di Catalan ($C_0=C_1=1, C_2=2, C_3=5$ e così via.
Dimostrazione: per ricorrenza. Sia $D_n$ il numero di disposizioni con n scarpe. Divido la carriera in 2 blocchi: il primo intervallo (tra A-giorno 1 e A-giorno 2) e "tutto il resto", fisso la lunghezza 2l-1 del primo intervallo. Allora ho $D_l\cdot D_{n-l}$ modi di disporre le scarpe (infatti il primo intervallo e l'ntervallo "tutto il resto" sono indipendenti e basta togliere le prime 2l-2 giornate per accorgersene). Sommando al variare di l ottengo: $D_n=\sum_{l=1}^{n-1}=D_l\cdot D_{n-1-l}$. Questo insieme alla verifica dei primi casi $D_1=D_2=1, D_3=5, D_4=14,\dots$ basta a dimostrare che $D_n=C_{n-1}$. Non resta che moltiplicare per $n!$ per ottenere tutti gli ordinamenti possibili delle scarpe. Scritta da cani ma tant'è :D
Ultima modifica di Sonner il 14 giu 2011, 08:34, modificato 1 volta in totale.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: 24. Ciancica: la donna in carriera (staffetta)

Messaggio da dario2994 » 14 giu 2011, 08:33

Sonner ha scritto:Bon ci provo (ho svolto il problema per n generico mentre il problema chiede solo n=2011, tanto è uguale).

Parte 1: con n scarpe Ciancica dura 2n-1 giorni di lavoro.
Dimostrazione: per induzione su n. n=1 è banale, suppongo che la tesi valga per tutti i numeri da 1 a n-1 e la dimostro per n. Chiamo A il primo paio di scarpe che usa Ciancica e A-giorno un giorno in cui questo viene indossato.
Osservazione 1: A sarà indossato anche l'ultimo giorno (non può violare la seconda condizione e se non ci fosse la sequenza non sarebbe massima, visto che potrei sempre aggiungerlo).
Osservazione 2: dal momento che A compare almeno due volte, consideriamo la seconda volta in cui viene usato. Le scarpe nell'intervallo tra il primo e il secondo A-giorno non potranno essere usate all'infuori di quell'intervallo per la condizione, e così le scarpe tra l'i-esimo A-giorno e l'(i+1)-esimo.
Osservazione 3: in questi intervalli Ciancica indossa un numero di paia di scarpe minore di n (non usa A), quindi posso applicare l'ipotesi induttiva (e questo tra l'altro implica che gli A-giorni sono tutti giorni dispari) visto che per massimizzare la carriera con n scarpe devo necessariamente massimizzare l'intervallo (visto che sono tutti indipendenti).
Ora faccio il conto. Chiamo $k_i$ (con $1\geq i\geq a-1$ dove a è il numero di A-giorni) il numero di scarpe usate (contandole una sola volta) nell'i-esimo intervallo (nota: gli intervalli sono chiaramente a-1 e non a), quindi $\sum_{i=1}^{a-1} k_i=n-1$. Applicando l'ipotesi induttiva ottengo che la lunghezza totale degli intervalli è $\sum_{i=1}^{a-1} 2k_i-1=2(\sum_{i=1}^{a-1}k_i)-n+1=2n-a-1$ a cui devo aggiungere ancora gli a A-giorni per ottenere la tesi.

Parte 2: ci sono $C_{n-1}\cdot n!$ modi di raggiungere il massimo, dove $C_m$ è l'm-esimo numero di Catalan ($C_0=C_1=1, C_2=2, C_3=5$ e così via.
Dimostrazione: per ricorrenza. Sia $D_n$ il numero di disposizioni con n scarpe. Divido la carriera in 2 blocchi: il primo intervallo (tra A-giorno 1 e A-giorno 2), fisso la lunghezza 2l-1 del primo intervallo. Allora ho $D_l\cdot D_{n-l}$ modi di disporre le scarpe (infatti il primo intervallo e l'ntervallo "tutto il resto" sono indipendenti e basta togliere le prime 2l-2 giornate per accorgersene). Sommando al variare di l ottengo: $D_n=\sum_{l=1}^{n-1}=D_l\cdot D_{n-1-l}$. Questo insieme alla verifica dei primi casi $D_1=D_2=1, D_3=5, D_4=14,\dots$ basta a dimostrare che $D_n=C_{n-1}$. Non resta che moltiplicare per $n!$ per ottenere tutti gli ordinamenti possibili delle scarpe. Scritta da cani ma tant'è :D
Le idee ci sono tutte ed è anche abbastanza chiara :) (ci sono vari typo e sviste ma nulla di grave ;) )
Certo sul finale prova a trovare una formula bella, che esiste, per $C_{n-1}\cdot n!$ (non ho controllato che gli indici siano giusti, mi fido :D )
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Rispondi