Per chi soffre di insonnia... un simpatico problemino...

[Sk_Anonymous]

Ragazzi
anche questa settimana è arrivata al venerdì e ci rilassiamo un poco in attesa del fine settimana. E quale miglior relax che risolvere un bel problemino?…

Per unire l’utile al dilettevole pertanto vi proporrò un problema la cui soluzione è estremamente utile per un problema che sto affrontando e che ora vi spiego. Supponiamo di avere una funzione complessa in $z$ definita come il prodotto di due polinomi $P(z)$ e $Q(z)$ nel modo seguente…

$R(z)=P(z)*Q(z)= prod_(k=0)^(n-1)* (1-(z^(-1))/(sigma_k))* prod_(i=0)^(n-1)* (1-(z^(-1))/(tau_i))$ (1)

… i cui…

$sigma_k= r_1*e^(j*2*pi*k/n)$, $tau_i= r_2*e^(j*2*pi*i/n)$ , $k=0,1,…,n-1$, $i=0,1,…,n-1$ (2)

I parametri $r_1$ ed $r_2$ non sono indipendenti ma sono legati dalla relazione $r_1*r_2=1$. Le $sigma_k$ e le $tau_i$ sono disposte su cerchi concentrici nell’origine nel modo mostrato in figura ove è $n=8$ e $r_1=.562348$…



Delle $2n$ radici che compaiono nella (2) $n$ formano il polinomio $P$ e $n$ il polinomio $Q$. La loro scelta non è arbitraria ma è soggetta al vincolo che se $alpha$ è radice di $P$, allora $1/alpha$ è radice di $Q$. Esemplificando facendo riferimento alla figura, se $sigma_1= r_1*e^(j*pi/4)$ è radice di $P$, allora $1/sigma_1= tau_7= r_2*e^(-j*pi/4)$ è radice di $Q$. Il problema che ho il piacere di sottoporvi consiste nel fornire una risposta alle seguenti domande…

a) fissati $n$ e $r_1$, quante possibili differenti coppie di polinomi $P$ e $Q$ posso costruire?…
b) detto N il numero di queste coppie, come posso associare univocamente un indice $m$ con $m$ che và da $0$ a $N-1$ a ciascuna coppia?…

Spero sia un problema idoneo a solleticare il vostro interesse… e la vostra ‘voglia di competizione’ naturalmente…

Buon fine settimana… e buon divertimento!…

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[_luca.barletta]

a) se ho capito bene il quesito: abbiamo 2n radici, quando scegliamo la prima da assegnare a P, quella da assegnare a Q rimane determinata, pertanto rimangono 2n-2 radici da assegnare. Procedendo così fino ad assegnare tutte le radici, le coppie possibili sono
$N=prod_(i=1)^n 2i=2^n*n!$

se $r_1=r_2=1$ abbiamo 2n radici coincidenti a coppie

[Sk_Anonymous]

Una risposta veramente rapida!... troppo rapida e per 'digerirla' mi ci vorrà un pò ... grazie comunque!...

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[Sk_Anonymous]

Ragazzi
noto che l’unico che l’unico che ha voluto darmi una mano è stato Luca [Barletta] e deduco [ma in questo caso la colpa è mia…] che il problema da me posto non deve aver suscitato molto interesse. Riproponiamo nuovamante il problema…

Dato il seguente prodotto di due polinomi [in $z^-1$…] $P$ e $Q$…

$P(z)*Q(z)= prod_(k=0)^(n-1)* (1-sigma_k*z^(-1))* prod_(i=0)^(n-1)* (1-tau_i*z^(-1))$ (1)

… i cui…

$sigma_k= r_1*e^(j*2*pi*k/n)$, $tau_i= r_2*e^(j*2*pi*i/n)$ , $k=0,1,…,n-1$, $i=0,1,…,n-1$ (2)

… sapendo che che se $alpha$ è radice di $P$, allora $1/alpha$ è radice di $Q$ e viceversa se $alpha$ è radice di $Q$, allora $1/alpha$ è radice di $$.P, determinare il numero N di possibili coppie di polinomi $P$ e $Q$ che si possono formare dati $n$ ed $r_1$.

