coefficiente di x^2006

[mod_2]

(non so se è veramente combinatoria, e quindi chiedo scusa se sbaglio la sezione...)

$ $(1+x)^2(1+x^2)(1+x^4)(1+x^8)^3(1+x^{16}) $$ $(1+x^{32})^4(1+x^{64})(1+x^{128})(1+x^{256})(1+x^{512})(1+x^{1024}) $

Trovare il coefficiente del termine $ $x^{2006} $ del polinomio

GARA NAZIONALE A SQUADRE 2006

[Agi_90]

la soluzione non è delle migliori, ma in mancanza di altro ( )

be' pensiamo un po' a come potrebbero essere fatti i termini di quel mostro: ogni termine sarà il prodotto di un termine da ogni parentesi, tutte le possibili scelte faranno tutti i termini, ovviamente poi potremo sommare quelli simili, noi vogliamo quelli in cui compare la x^2006. Dopo aver sviluppato le potenze notiamo che i termini in x^1024, x^512, x^256 e almeno uno dei due termini in x^128, dovrà essere preso per forza (moltiplicando infatti tutti i termini con esponente massimo nelle altre parentesi non riusciamo a raggiungere x^2006). Bene li eliminiamo momentaneamente e consideriamo che dobbiamo raggiungere 2006 - 1024 - 512 - 256 - 128 = 86. Ottimo, ma questo non è un grande problema:

$ (1+2x+x^2)(1+x^2)(1+x^4)(1+3x^8+3x^{16} $$ +x^{24})(1+x^{16})(x^{128}+4x^{96} $$ +6x^{64}+4x^{32}+1)(1+x^{64})(1+x^{128}) $

consideriamo di prendere il primo x^128 da destra. Possiamo ottenere x^86 con:
$ x^{128}\cdot x^{64}\cdot 3x^{16} \cdot x^4 \cdot x^2 $ (per 2 visto che ci sono due x^2)
$ x^{128}\cdot 6x^{64}\cdot 3x^{16} \cdot x^4\cdot x^2 $ (sempre per 2)
$ x^{128}\cdot 6x^{64}\cdot x^{16} \cdot x^4 \cdot x^2 $ (per 2)
$ x^{128}\cdot x^{64}\cdot 3x^{16} \cdot x^4 \cdot x^2 $ (indovinate? per dueXD)

e poi considerando il secondo x^128:

$ x^{128}\cdot x^{64}\cdot x^{16} \cdot x^4 \cdot x^2 $ (al solito per due)
$ x^{128}\cdot x^{64}\cdot 3x^{16} \cdot x^4 \cdot x^2 $ (sempre per dueXD)

in totale saranno: $ (6+36+12+2+2+6)x^{2006} = 64x^{2006} $

p.s. il bello è che il mostro di sopra contiene tutte le potenze di x da x^0 a x^2160 avendo per ogni termine x^0 + x^{2^k}, insomma fatto apposta per essere sviluppato

[darkcrystal]

Soluzione più semplice: raccolgo $ q(x)=(1+x)(1+x^8)^2(1+x^{32})^3 $. Quello che resta, lo moltiplico e divido per $ (1-x) $ e scopro che viene (perchè?) $ p(x)=\frac{1-x^{2048}}{1-x}=1+x+...+x^{2047} $.
Allora, dato che in questo ultimo polinomio TUTTI i termini compaiono con coefficiente 1, e ci sono TUTTI gli esponenti, ogni termine nell'espansione di q(x) potrà essere associato ad un termine nell'espansione di p(x) in modo che il prodotto abbia esponente 2006, e il coefficiente sia lo stesso del termine preso da q(x). Ma allora si tratta solo di contare qual è la somma dei coefficienti di q(x), cioè q(1)! E infatti $ q(1)=2 \cdot 2^2 \cdot 2^3 =2^6=64 $.

Ciao!

[mod_2]

Bella la soluzione!

Soluzione più semplice: raccolgo $ q(x)=(1+x)(1+x^8)^2(1+x^{32})^3 $. Quello che resta, lo moltiplico e divido per $ (1-x) $ e scopro che viene (perchè?) $ p(x)=\frac{1-x^{2048}}{1-x}=1+x+...+x^{2047} $.

Sfrutto questa famosa identità algebrica: $ $(a+b)(a-b)=a^2-b^2 $

Moltiplicando $ $1-x $ per la seguente robaccia
$ $(1+x)(1+x^2)(1+x^4)(1+x^8)(1+x^{16})(1+x^{32})(1+x^{64}) $$ $(1+x^{128})(1+x^{256})(1+x^{512})(1+x^{1024}) $

si ottiene

$ $(1-x^2)(1+x^2)... $
$ $(1-x^4)(1+x^4)... $
ecc...
$ $(1-x^{1024})(1+x^{1024})=1-x^{2048} $

Facendo ora la divisione $ $\frac{1-x^{2048}}{1-x} $ si nota che viene generato ogni termine di $ $x^{2047}+x^{2046}+...+x+1 $

così?

[darkcrystal]

Si, esatto! Ogni tanto infilo dei "perchè" nelle soluzioni solo per controllare che la gente segua sul serio, in realtà