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