Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
20/03/2004, 16:56
Navigando sulla rete mi sono imbattuto in
questo problema:
<b>Trovare il numero M dei coefficienti dispari
nello sviluppo polinomiale di (x+1)^n
(n intero positivo)</b>
Personalmente sono riuscito a trovare solo qualche
(insoddisfacente) risultato parziale ,calcolato
piu' che altro in modo euristico.Per es. sembra
che nel caso di n=2^k (k>0) risulti costantemente M=2
ed altri casi che non ho provato fino in fondo.
Forse la mia strategia e' sbagliata:
volete provare voi a trovare una soluzione completa ?
karl.
20/03/2004, 18:29
Auguri per i 500... <img src=icon_smile.gif border=0 align=middle>
20/03/2004, 18:57
Ringrazio sentitamente.
karl.
20/03/2004, 19:00
Mi sembra difficile poter dare una risposta con un n generico...
Confermo che nel caso di n = 2^k risulti costantemente M=2 e aggiungerei banalmente M=n per n = 2^k - 1, M = 4 per n = 2^k + 1 e così via...
21/03/2004, 11:39
Sono d'accordo, trovare una formula generale per n mi sembra arduo.
Per il momento mi accontento di un formula iterativa che ricostruisce il triangolo di Tartaglia a partire da n = 1 con la regola ovvia (P=pari, D=dispari) :
P + P = P
P + D = D
D + P = D
D + D = P
La formula può essere ottimizzata notando che si presentano tutti D quando n = 2^m-1 .
La formula è trasformabile in un semplicissimo programmino al computer per cui mi considero soddisfatto.
Naturalmente c'è di mezzo il "tempo macchina" che cresce al crescere di n , onde la soluzione non è il massimo dal punto di vista matematico, ma chi si accontenta ... gode.
Bye.
ps. poi l'analisi combinatoria non mi ha mai entusiasmato ...
23/03/2004, 20:46
Andando piu' che altro ad intuito e senza pretese
di verita' matematica,sarei giunto a questa conclusione:
Sia M il numero dei coeff. dispari ,risulta che:
<b>
M=2^k
essendo k il numero degli addendi che figurano nella scomposizione
di n nella somma di potenze del 2
</b>
Faccio qualche esempio:
0)n=7
n=2^2+2^1+2^0,k=3--->M=2^3=8
1)n=9
n=2^3+2^0,k=2---->M=2^2=4
2)n=11
n=2^3+2^1+2^0,k=3---->M=2^3=8
3)n=16
n=2^4,k=1----->M=2^1=2
In maniera piu' "scientifica" si potrebbe dire che k corrisponde
al numero delle cifre "1" che compaiono nella rappresentazione
binaria del numero n.
Forse si puo' tentare una dimostrazione per induzione completa:
ma come?
karl.
23/03/2004, 21:47
Geniale karl !!!
Ho verificato la tua formula al computer fino a n = 22. Poi ho dei problemi strani di conversione tipi dati per cui devo rifare il programma.
Direi a questo punto che la formula richiede solo una verifica rigorosa.
Bye.
Modificato da - arriama il 23/03/2004 21:59:29
Modificato da - arriama il 23/03/2004 23:18:19
24/03/2004, 09:29
Il computer conferma !!!
Mi sono spinto fino a n = 500 (crepi l'avarizia !).
Per la dimostrazione pensavo che potrebbe entrarci il fatto che le regole di composizione dei Pari e Dispari :
P + P = P
P + D = D
D + P = D
D + D = P
sono analoghe alla regola della somma in binario :
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
Però mi fermo qui ... preferisco le funzioni, integrali ecc.
Complimenti ancora per la brillante soluzione, karl.
Bye.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.