Questo esercizio era il primo del "Penta" proposto ieri a Caldè, nonché ultimo problema dell'edizione francese dei giochi della Bocconi.
E' molto meno contoso di quanto non sembri a prima vista, anche se ieri fior di concorrenti hanno fatto figure imbarazzanti nel tentare di risolverlo. A me la soluzione è balenata in mente mentre guidavo al ritorno.
Veniamo al problema.
Consideriamo i numeri da 1 a 36. Quante sono le sestine di numeri distinti che hanno almeno due numeri consecutivi? (Ad esempio {3,7,8,15,19,32}.)
Problema 1 del "Penta 2006"
-
Franchifis
- Messaggi: 149
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa
Cerchiamo i sottoinsiemi di 6 elementi che *non* contengono due numeri consecutivi.
Sottraendoli al totale dei sottoinsiemi di 6 elementi avremo il risultato.
Rappresentiamo i numeri da 1 a 36 con una 'stringa' di 36 simboli e indichiamo con 'X' i numeri che fanno parte del sottoinsieme, con 'o' gli altri.
Per essere sicuri che non ci siano due numeri consecutivi, partiamo da una stringa del tipo
... X o ... X o ... X o ... X o ... X o ... X ...
Ora aggiungiamo i 25 'o' che restano; possono andare in 7 posti diversi (dove ci sono i puntini), quindi lo possiamo fare in $ {25+7-1}\choose{7-1} $ modi (do' per nota la formula, eventualmente la dimostro).
Quindi il risultato è $ {36 \choose 6} - {31 \choose 6} = 1.211.511 $.
Sottraendoli al totale dei sottoinsiemi di 6 elementi avremo il risultato.
Rappresentiamo i numeri da 1 a 36 con una 'stringa' di 36 simboli e indichiamo con 'X' i numeri che fanno parte del sottoinsieme, con 'o' gli altri.
Per essere sicuri che non ci siano due numeri consecutivi, partiamo da una stringa del tipo
... X o ... X o ... X o ... X o ... X o ... X ...
Ora aggiungiamo i 25 'o' che restano; possono andare in 7 posti diversi (dove ci sono i puntini), quindi lo possiamo fare in $ {25+7-1}\choose{7-1} $ modi (do' per nota la formula, eventualmente la dimostro).
Quindi il risultato è $ {36 \choose 6} - {31 \choose 6} = 1.211.511 $.
-
MindFlyer
Propongo un'idea (CHI NON VUOLE SAPERE NIENTE NON LEGGA!!).
Contiamo le sestine del complementare, che sono quelle in cui non vi sono numeri consecutivi. Per farlo possiamo contare il numero di modi di scegliere i 7 "spazi" tra un numero e l'altro, col vincolo che il primo e l'ultimo spazio possono essere 0, tutti gli altri spazi devono essere almeno 1, e che la somma degli spazi sia 30. E questo è esattamente come contare il numero di sestine di un insieme 31 elementi.
In definitiva, la risposta è $ \displaystyle{{36}\choose{6}} - {{31}\choose{6}} $.
Contiamo le sestine del complementare, che sono quelle in cui non vi sono numeri consecutivi. Per farlo possiamo contare il numero di modi di scegliere i 7 "spazi" tra un numero e l'altro, col vincolo che il primo e l'ultimo spazio possono essere 0, tutti gli altri spazi devono essere almeno 1, e che la somma degli spazi sia 30. E questo è esattamente come contare il numero di sestine di un insieme 31 elementi.
In definitiva, la risposta è $ \displaystyle{{36}\choose{6}} - {{31}\choose{6}} $.
