SNS 2008/2009 problema 4

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Algebert
Messaggi: 330
Iscritto il: 31 lug 2008, 20:09
Località: Carrara
Contatta:

SNS 2008/2009 problema 4

Messaggio da Algebert » 03 set 2008, 14:21

Raccolgo l'appello di EvaristeG e posto nelle loro apposite sezioni i rimanenti problemi di ammissione alla Normale di quest'anno, in modo che si possano discutere separatamente. Questo è il quarto (e, a mio avviso, forse il più semplice):

"30 scienziati sono invitati a un festival. Essi provengono da 6 città diverse, e ognuna di esse manda 5 scienziati. Gli organizzatori del festival dispongono di 6 tavoli da 5 posti ciascuno, e decidono di disporre i vari invitati in modo tale che in ogni tavolo non ci siano due scienziati della stessa città. In quanti modi è possibile fare questa cosa? L'ordine con cui gli scienziati si siedono ai tavoli non conta, mentre invece i tavoli sono da considerarsi distinti l'uno dall'altro."


P.S:
qualcuno non potrebbe prendersi la briga di postare in questa sezione il testo (approssimativamente) esatto del terzo problema, se se lo ricorda? Io me lo sono quasi del tutto dimenticato :oops: , e ovviamente quello di supergrane non è corretto.
"[i]What is a good Olympiad problem?[/i] Its solution should not require any prerequisites except cleverness. A high scool student should not be at a disadvantage compared to a professional mathematician."

Avatar utente
invuniros
Messaggi: 17
Iscritto il: 30 ago 2008, 10:45

Messaggio da invuniros » 03 set 2008, 14:40

Premetto di saperne veramente poco in materia perciò probabilmente scriverò una sciocchezza. Da ignorante comunque ho pensato questo:

(5!*6)^6
Tutti sanno che una cosa è impossibile da realizzare finché arriva uno sprovveduto che non lo sa e la inventa

fph
Site Admin
Messaggi: 3665
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: SNS 2008/2009 problema 4

Messaggio da fph » 03 set 2008, 14:50

Algebert ha scritto: qualcuno non potrebbe prendersi la briga di postare in questa sezione il testo (approssimativamente) esatto del terzo problema, se se lo ricorda? Io me lo sono quasi del tutto dimenticato :oops: , e ovviamente quello di supergrane non è corretto.
In effetti si è dimenticato di specificare che i quadretti devono essere di 1 cm di lato.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
dado91
Messaggi: 19
Iscritto il: 25 ott 2007, 21:14

Messaggio da dado91 » 03 set 2008, 15:24

invuniros ha scritto:Premetto di saperne veramente poco in materia perciò probabilmente scriverò una sciocchezza. Da ignorante comunque ho pensato questo:

(5!*6)^6
Forse sbaglierò io,ma non è solo $ 5!*6 $ ? :?
"Tutti sanno che una cosa è impossibile da realizzare,poi arriva uno sprovveduto che non lo sa e la inventa" A.Einstein

Avatar utente
invuniros
Messaggi: 17
Iscritto il: 30 ago 2008, 10:45

Messaggio da invuniros » 03 set 2008, 15:38

dado91 ha scritto:
Forse sbaglierò io,ma non è solo $ 5!*6 $ ? :?
In questo modo però ti calcoli le possibili disposizioni dei rappresentanti di una sola città, senza considerare le altre (almeno credo :?)
Tutti sanno che una cosa è impossibile da realizzare finché arriva uno sprovveduto che non lo sa e la inventa

L'ale
Messaggi: 49
Iscritto il: 14 set 2007, 13:10
Località: Pistoia

Messaggio da L'ale » 03 set 2008, 15:50

Dunque: i tavoli sono 6, in ogni tavolo ci stanno 5 persone che non si conoscono.
Chiamiamo A1,A2,A3,A4,A5,A6 i 6 rappresentanti della città A.

Partendo nella collocazione delle persone di A nei tavoli, A1 lo posso collocare in 6 modi, A2 in 5, A3 in 4, e così via, dunque i rappresentanti della città A possono esser collocati in 6*5*4*3*2*1 modi.
Siccome le città sono 6, per ognuna si deve ripetere questo schema.
Perciò la soluzione dovrebbe essere:

