
11) Carlo ha sei mele e sei pere: in quanti modi può mettere in fila 6 frutti, in modo tale che tra due mele non ci sia mai nessuna pera?
(A) 16
(B) 22
(C) 32
(D) 35
(E) 39

11. La risposta è $\mathbf{( B )}$.

Rappresentiamo una generica disposizione di 6 frutti con una sequenza di 6 lettere, ciascuna delle quali può essere una $P$ (pera) o una $M$ (mela). Vogliamo contare le sequenze in cui tra due $M$ non ci sia nessuna $P$; per comodità chiamiamo queste sequenze accettabili. Come regola generale, una sequenza è accettabile se tutte le $M$ in essa contenute sono adiacenti l'una all'altra, cioè consecutive; questa osservazione rende più facile contare le sequenze accettabili perché in una sequenza accettabile la posizione delle $M$ è univocamente determinata una volta che si sia individuata la prima $M$ (quella più a sinistra) e il numero complessivo di $M$ presenti nella sequenza. Utilizzando questo fatto scriviamo allora le possibili sequenze in base al numero di $M$ che esse contengono, partendo dal valore massimo in cui ci sono $6 M$ (ovvero i 6 frutti sono tutte mele), fino a quello minimo in cui non c'è nessuna $M$ :

- se ci sono $6 M$ si ha 1 sequenza accettabile:

$$
M M M M M M \text {. }
$$

- se ci sono $5 M$ si hanno 2 sequenze accettabili:

$$
M M M M M P, \quad P M M M M M \text {. }
$$

- se ci sono $4 M$ si hanno 3 sequenze accettabili:

$$
M M M M P P, \quad P M M M M P, \quad P P M M M M
$$

- se ci sono $3 M$ si hanno 4 sequenze accettabili:

$$
M M M P P P, P M M M P P, P P M M M P, P P P M M M \text {. }
$$

- se ci sono $2 M$ si hanno 5 sequenze accettabili:

$$
M M P P P P, P M M P P P, P P M M P P, P P P M M P, P P P P M M \text {. }
$$

- se c'è una sola $M$ si hanno 6 sequenze accettabili:

$$
M P P P P P, P M P P P P, P P M P P P, P P P M P P, P P P P M P, P P P P P M \text {. }
$$

- infine, l'unica sequenza senza $M$ è accettabile:

$$
P P P P P P \text {. }
$$

In tutto abbiamo allora $1+2+3+4+5+6+1=22$ sequenze accettabili.

[Problema proposto da P. Leonetti.]
