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?
Problema 15 semifinale A 2007
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Problema 15 semifinale A 2007
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.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
Re: Problema 15 semifinale A 2007
non vorrei fare una domanda stupida, ma perché il risultato cercato è $ p(1)-1 $?
Re: Problema 15 semifinale A 2007
$p(1)$ è la somma algebrica dei coefficenti del polinomio.EDG93 ha scritto:non vorrei fare una domanda stupida, ma perché il risultato cercato è $ p(1)-1 $?
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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Problema 15 semifinale A 2007
capito! grazie, non ci sarei mai e poi mai arrivato