Non so quanto sia leggera questa matematica qua; diciamo però che la soluzione, quando ve la dicono, è facile.
Come forse ricordate, un polinomio di grado n può essere determinato univocamente se conoscete il suo valore in n+1 punti. Supponiamo però che ci venga detto che il nostro polinomio P sia speciale: i suoi coefficienti sono tutti interi non negativi. In questo caso è concepibile che si possa determinare il polinomio conoscendo un numero minore di valori. Se ci è consentito di scegliere opportunamente per quali numeri x (algebrici) ci venga detto qual è il valore di P(x), quanti ce ne serviranno?
(l’ho visto da God Plays Dice, dove c’è anche la soluzione…)
Ultimo aggiornamento: 2010-03-17 16:22
La soluzione è davvero bella, semplice ed elegante. Non ho provato a farlo da sola, ma non credo sarei riuscita (forse vent’anni fa).
A differenza di Barbara, non ho dubbio veruno: non ce l’avrei fatta in millanta anni. Ciò non toglie che la soluzione è non solo bella, ma prossima alla magia, tanto è geniale.
Tra l’altro, come scrive Isabel, dire che si possono scegliere numeri algebrici è una falsa traccia, visto che basta usare gli interi. È chiaro che se si possono scegliere numeri reali qualunque basterebbe prenderne uno solo purché sia trascendente: però mi chiedo se ci sia un algoritmo un po’ più intelligente della forza bruta per ricavare il polinomio, e se c’è una scelta computazionalmente più leggera.