Polinomi e sporchi trucchi
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…
Dovrebbe ormai esservi noto che io amo leggere questi vecchissimi libretti che la Progresso Tecnico Editoriale traduceva dalla traduzione inglese degli originali russi. (Non che ci sia nulla da eccepire sul lavoro di Emanuele Vinassa de Regny, a parte un “il gioco è giusto”, anziché equo, al fondo di pagina 58.) Non è che debba impararci nulla, ma penso che sia interessante vedere un punto di vista diverso da quello a cui siamo abituati.