Problema 15 semifinale A 2007

[EDG93]

Facendo problemi delle gare a squadre passate ho trovato questo problema che non ho idea di come fare...

Numeruto e` un esperto della tecnica superiore della moltiplicazione, un’arte magica che gli permette di ottenere istantaneamente il prodotto di un qualunque insieme di numeri interi. Il maestro Isoshilo gli ha pero` affidato un addestramento durissimo: considerati i numeri interi $ 2007, 2 · 2007, 3 · 2007, . . . , 2007^2 $ deve calcolare il prodotto di ogni sottoinsieme non vuoto dei numeri assegnati e sommarli tutti. Siete capaci di aiutarlo calcolando almeno le ultime 4 cifre del risultato?

Qualcuno mi potrebbe dare qualche suggerimento?

[Karl Zsigmondy]

Considero il polinomio $ p(x)=(x+2007 \cdot 1) \cdot (x + 2007 \cdot 2) \cdots (x+2007^2). $ Il risultato cercato è p(1)-1, ovvero $ (1+2007)(1+4014)(1+6021)\cdots(1+2007^2)-1 $ e dato che ci sono abbastanza fattori 5 e fattori 2, il risultato è 0000-0001=9999.

[EDG93]

non vorrei fare una domanda stupida, ma perché il risultato cercato è $ p(1)-1 $?

[Drago96]

non vorrei fare una domanda stupida, ma perché il risultato cercato è $ p(1)-1 $?

$p(1)$ è la somma algebrica dei coefficenti del polinomio.
Come immagino che tu sappia, in un polinomio monico di grado $n$, il termine di grado $n-1$ ha come coefficente la somma di tutte le radici; il termine di grado $n-2$ ha come coefficente la somma dei prodotti delle radici a due a due, ecc... (in realtà ci sarebbe la storia dei $-$, ma in quel polinomio si vede ad occhio che è tutto positivo, quindi in questo caso va bene così)
E quello che serve a noi sono tutti i sottoinsiemi non vuoti, ovvero la somma dei singoli elementi, i prodotti 2 a 2, quelli 3 a 3, ecc...
che come vedi sono proprio i coefficienti di quel polinomio.
Poi tolgo 1, perchè calcolando $p(1)$ considero anche il coefficente del termine di grado massimo, ovvero quello per cui non prendo nessun numero dall'insieme; e siccome è 1, lo tolgo per ottenere quello che serve a me...

[EDG93]

capito! grazie, non ci sarei mai e poi mai arrivato