Il motivo per il quale sono interessato a questo numero $N$ non è mera curiosità ma risponde ad una specifica esigenza. Diciamo che per l’applicazione che ho in mente $N$ deve essere almeno dell’ordine di $10^18$ [!…]. Il nostro amico Luca [Barletta] ci ha fornito il seguente valore…

$N=prod_(i=1)^n 2i=2^n*n!$ (3)

Sul momento la cosa mi ha riempito di gioia dal momento che se $n=8$ [come nell’esempio da me fornito…] allora è $N= 2^8*(8!)= 10321920$ [dieci milioni trecentomila e passa!… ] … però!… E se $n=16$?… allora $N=2*16*(16!)= 1.37116… 10^18$ [un miliardo e trecentomilioni di miliardi e passa!… ]… allora ci siamo!… Ma è possibile con $n$ così ‘piccolo’?…

Per pura verifica andiamo ad esaminare il caso $n=8$ aiutandoci col la figura…



Dunque dunque… cominciamo con la coppia di radici ‘reali positive’ $r_1$ ed $r2$. Qui è semplice poiché i casi possibili sono due, ovvero $r_1$ radice di $P$ ed $r_2$ radice di $Q$ o viceversa. Stessa cosa per quanto riguarda la coppia di radici ‘reali negative’ $-r_1$ e $-r_2$. Andiamo ora a vedere un coppia di radici complesse, per esempio $sigma_1$ e $tau_1$. Qui i casi possibili sono…

a) $sigma_1$ è radice di $P$ [quindi $tau_7$ è radice di $Q$…] e $tau_1$ è radice di $Q$ [quindi $sigma_7$ è radice di $P$…]
b) $sigma_1$ è radice di $Q$ [quindi $tau_7$ è radice di $P$…] e $tau_1$ è radice di $P$ [quindi $sigma_7$ è radice di $Q$…]
c) $sigma_1$ e $tau_1$ sono entrambe radici di $P$ [quindi $sigma_7$ e $tau_7$ sono entrambe radici di $Q$…]
d) $sigma_1$ e $tau_1$ sono entrambe radici di $Q$ [quindi $sigma_7$ e $tau_7$ sono entrambe radici di $P$…]



Altri casi possibili non sembrano esserci per cui ogni coppia di radici complesse con parte immaginaria positiva fornisce quattro casi possibili. Dal momento che le coppie di radici reali sono $2$ e le coppie di radici comlplesse con parte immaginaria positiva sono $3$ le combinazioni possibili con $n=8$ sembrano essere $N= 4^4=2^8=256$… peccato!…

Siccome lo stesso discorso si può fare per tutti gli $n$ [anche per $n$ dispari…] sembra si debba dedurre che il numero cercato vale 'semplicemente'…

$N=2^n$ (4)

Pertanto per quello che ho in mente $n$ deve essere almeno pari a $64$ [dal momento che $2^64=1,84467… 10^19$…] Vabbeh!…

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[Sk_Anonymous]

"lupo grigio":Supponiamo di avere una funzione complessa in $z$ definita come il prodotto di due polinomi $P(z)$ e $Q(z)$ nel modo seguente

$R(z)=P(z)*Q(z)= prod_(k=0)^(n-1)* (1-(z^(-1))/(sigma_k))* prod_(i=0)^(n-1)* (1-(z^(-1))/(tau_i))$ (1)

i cui $sigma_k= r_1*e^(j*2*pi*k/n)$, $tau_i= r_2*e^(j*2*pi*i/n)$ , $k=0,1,…,n-1$, $i=0,1,…,n-1$ (2)

I parametri $r_1$ ed $r_2$ non sono indipendenti ma sono legati dalla relazione $r_1*r_2=1$.

Delle $2n$ radici che compaiono nella (2) $n$ formano il polinomio $P$ e $n$ il polinomio $Q$. La loro scelta non è arbitraria ma è soggetta al vincolo che se $alpha$ è radice di $P$, allora $1/alpha$ è radice di $Q$. Il problema che ho il piacere di sottoporvi consiste nel fornire una risposta alle seguenti domande…

a) fissati $n$ e $r_1$, quante possibili differenti coppie di polinomi $P$ e $Q$ posso costruire?

Infiniti, è evidente. Seguono chiacchiere - lascerò che sia.

