Roba da smanettoni [SNS 2013/14 n. 5]

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
AlexThirty
Messaggi: 214
Iscritto il: 20 giu 2015, 20:58

Roba da smanettoni [SNS 2013/14 n. 5]

Messaggio da AlexThirty » 22 gen 2017, 17:04

Sia dato il polinomio $ f(x)=2x^2-7x+3 $. Trovare il polinomio $ g(x) $ tale per cui
  • $ g(0)=1 $
  • per ogni $ n $ le somme dei quadrati dei coefficienti di $ f(x)^n $ e $ g(x)^n $ sono uguali
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Roba da smanettoni [SNS 2013/14 n. 5]

Messaggio da Giovanni_98 » 25 gen 2017, 21:02

Bruttino questo...(sempre se risulta avere solo soluzioni contose come la mia, sperando che la mia sia una soluzione ahaha)
Testo nascosto:
Il (o un) polinomio che soddisfa (anche se non ho capito se il testo si riferisce ad esso specificando che sia unico o meno) è $g(x) = 6x^2 - 5x + 1$.

Prima di passare alla dimostrazione definiamo le matrici $a_{i,j}$ e $b_{i,j}$ tali che $f(x)^n = \sum_{i=0}^{2n} a_{n,i} x^i$ e $g(x)^n = \sum_{i=0}^{2n} b_{n,i} x^i$ per ogni $n$ intero positivo.

Poniamo per comodita' per ogni $n$ $a_{n,-2} = a_{n,-1} = a_{n,2n+1} = a_{n,2n+2} = 0$.

E' molto semplice notare ora che $a_{n+1,i} = 3a_{n,i} - 7a_{n,i-1} + 2a_{n,i-2}$ e che $b_{n+1,i} = b_{n,i} - 5b_{n,i-1} + 6b_{n,i-2}$ (*).

Dimostriamo ora innanzitutto che $\sum_{i=0}^{2n} a_{n,i}a_{n,i-j} = \sum_{i=0}^{2n} b_{n,i}b_{n,i-j}$per ogni $n \ge 1$ e per ogni $0 \leq j \leq i$ tramite il principio di induzione.

Passo base : $n=1$. Trivial.

Passo induttivo : supponiamo vera la tesi per $n$ e dimostriamola per $n+1$.
Vogliamo quindi dimostrare che $\sum_{i=0}^{2n+2} a_{n+1,i-j}a_{n+1,i-j} = \sum_{i=0}^{2n+2} b_{n+1,i}b_{n+1,i-j}$. Grazie a (*) l'uguaglianza da dimostrare si riduce a $$\sum_{i=0}^{2n+2} (3a_{n,i} - 7a_{n,i-1} + 2a_{n,i-2})(3a_{n,i-j} - 7a_{n,i-j-1} + 2a_{n,i-j-2}) = \sum_{i=0}^{2n+2} (b_{n,i} - 5b_{n,i-1} + 6b_{n,i-2})(b_{n,i-j} - 5b_{n,i-j-1} + 6b_{n,i-j-2})$$

Svolgendo il calcoli e sfruttando l'ipotesi induttiva abbiamo la nostra tesi.

Ora passiamo al dimostrare per ogni $n \ge 1$ che $\sum_{i=0}^{2n} a_{n,i}^2 =\sum_{i=0}^{2n} b_{n,i}^2 $, usufruendo nuovamente del principio di induzione.

Passo base : $n=1$. Trivial again.

Passo induttivo : Come prima, supponiamo la tesi verificata per $n$ prestandoci ora a dimostrarla per $n+1$. Grazie a (*) riscriviamo l'identità da dimostrare come $$\sum_{i=0}^{2n+2} (3a_{n+1,i} - 7a_{n+1,i-1} + 2a_{n+1,i-2})^2 = \sum_{i=0}^{2n+2} (b_{n+1,i} - 5b_{n+1,i-1} + 6b_{n+1,i-2})^2$$

Svolgendo i calcoli è semplice notare che l'uguaglianza è verificata se $\sum_{i=1}^{2n} a_{n,i}a_{n,i-j} = \sum_{i=1}^{2n} b_{n,i}b_{n,i-j}$ con $j \in \{1,2\}$ , cosa che abbiamo dimostrato essere vera in precedenza, quindi fine.

AlexThirty
Messaggi: 214
Iscritto il: 20 giu 2015, 20:58

Re: Roba da smanettoni [SNS 2013/14 n. 5]

Messaggio da AlexThirty » 25 gen 2017, 21:34

Bene, come la mia!
La soluzione ufficiale è un po' più pulita e sfrutta questo fatto
Testo nascosto:
dato un polinomio $ h(x) $, i due polinomi $ (a+bx)h(x) $ e $ (b+ax)h(x) $ hanno somma dei quadrati dei coefficienti uguali
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Roba da smanettoni [SNS 2013/14 n. 5]

Messaggio da Giovanni_98 » 25 gen 2017, 22:31

Cavolo, effettivamente era ovvio. Inoltre ho visto il testo e quel fatto veniva dato come hint, il che spiega la scelta di questo problema.

AlexThirty
Messaggi: 214
Iscritto il: 20 giu 2015, 20:58

Re: Roba da smanettoni [SNS 2013/14 n. 5]

Messaggio da AlexThirty » 25 gen 2017, 23:02

Eh dove l'ho trovato io l'hint non c'era quindi ero nella tua stessa condizione :D
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti