OliForum Matematico

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 )

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

dario2994 ha scritto: allora nei giorni $a,b,c,d$ indossa sempre lo stesso paio di scarpe! (naturale esigenza di stile )

Non ho capito questa frase...cosa intendi con $a,b,c,d$?

paga92aren ha scritto:

dario2994 ha scritto: allora nei giorni $a,b,c,d$ indossa sempre lo stesso paio di scarpe! (naturale esigenza di stile )

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.

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

Se la soluzione è 2012! allora la posto.

EDIT: completamente cannato

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

Non ho capito bene la seconda condizione. Stai dicendo che non può mai alternare due paia di scarpe diverse?

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)

e in giorni consecutivi? lo puoi fare, in giorni consecutivi? o nno?

ileo83 ha scritto:e in giorni consecutivi? lo puoi fare, in giorni consecutivi? o nno?

No

e perche'? ma soprattutto, perche'?

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!

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!

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'è

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'è

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 )