Nome dell'autore: .mau.

Un problema matematico abbastanza noto, probabilmente l’ho anche messo nei miei quizzini, è il seguente. Io creo un polinomio $P$ a coefficienti interi non negativi, per esempio $n^2 + 42$ oppure $n^4 + 4n^3 + 6n^2 + 4n + 1$. Voi dovete scoprire qual è il polinomio nel minore numero di tentativi possibili: un tentativo consiste nel dirmi un numero, al che io vi dico il valore del polinomio calcolato in quel numero. Se per esempio voi mi dite 3 io nel primo caso risponderò 51 e nel secondo 256. Quanti tentativi vi servono per scoprire il polinomio? Fermatevi un attimo, se volete provare a risolvere il problema.

Può sembrare incredibile, ma bastano due tentativi; e posso anche dirvi che il primo tentativo usa il numero 1. Potete ancora pensarsi su un attimo, se volete.

Ecco la spiegazione di come trovare il polinomio. Per definizione, $P(1)$ è la somma di tutti i coefficienti del polinomio: nel primo caso 43, nel secondo 16. Dato che tutti i coefficienti sono positivi, sappiamo che nessuno può superare quel valore. Prendete ora la più piccola potenza di 10 che superi quel valore – in entrambi i casi è 100 – e chiedete quanto vale il polinomio per quel numero: nel primo caso è 10042 e nel secondo 104060401. Separate infine il numero ottenuto in parti della stessa lunghezza del numero di zeri del vostro tentativo, in questo caso 2: troviamo 1|00|42 e 1|04|06|04|01, e come vedete quelli sono proprio i coefficienti del polinomio. Chiedere un valore maggiore di $P(1)$ serve per non avere sovrapposizione tra i vari pezzi: con il primo polinomio se aveste chiesto $P(10)$ vi avrei risposto 142, e voi non avreste potuto distinguere tra $n^2 + 42$ o $n^2 + 4n + 2$. Vi sarebbe bastato prendere un qualunque numero maggiore di $P(1)$ e scrivere il risultato in quella base; ma perché fare più fatica del necessario a decodificare?

Proof Positive ha però mostrato che si può anche trovare il polinomio chiedendo il suo valore per un singolo numero! Il trucco è scegliere un numero trascendente, come $\pi$. Per definizione di numero trascendente, due polinomi qualunque a coefficienti interi devono per forza dare valori diversi quando calcolati per un valore trascendente: altrimenti la loro differenza sarebbe un polinomio che vale zero per quel numero, il che è impossibile. Prendiamo per esempio il primo polinomio: abbiamo che $P(\pi) = 51,86960440…$. Dato che $ \pi^4 \gt 3^4 = 81$ si sa che il polinomio è al più di terzo grado. A questo punto con molta pazienza si prova a vedere se è della forma $kx^3 + \textrm{qualcosa}$ con $k$ minore di 4, poi si passa a $kx^2 + \textrm{qualcosa}$ ed eventualmente, ma non è il nostro caso, a $kx + \textrm{qualcosa}$. Il numero di verifiche da fare è finito, e quindi in linea di principio, e se vi do sufficienti cifre decimali siete sicuri di trovarlo. Chiaramente all’inizio avevo usato $n$ e non $x$ come variabile per trarvi in inganno…