6^6 * 5^6 * 4^6 * 3^6 * 2^6 * 1*6.

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 03 set 2008, 15:53

Sembra fatto apposta per farti fare confusione... cmq io direi che si può fare così. Ogni città ha un tavolo senza scienziati, quale città non siede a quale tavolo si può scegliere in $ $6! $ modi. A questo punto ogni città ha $ $5 $ scienziati che può disporre in $ $5 $ tavoli in $ $5! $ modi, per $ $6 $ città $ $5!^6 $. Quindi direi $ $6!\cdot5!^6 $
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Whov
Messaggi: 23
Iscritto il: 20 ago 2014, 12:40

Re: SNS 2008/2009 problema 4

Messaggio da Whov » 25 mag 2015, 22:12

Ciao, scusate se dopo tanto tempo che non scrivo torno qui (per di più a riesumare un thread vecchissimo..), ma sto affrontando i vecchi problemi di ammissione alla normale (immaginerete perché). Non mi tornano le soluzioni qui sopra, quindi volevo provare a postare quello che ho trovato io. Anzitutto chiamo per comodità i trenta scienziati A1,A2,A3,A4,A5 con le lettere da A a F (6 città, 5 scienziati per ogni città). Distinguo ora i tavoli:
Tavolo 1: scelgo 5 città dalle 6 e da ognuna 1 persona fra 5 $ \dbinom{6}{5} * 5^5 $. Fingo (solo per intendersi meglio in seguito), di aver messo ogni città tranne F
Tavolo 2: Se qui escludo le persone da F allora avrò poi 5 persone da sistemare in 6-2=4 tavoli, per cui per il principio dei cassetti un tavolo avrà 2 persone. Allora in questo tavolo devo includere un F. Scelgo ora le restanti 4 città; dalla città F ho poi 6 persone, mentre dalle altre 4 ne scelgo uno fra 4 $ \dbinom{5}{4} * 6 * 4^4 $. Suppongo di aver inserito le città BCDEF e di aver escluso A.
Tavolo 3: Avendo escluso A prima sono ora costretto a inserirlo (come sopra), e così pure F. Allora scelgo le persone da A e F fra 4, mentre dalle altre città fra 3. $ \dbinom{4}{3} * 4^2 * 3^3 $. Escludo E.
Tavolo 4: Continuo così. Ora ho fissati A,E,F (a cui ne restano 3 ciascuno), mentre B,C,D ne hanno ancora 2. $ \dbinom{3}{2} * 3^3 * 2^2 $. Escludo B.
Tavolo 5: Metto A,B,E,F che ne hanno 2 ciascuno. C,D ne rimangono 1 (gli altri sono nei tavoli 1,2,3,4). $ \dbinom{2}{1} * 2^4 * 1 $
Tavolo 6: è determinato univocamente..

Perciò le possibilità sono i prodotti delle espressioni in latex sopra.. Sto considerando l'ordine dei tavoli (ovviamente, li ho numerati), e sono abbastanza certo di non stare considerando l'ordine delle persone al tavolo, dopotutto le potenze nelle espressioni mi rappresentano possibili insiemi di persone, non n-uple.
Grazie a chiunque ci dia un'occhiata!!

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: SNS 2008/2009 problema 4

Messaggio da Enigmatico » 26 mag 2015, 22:45

Ragazzi, io non sono un drago in combinatoria, ma penso che il problema vada risolto così:

