Due valori bastano
Inviato: 09 nov 2012, 09:46
Visto di recente su MathOverflow:
[Edit: versione più generale e sorprendente...]
Alberto sceglie un polinomio $p(x)$ a coefficienti naturali (interi nonnegativi), e lo tiene segreto. Barbara sceglie un intero $a$, chiede ad Alberto di dirle $p(a)$; poi, sentita la risposta, sceglie un intero $b$, e chiede ad Alberto di dirle $p(b)$. Mostrare che, scegliendo opportunamente $a$ e $b$, questa informazione basta a Barbara per determinare tutti i coefficienti di $p$.
Bonus: mostrare che se invece Barbara sceglie due interi $a,b$ e chiede ad Alberto di dirle $p(a)$ e $p(b)$, allora potrebbe non essere in grado di ricostruire tutti i coefficienti di $p$.
[Edit: versione più generale e sorprendente...]
Alberto sceglie un polinomio $p(x)$ a coefficienti naturali (interi nonnegativi), e lo tiene segreto. Barbara sceglie un intero $a$, chiede ad Alberto di dirle $p(a)$; poi, sentita la risposta, sceglie un intero $b$, e chiede ad Alberto di dirle $p(b)$. Mostrare che, scegliendo opportunamente $a$ e $b$, questa informazione basta a Barbara per determinare tutti i coefficienti di $p$.
Bonus: mostrare che se invece Barbara sceglie due interi $a,b$ e chiede ad Alberto di dirle $p(a)$ e $p(b)$, allora potrebbe non essere in grado di ricostruire tutti i coefficienti di $p$.