Problema 1 del "Penta 2006"

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
teppic
Moderatore
Messaggi: 689
Iscritto il: 26 ago 2005, 09:50
Località: Parma
Contatta:

Problema 1 del "Penta 2006"

Messaggio da teppic » 31 lug 2006, 09:38

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}.)

Avatar utente
Franchifis
Messaggi: 149
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Franchifis » 31 lug 2006, 14:36

Non ho capito, vuoi il numero di insiemi di sei numeri di cui almeno due consecutivi, o le sestine ordinate di cui almeno due numeri successivi sono consecutivi?

Avatar utente
teppic
Moderatore
Messaggi: 689
Iscritto il: 26 ago 2005, 09:50
Località: Parma
Contatta:

Messaggio da teppic » 31 lug 2006, 14:57

Chiedo il numero di insiemi. Perché si capisse meglio, nell'esempio avevo messo le parentesi graffe e i numeri in ordine, ma ammetto che non era comunque molto chiaro.

Hammond
Messaggi: 110
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da Hammond » 31 lug 2006, 16:43

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 $.

MindFlyer

Messaggio da MindFlyer » 31 lug 2006, 16:45

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}} $.

MindFlyer

Messaggio da MindFlyer » 31 lug 2006, 16:47

Ops, hammond mi ha anticipato di 2 minuti!! :shock:

Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Messaggio da luca88 » 02 ago 2006, 18:26

per chi avesse letto l'engel c'è un esercizio uguale identico

Rispondi