Si denominino i tavoli con i numeri da $1$ a $6$ e le città con le lettere da $A$ a $F$.
Per semplificare l'analisi del problema si inizi considerando il tavolo 1, dove il numero degli scienziati che vi prenderà posto sarà dato da $6 \choose 5$ modi di scegliere le $5$ città per $5^{5}$ modi di scegliere uno scienziato su cinque.
Ora, si noti che dal primo tavolo rimane esclusa una città, pertanto, se essa rimanesse esclusa anche dal secondo tavolo, essendo $5$ gli scienziati e $4$ i tavoli in cui questi potrebbero trovare posto, non si otterrebbe una configurazione accettabile (pidgeonhole).
Pertanto, si possono considerare sistemati gli scienziati della sesta città, che per comodità si chiamerà $F$, uno per tavolo rimasto libero, in $5!$ modi.
Si consideri, ora, il tavolo $2$; esso può essere riempito in $5 \choose 4$ modi di scegliere la città e $4^{4}$ di scegliere gli scienziati.
Una città, che si chiamerà $E$, è rimasta esclusa dal tavolo $2$, pertanto, si può ragionare come sopra e, per pigeonhole, affermare che questa deve avere uno scienziato in ognuno dei tavoli rimasti liberi, disposti in $4!$ modi.
Ragionando sempre alla stessa maniera si giunge all'analisi del tavolo $6$ che è obbligato.
Dunque, si può concludere che gli scienziati si possono sedere in $5! \cdot 4! \cdot 3! \cdot 2 \cdot {6 \choose 5} \cdot 5^{5} \cdot {5 \choose 4} \cdot 4^{4} \cdot {4 \choose 3} \cdot 3^{3} \cdot {3 \choose 2} \cdot 2^{2} \cdot {2 \choose 1}$.

P.S.: non ho ben capito la soluzione di Whov, me la potreste spiegare? non capisco perché lui si trova le potenze in più, mentre io vado avanti a fattoriali :?

Whov
Messaggi: 23
Iscritto il: 20 ago 2014, 12:40

Re: SNS 2008/2009 problema 4

Messaggio da Whov » 27 mag 2015, 12:43

Sai, le nostre soluzioni sono quasi equivalenti: in particolare io dovrei andare a letto alle 9, non alle 11..
Scelgo ora le restanti 4 città; dalla città F ho poi 6 persone
Ne ho 5 in verità...
Se aggiusti quello in effetti a me viene $ \binom{6}{5}*5^5 * \binom{5}{4} *4^4*5 * \binom{4}{3} *3^3*4^2 * \binom{3}{2} *2^2*3^3 * \binom{2}{1} *2^4 $. Riordinando cioé viene $ {6 \choose 5} \cdot 5^{5} \cdot {5 \choose 4} \cdot 4^{4} \cdot {4 \choose 3} \cdot 3^{3} \cdot {3 \choose 2} \cdot 2^{2} \cdot {2 \choose 1} * 5*4^2*3^3*2^4 $. La prima parte è come la tua. Gli ultimi fattori si possono riscrivere come $ 5!*4!*3!*2! $. Quindi ottimo!
Cerco ugualmente di spiegarti come mai funziona anche la mia: il tavolo 1 lo abbiamo fatto ugualmente. Per il secondo scegliamo entrambi quali città mettere dando per certo che F ci debba essere. Per le altre 4 lettere che metto ho 4 scienziati (4^4). Semplicemente io ora scelgo uno scienziato di F fra 5 e finisco il tavolo 2. Ora passo al terzo tavolo: devo mettere F e E (lettere come nella tua soluzione); ne restano da scegliere 3 fra 4 altre. Di queste 3 "altre" ho 3^3 possibilità per le persone (fin qui uguale). Adesso per completare il tavolo devo scegliere qualcuno da E e F. Ne restano 4 di persone disponibili, perciò 4^2.
In sintesi tu ordini le persone della città obbligata tutte in una volta nei tavoli restanti, io riempio un singolo tavolo alla volta.
In ogni caso emerge da me che i fattori sono del tipo $ \dbinom{n+1}{n} * n^n * (n+1)^(5-n) $, con n da 1 a 5, quindi anche se il tuo metodo è un po'più veloce per numeri più grandi anche con questo si arriva rapidamente a notare un fenomeno emergente e a sveltire la generalizzazione (eventuale). Grazie della conferma del risultato!

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: SNS 2008/2009 problema 4

Messaggio da Enigmatico » 27 mag 2015, 14:17

Grazie mille, ora ho capito tutto :D

Rispondi