Putnam 2007 A3
Putnam 2007 A3
Sia k un intero positivo, e si suponga che gli interi 1, 2, 3,... 3k+1 siano scritti in una lista in ordine casuale. Determinare, in funzione di k, la probabilità che la somma dei primi h numeri della lista non sia multipla di 3 per ogni h da 1 a 3k+1.
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]
Membro del fan club di Ippo_
Membro del fan club di Ippo_
Prima di tutto elimino i k multipli di 3 perchè non influiscono la congruenza mod 3 della somma dei primi h numeri, l'unica cosa importante è che nessuno di loro sia il primo della lista, cosa che vedrò alla fine.
Mi rimangono k+1 numeri $ $\equiv 1\pmod 3 $ e k numeri $ $\equiv 2\pmod 3 $. Banalmente vedo che devono essere disposti in uno di questi due ordini:
1121212...
2212121...
ma poichè ho più "1", il primo ordine è quello giusto.
Quindi la probabilità che siano ordinati in modo corretto è $ $\frac{(k+1)!\cdot k!}{(2k+1)!} $, che moltiplicata per la probabilità $ $\frac{2k+1}{3k+1} $ che il primo numero non sia multiplo di 3 dà $ $\frac{(k+1)!\cdot k!}{2k!\cdot(3k+1)} $
EDIT: a furia di mettere fattoriali li avevo messi anche dove non servivano!
Mi rimangono k+1 numeri $ $\equiv 1\pmod 3 $ e k numeri $ $\equiv 2\pmod 3 $. Banalmente vedo che devono essere disposti in uno di questi due ordini:
1121212...
2212121...
ma poichè ho più "1", il primo ordine è quello giusto.
Quindi la probabilità che siano ordinati in modo corretto è $ $\frac{(k+1)!\cdot k!}{(2k+1)!} $, che moltiplicata per la probabilità $ $\frac{2k+1}{3k+1} $ che il primo numero non sia multiplo di 3 dà $ $\frac{(k+1)!\cdot k!}{2k!\cdot(3k+1)} $
EDIT: a furia di mettere fattoriali li avevo messi anche dove non servivano!
Ultima modifica di julio14 il 09 feb 2008, 22:32, modificato 1 volta in totale.
Zoidberg ha scritto:Non posso far altro che confermare il risultato!
[edit: per la serie "cerco di evitare di postare messaggi inutili alla comunità": dico io..apparte la fortuna di aver indovinato il risultato per k=1 e k=2
come fate a moltiplicare tra loro due cose del genere?? poi, è un putnam... ribadisco in ogni caso il mo secondo post e anche il primo per chi volesse intendere]The only goal of science is the honor of the human spirit.
Secondo te non è giusto?Mr.Simpatia ha scritto:Zoidberg ha scritto:Non posso far altro che confermare il risultato!
[edit: per la serie "cerco di evitare di postare messaggi inutili alla comunità": dico io..apparte la fortuna di aver indovinato il risultato per k=1 e k=2
io non l'ho fatto come julio però il risultato mi viene lo stesso!
Se consideriamo i numeri con residui 1 e 2 mod 3 si nota che a parte una coppia di 1 iniziali poi devono per forza essere alternati.
I multipli di 3 poi posso metterli ovunque tranne che in pole position, quindi in $ {3k\choose k} $modi.
in ogni classe di resto l'ordine dei numeri è indifferente quindi i casi favorevoli sono $ (k+1)!k!k!{3k\choose k} $
divido per i casi possibili $ (3k+1)! $
Membro dell'associazione "Matematici per la messa al bando dell'associazione "Matematici per la messa al bando del Sudoku" fondata da fph" fondata da Zoidberg
le mie scuse a Zoidberg e Julio...da Mr.Simpatia 
Siccome non riuscivo a capire il come mettere quei multipli di 3 mi sono costruito la soluzione con il triangolo di Tartaglia..
praticamente veniva:
$ p=\displaystyle \frac{(k+1){(k!)}^3}{(3k+1)!} \sum_{i=0}^{k-1}{\binom{k-1}{i} \binom{2k+1}{i+1}} $
effettivamente esplicitando la sommatoria (credo) viene $ \binom{3k}{k} $ proprio per il modo in cui l'ho costruita, e la conclusione è la stessa ..
Siccome non riuscivo a capire il come mettere quei multipli di 3 mi sono costruito la soluzione con il triangolo di Tartaglia..
praticamente veniva:
$ p=\displaystyle \frac{(k+1){(k!)}^3}{(3k+1)!} \sum_{i=0}^{k-1}{\binom{k-1}{i} \binom{2k+1}{i+1}} $
effettivamente esplicitando la sommatoria (credo) viene $ \binom{3k}{k} $ proprio per il modo in cui l'ho costruita, e la conclusione è la stessa ..
The only goal of science is the honor of the human spirit.