31- Tante caramelle

[mat94]

Sia $n$ un numero naturale. Ci sono $n$ ragazzi e $n$ ragazze su una linea in un ordine qualsiasi. Un ragazzo/a $X$ può ricevere $m$ caramelle se si possono scegliere due ragazzi di sesso opposto ad $X$ che si trovano su entrambi i lati di $X$ in $m$ modi. Dimostrare che il numero totale di caramelle non supera $n(n^2-1)/3$.

[Troleito br00tal]

che si trovano su entrambi i lati di $X$

Scusami, puoi spiegarti meglio? Devono stare ognuno su un lato o entrambi sullo stesso? Grazie

[mat94]

Faccio un esempio: se ho MF... (M maschio e F femmina), ho che M ha 0 caramelle, F $1\cdot (n-1)$ caramelle.
Devi prendere un ragazzo di sesso opoosto a X da entrambi i lati, cioè uno a destra e uno a sinistra.

[Troleito br00tal]

Ok grazie ora è tutto ben chiaro

[Mist]

Dimostro anzitutto che la disposizione che richiede il massimo numero di caramelle è "a maschi e femmine alternati", ovvero MFMF... .
Assumo $n$ pari. La fila si apra WLOG con un maschio M. Divido ora l'$n-$esimo bambino (F) dall' $n+1-$esimo (M) con un muretto. Basterà contare, ora, quante caramelle verranno date ai bambini a sinistra del muretto e moltiplicarlo per due (per simmetria) per conoscere il numero totale delle caramelle date ai bambini. è quindi facile osservare che il numero totale di caramelle distribuite nel caso considerato sarà $\displaystyle 2\left[ \left( 2\sum_{j=1}^{\frac{n}{2}} j(n-j) \right) -\left( \frac{n}{2} \right)^2 \right] = 2\left( 2n\sum_{j=1}^{\frac{n}{2}}j - 2\sum_{j=1}^{\frac{n}{2}} j^2 - \left( \frac{n}{2} \right)^2 \right) = 2\left( \frac{n^2(n+2)}{4} -\frac{n(n+1)(n+2)}{3\cdot 4} -\left( \frac{n}{2} \right) ^2 \right) =\frac{n^3-n}{3}$.
Per $n$ dispari si calcola analogamente che il numero totale delle caramelle distribuite nel caso "maschi femmine alternati è pari a $\displaystyle 4\sum_{j=1}^{\frac{n-1}{2}}j(n-j) = \frac{n(n^2-1)}{3}$ (risparmiatemi dallo scrivere i conti anche di questo caso, vi prego).
Si verificano facilmente a mano che i casi $n=2$, $n=3$ e $n=4$ soddisfano la tesi. Sia vero che il numero massimo di caramelle viene distribuito in caso di alternanza maschi-femmine per un $n$ pari. Divido gli $n$ bambini a sinistra del muretto di cui si parlava sopra in $\displaystyle \frac{n}{2}$ coppie MF (la fila si apre sempre WLOG con un mschietto). Cerchiamo ora la posizione $p$ tra il $p-$esimo ed il $p+1-$esimo blocchetto in cui inserire un maschietto in modo tale da ottenere il numero massimo di caramelle. Ovviamente $p$ varia tra $1$ e $\frac{n}{2}$. Il numero di caramelle date alle fanciulle a destra del muretto è indipendente dalla posizione del nuovo maschio. Il numero di caramelle da dare alle femminucce a sinistra del muretto dipende soltanto dalla posizione del nuovo maschio ed è pari a $\displaystyle \sum_{j=1}^{p}j(n-j+1) + \sum_{j=p+1}^{\frac{n}{2}}(j+1)(n-j)$ che, fatti i conti ed eliminate le costanti, ci si acccorge che varia come $p^2-p$ e che quindi assume il suo valore massimo quando $p$ è massimo, ovvero $\frac{n}{2}$. Volendo aggiungere una bambina nel blocco di sinistra anzichè un bambino, si ricaverà che la posizione che massimizza le caramelle sarà $p=0$ e quindi la tesi sarà comunque dimostrato. Si è quindi dimostrato che se la configurazione con $2n$ bambini con $n$ pari raggiunge il suo massimo mettendo maschi e femmine alternati, allora la configurazione con $2n+2$ bambini raggiunge anch'essa la massima richiesta di caramelle quando i bambini sono alternati.
Consideriamo ora il caso in cui la tesi sia vera per un $n$ dispari, la fila si apra sempre a sinistra WLOG con un maschietto e si cerchi la posizione ottimale dove mettere nel blocco di sinistra un altro maschietto. Siccome il numero di maschi presenti a sinistra è ininfluente, i conti sono uguali a quelli del caso "$n$ pari" e si ottiene quindi che la posizione ottimale per il maschietto è all'estrema destra del blocco di sinistra, ovvero attaccato al muretto. Analogamente, nel blocco di destra la bambina nuova andrà accanto al muretto. Si verifica banalmente che invertendo il maschio e la femmina che sono attaccate al muretto, il numero totale di caramelle aumenta e quindi si ha ancora che se il massimo numero di caramelle è raggiunto per $n$ dispari a maschi e femmine alternati, allora per $n$ pari il massimo delle caramelle è raggiunto a maschi e femmine alternati. ma si è dimostrato sopra che una configurazione a maschi e femmine alternati richiese sempre e comunque $\displaystyle \frac{n(n^2-1)}{3}$ caramelle, da cui la tesi.

Che casino Spero si capisca...

[mat94]

Sei sicuro che il primo conto venga $\frac{n^3-n}{3}$?

[Mist]

Sìsì, mi ero dimenticato di ricopiare un $\displaystyle \frac{n^2}{4}$, ho editato, guarda ora se il resto funziona

[mat94]

Si dovrebbe funzionare vai pure con il prossimo