Sia identicamente $P(z) = P_0 \prod_(k=0)^(n-1) (1-z/\sigma_k) = P_0 \prod_(k=0)^(n-1) (1-z/r e^{-j\frac{2\pi k}{n}}) = {(-1)^n P_0}/r^n \cdot \prod_{k=0}^{n-1} (z - r e^{j\frac{2\pi k}{n}})$, dove $r \in (0,+\infty)$ ed $n \in NN^+$ sono fissati e $P_0$ è un qualunque coefficiente (complesso) $\ne 0$. Vale allora $P(z) = 0$ sse $z = \sigma_k = r e^{j\frac{2\pi k}{n}}$, per k = 0, 1, ..., n-1. Sia adesso $Q \in CC[z]$ tale che deg Q = n e $Q(1/z_k) = 0$, per ogni $k = 0, 1, ..., n-1$. Allora $\tau_k = 1/r e^{-{j\frac{2\pi k}{n}}$ è uno zero di $Q(-)$, per ogni $k = 0, 1, ..., n-1$, e perciò (non è certo per un caso se lo chiamano teorema fondamentale dell'algebra...) $Q(z) = Q_0 \prod_{k=1}^n (z - 1/r e^{-j\frac{2\pi k}{n}}) = Q_0 \prod_{k=0}^{n-1} (z - 1/r e^{j\frac{2\pi k}{n}}) = {(-1)^n Q_0}/r^n \cdot \prod_{k=0}^{n-1} (1 - rz e^{-j\frac{2\pi k}{n}}) = {(-1)^n Q_0}/r^n \cdot \prod_{k=0}^{n-1} (1 - z/\tau_k)$, per qualche $Q_0 \in CC$ \ $\{0\}$.

Tutto sostanzialmente inutile, visto che un polinomio di dato grado è univocamente determinato dalle sue radici (molteplicità incluse). E adesso... Cosa mai ho frainteso!?

[Sk_Anonymous]

"DavidHilbert":
Infiniti, è evidente.

A meno di aggiungere una qualche condizione di normalizzazione su $P(-)$: nel qual caso, $\infty$ -> 1.

[_luca.barletta]

@ lupo grigio:

al mio ragionamento mancava una normalizzazione, infatti per la proprietà commutativa del prodotto i polinomi non risentono dell'ordine di scelta delle radici, quindi:
$N=(prod_(i=i)^n 2i)/(n!)=2^n$

[Sk_Anonymous]

"luca.barletta":
al mio ragionamento mancava una normalizzazione, infatti per la proprietà commutativa del prodotto i polinomi non risentono dell'ordine di scelta delle radici, quindi:
$N=(prod_(i=i)^n 2i)/(n!)=2^n$

Ma cosa c'entra!? Un polinomio è univocamente determinato dalle sue radici e dal coefficiente del termine di massimo grado, indipendentemente dall'ordine con cui le stesse radici sono enumerate. Il problema chiede di stabilire quanti sono i polinomi che soddisfano un set ben definito di proprietà, e non quante sono le possibili permutazioni delle loro radici... Dico bene!?

[_luca.barletta]

"DavidHilbert": Un polinomio è univocamente determinato dalle sue radici e dal coefficiente del termine di massimo grado, indipendentemente dall'ordine con cui le stesse radici sono enumerate.

Appunto.
Ti faccio un esempio molto ridotto, n=2. Abbiamo a disposizione 4 zeri sul piano z ${a,1/a,-a,-1/a}$. Costruisco tutti i possibili polinomi P(z):
$P_1(z)=(1-az^-1)(1+1/az^-1)=1+(1/a-a)z^-1-z^-2$
$P_2(z)=(1-az^-1)(1+az^-1)=1-a^2z^-2$
$P_3(z)=(1-1/az^-1)(1+az^-1)=1+(-1/a+a)z^-1-z^-2$
$P_4(z)=(1-1/az^-1)(1+1/az^-1)=1-1/a^2z^-2$

naturalmente se a=1 il problema degenera

[Sk_Anonymous]

"luca.barletta":
Ti faccio un esempio molto ridotto, n=2. Abbiamo a disposizione 4 zeri sul piano z ${a,1/a,-a,-1/a}$. Costruisco tutti i possibili polinomi P(z):
$P_1(z)=(1-az^-1)(1+1/az^-1)=1+(1/a-a)z^-1-z^-2$
$P_2(z)=(1-az^-1)(1+az^-1)=1-a^2z^-2$
$P_3(z)=(1-1/az^-1)(1+az^-1)=1+(-1/a+a)z^-1-z^-2$
$P_4(z)=(1-1/az^-1)(1+1/az^-1)=1-1/a^2z^-2$

A parte che $P_1(-)$ (risp., $P_3(-)$) non soddisfa i requisiti imposti nella consegna, visto che gli zeri dell'equazioni $P_1(z) = 0$ (risp., $P_3(z) = 0$) non appartengono ad una stessa circonferenza centrata nell'origine del piano complesso (a meno del caso a = 1), è detto espressamente che il parametro $r$ deve intendersi fissato, una volta per tutte, in capo al problema: diversamente c'è poco di cui discutere, le coppie possibili divengono una volta in più infinite. Senonché, nel tuo esempio, r = a in quanto a $P_2(-)$, ed $r = 1/a$ in quanto a $P_4(-)$. Luca!?

[_luca.barletta]

io ho interpretato la consegna nel senso che le radici non dovevano per forza di cose essere scelte dalla stessa circonferenza, altrimenti logicamente N=1 una volta fissati tutti i parametri.

[Sk_Anonymous]

"luca.barletta":io ho interpretato la consegna nel senso che le radici non dovevano per forza di cose essere scelte dalla stessa circonferenza, altrimenti logicamente N=1 una volta fissati tutti i parametri.

Eppure non c'è molto spazio per l'interpretazione, lupo grigio è stato chiaro quanto basta:

"lupo grigio":Supponiamo di avere una funzione complessa in $z$ definita come il prodotto di due polinomi $P(z)$ e $Q(z)$ nel modo seguente: $R(z)=P(z)*Q(z)= prod_(k=0)^(n-1)* (1-(z^(-1))/(sigma_k))* prod_(i=0)^(n-1)* (1-(z^(-1))/(tau_i))$ (1) i cui

$sigma_k= r_1*e^(j*2*pi*k/n)$, $tau_i= r_2*e^(j*2*pi*i/n)$ , $k=0,1,…,n-1$, $i=0,1,…,n-1$ (2)

I parametri $r_1$ ed $r_2$ [...] sono legati dalla relazione $r_1*r_2=1$. Le $sigma_k$ e le $tau_i$ sono disposte su cerchi concentrici nell’origine [...]

Delle $2n$ radici che compaiono nella (2) $n$ formano il polinomio $P$ e $n$ il polinomio $Q$. La loro scelta non è arbitraria ma è soggetta al vincolo che se $alpha$ è radice di $P$, allora $1/alpha$ è radice di $Q$. [...] Il problema che ho il piacere di sottoporvi consiste nel fornire una risposta alle seguenti domande…

a) fissati $n$ e $r_1$, quante possibili differenti coppie di polinomi $P$ e $Q$ posso costruire?

A parte, forse, per il fatto che i cerchi non sono cerchi, bensì circonferenze.

[_luca.barletta]

ma non ha detto che tutti i $sigma_k$ sono di P e che i $tau_i$ sono di Q.
Leggiti il terzo post di lupo grigio

[Sk_Anonymous]

"lupo grigio":
a) $sigma_1$ è radice di $P$ [quindi $tau_7$ è radice di $Q$…] e $tau_1$ è radice di $Q$ [quindi $sigma_7$ è radice di $P$…]
b) $sigma_1$ è radice di $Q$ [quindi $tau_7$ è radice di $P$…] e $tau_1$ è radice di $P$ [quindi $sigma_7$ è radice di $Q$…]
c) $sigma_1$ e $tau_1$ sono entrambe radici di $P$ [quindi $sigma_7$ e $tau_7$ sono entrambe radici di $Q$…]
d) $sigma_1$ e $tau_1$ sono entrambe radici di $Q$ [quindi $sigma_7$ e $tau_7$ sono entrambe radici di $P$…]

Ah, ecco! In effetti, mi ero perso l'esempio e avevo operato un'assunzione di troppo. Resta comunque il fatto che, in assenza di condizioni di normalizzazione sul coefficiente guida di P(-), i polinomi possibili sono infiniti.