Ancora archeologia – ValCon.It

Olimpiadi di Informatica – Gara nazionale a squadre 2001 – Numero 20

Grazie anche al vostro aiuto il sistema di numerazione della civilità Qwghlm è stato finalmente decifrato.
Ora potete apprezzare un altro problema trovato da alcuni valenti archeologi e tradotto nel nostro sistema decimale.

“Quali sono le ultime quattro cifre del coefficiente più grande in valore assoluto del polinomio

$(x-1)(x-2)(x-4)(x-8)(x-16)(x-32)(x-64)$ ?”

Passo 1

Lo sviluppo del prodotto

$(x-1)(x-2)(x-4)(x-8)(x-{16})(x-{32})(x-{64})$

= $[\ x^2-(1+2)\cdot x +1\cdot 2\ ] (x-4)(x-8)(x-{16})(x-{32})(x-{64})$

= $[\ x^3-(1+2+4)\cdot x^2 +(1\cdot 2+1\cdot 4+2\cdot 4)\cdot x-1\cdot 2\cdot 4\ ]$ $(x-8)(x-{16})(x-{32})(x-{64})$

= …

Passo 2

I valori assoluti dei coefficienti delle potenze di x

Passo 3

Il coefficiente più grande è 4.161.536
La soluzione del quesito è 1.536

$C_7$	…	= $1 \cdot 1 \dots \cdot 1$	= 1
$C_6$	La somma delle 7 radici	= $1+2+4+ 8+{16}+{32}+{64}$	= 127
$C_5$	La somma di tutti i prodotti (21) di 2 radici diverse	= $1\cdot 2+1\cdot 4+ \dots + {32}\cdot {64}$	= 5.334
$C_4$	La somma di tutti i prodotti (35) di 3 radici diverse	= …	= 94.488
$C_3$	La somma di tutti i prodotti (35) di 4 radici diverse	= …	= 755.904
$C_2$	La somma di tutti i prodotti (21) di 5 radici diverse	= …	= 2.731.008
$C_1$	La somma di tutti i prodotti (7) di 6 radici diverse	= $1\cdot 2\cdot 4\cdot 8\cdot {16}\cdot {32}$ + $1\cdot 2\cdot 4\cdot 8\cdot {16}\cdot {64}$ + $1\cdot 2\cdot 4\cdot 8\cdot {32}\cdot {64}$ + $1\cdot 2\cdot 4\cdot {16}\cdot {32}\cdot {64}$ + $1\cdot 2\cdot 8\cdot {16}\cdot {32}\cdot {64}$ + $1\cdot 4\cdot 8\cdot {16}\cdot {32}\cdot {64}$ + $2\cdot 4\cdot 8\cdot {16}\cdot {32}\cdot {64}$ = $2^{15}+2^{16}+2^{17}+2^{18}+2^{19}+2^{20}+2^{21}$	= 4.161.536
$C_0$	Il prodotto (1) delle 7 radici	= $1\cdot 2\cdot 4\cdot 8\cdot 16\cdot 32\cdot 64$ = $2^{21}$	= 2.097.152