Maratona di problemi 2
[xdom="Fioravante Patrone"]Ricopio qui quanto detto da elgiovo, che aveva sollevato il problema di questo thread (io ho "retrodatato" la divisione fra prima e seconda parte per comodità di accesso al database):
Questo thread è la continuazione di "Maratona di problemi", che avendo raggiunto 50 pagine non può più contenere post.[/xdom]
Questo thread è la continuazione di "Maratona di problemi", che avendo raggiunto 50 pagine non può più contenere post.[/xdom]
Risposte
Ripropongo un problema che già proposi ma che è rimasto insoluto.
Dimostrare che
$1/(n+1)2^(n*H(k/n))<=((n),(k))$
dove $H(.)$ è l'entropia binaria:
$H(x)=-xlog_2x-(1-x)log_2(1-x)$
Dimostrare che
$1/(n+1)2^(n*H(k/n))<=((n),(k))$
dove $H(.)$ è l'entropia binaria:
$H(x)=-xlog_2x-(1-x)log_2(1-x)$
Bloccare una maratona del genere per oltre un anno ( e non mi pare l'unica su questo forum) mi pare un po' ridicolo. Personalmente proporrei, come per le staffette dell'(ormai defunto?) Oliforum, che chi propone il problema posti la soluzione entro al massimo una settimana se non viene ricevuta alcuna risposta.
Comunque, sono sempre stato contro i messaggi inutili. La soluzione al problema precedente l'ho postata sul mio blog all'indirizzo http://bboyjordan.wordpress.com/2010/07 ... blems-2nd/ (vedi problema 16). Ho anche dimostrato una formula asintotica per $((2n),(n))$ (basta osservare che $\frac{x_{n+1}}{x_n}\to 1$), ricordando il prodotto di Wallis. Aspetto conferme dal moderatore.
Comunque, sono sempre stato contro i messaggi inutili. La soluzione al problema precedente l'ho postata sul mio blog all'indirizzo http://bboyjordan.wordpress.com/2010/07 ... blems-2nd/ (vedi problema 16). Ho anche dimostrato una formula asintotica per $((2n),(n))$ (basta osservare che $\frac{x_{n+1}}{x_n}\to 1$), ricordando il prodotto di Wallis. Aspetto conferme dal moderatore.
"bboypa":Forse più che di ridicolaggine si tratta di perdita d'interesse. Succede. Ce ne faremo una ragione. D'altronde questo forum è veramente pieno di difetti. Sarà per questo che sopravvive.
Bloccare una maratona del genere per oltre un anno ( e non mi pare l'unica su questo forum) mi pare un po' ridicolo.
Ok, visto che nessuno conferma o meno la correttezza della soluzione, vado avanti.
Siano a,b,c tre interi fissati tali che MCD(a,b)=1 e min{a,b+1,c}>1. Dimostrare che esiste un intero n>b tale che $a^n-b$ ha almeno $c$ divisori primi distinti.
Siano a,b,c tre interi fissati tali che MCD(a,b)=1 e min{a,b+1,c}>1. Dimostrare che esiste un intero n>b tale che $a^n-b$ ha almeno $c$ divisori primi distinti.
"bboypa":
La soluzione al problema precedente l'ho postata sul mio blog all'indirizzo http://bboyjordan.wordpress.com/2010/07 ... blems-2nd/ (vedi problema 16).
C'è un modo (molto) più semplice, secondo me, per arrivare a dimostrare il bound.
Consideriamo una variabile aleatoria binomiale [tex]B[/tex] con parametri [tex]n[/tex] e [tex]p[/tex]. E' ben noto che il valore più probabile per [tex]B[/tex] è [tex]np[/tex], dunque si può scrivere
[tex]1=\sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k}\le (n+1)\max_k \binom{n}{k} p^k (1-p)^{n-k}[/tex]
[tex]=(n+1)\binom{n}{np} p^{np} (1-p)^{n-np}[/tex].
In particolare, prendendo [tex]p=\frac{k}{n}[/tex] si ha
[tex]1\le (n+1)\binom{n}{k} (\frac{k}{n})^{k} (1-\frac{k}{n})^{n-k}[/tex]
che può essere riscritta come
[tex]\frac{1}{n+1}2^{n\cdot H(k/n)}\le \binom{n}{k}[/tex]
Si, hai ragione, ma procedendo abbastanza per "fatti noti" la mia è la prima dimostrazione che mi è venuta in mente, in più volendo dimostra un bound asintoticamente migliore..
Comunque, qualcuno che risolve il mio?
Comunque, qualcuno che risolve il mio?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo