Problema 15 semifinale A 2007

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
EDG93
Messaggi: 25
Iscritto il: 10 mag 2011, 21:31
Località: Copernico Udine

Problema 15 semifinale A 2007

Messaggio da EDG93 » 06 apr 2012, 11:53

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? :)

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: Problema 15 semifinale A 2007

Messaggio da Karl Zsigmondy » 06 apr 2012, 13:39

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!"

EDG93
Messaggi: 25
Iscritto il: 10 mag 2011, 21:31
Località: Copernico Udine

Re: Problema 15 semifinale A 2007

Messaggio da EDG93 » 06 apr 2012, 14:54

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

Avatar utente
Drago96
Messaggi: 1142
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Problema 15 semifinale A 2007

Messaggio da Drago96 » 06 apr 2012, 15:06

EDG93 ha scritto:non vorrei fare una domanda stupida, ma perché il risultato cercato è $ p(1)-1 $? :roll:
$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... :D
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

EDG93
Messaggi: 25
Iscritto il: 10 mag 2011, 21:31
Località: Copernico Udine

Re: Problema 15 semifinale A 2007

Messaggio da EDG93 » 06 apr 2012, 15:13

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

Rispondi