OliForum Matematico

Ho in tasca un polinomio P(x) a coefficienti interi positivi, e il vostro scopo è indovinarlo.
Inizialmente non sapete nulla su questo polinomio, ma ogni volta che mi dite un numero intero n, io vi rispondo dicendovi il valore di P(n).
Ovviamente potete decidere di volta in volta il valore di n, in funzione delle mie risposte precedenti.

Quale strategia seguite per indovinare il polinomio facendomi il minimo numero di domande?

Bonus 1: e se i coefficienti potessero essere anche interi negativi o nulli, ma comunque maggiori di una costante a voi nota?

Bonus 2: e se vi permettessi di domandarmi il valore di P(x) anche per x reali non interi?

visto che nessuno risponde, provo a rispondere almeno al primo senza soffermarmi troppo sui dettagli, poi suppongo (non ne sono sicuro al 100% e ora non ho tempo di verificare, ma mi sembra plausibile) che la stessa idea si possa applicare con qualche accorgimento anche agli altri punti.

1)Chiedo P(1). In questo modo so che tutti i coefficienti del polinomio sono minori o uguali a P(1), visto che sono interi positii.
2)Scelgo x qualsiasi abbastanza grande rispetto a P(1) e chiedo P(x)
3)Chiedo P(2x)
Ora so che per x abbastanza grande (si intende sempre rispetto ai coefficienti del polinomio), detto n il grado del polinomio, vale $ \displaystyle 2^n>\frac{P(2x)}{P(x)}>2^{n-1} $, perchè $ \displaystyle \lim_{x\rightarrow\infty}\frac{P(2x)}{P(x)}=2^n $ e se i coefficienti sono tutti positivi o nulli vale anche $ \displaystyle \frac{P(2x)}{P(x)}<2^n $.
Da questo ricavo che il grado del polinomio è $ \displaystyle [\log_2\frac{P(2x)}{P(x)}]+1 $, dove $ [m] $ è la parte intera di m.
4)A questo punto conosco il grado n e il valore del polinomio su tre punti, chiedo altri n-2 valori diversi dai precedenti e individuo il polinomio.

Per i polinomi con grado maggiore di 1 questa è sicuramente una possibile strategia ottimale perchè, anche se si conoscesse fin da subito il grado n del polinomio sarebbero comunque necessarie n+1 domande per individuarlo.

Se il polinomio ha grado 0, cioè è costante, me ne accorgo e mi fermo al punto 2.
Se il polinomio ha grado 1, mi pare plausibile che siano comunque necessarie 3 domande per individuarlo, ma ora vado un po' di fretta e se c'è la conferma che questo è vero proverò a dimostrarlo domani (oppure ci può provare qualcun altro, non mi offendo). In caso contrario scusate per l'errore

Maioc92 ha scritto: Per i polinomi con grado maggiore di 1 questa è sicuramente una possibile strategia ottimale perchè, anche se si conoscesse fin da subito il grado n del polinomio sarebbero comunque necessarie n+1 domande per individuarlo.

Questo è falso perchè sono a coefficienti interi.
Penso che dato il grado si riesca a farlo in molto meno, o almeno spero. Praticamente tu con 3 "chiamate" trovi il grado, ora dato il grado (sperando che sia una strategia ottimale) devi trovare il polinomio con meno domande possibili.
p.s. anche io avevo la stessa strategia :)

Scusate il ritardo.
dario ha detto una cosa giustissima: la chiave di tutto sta nella positività dei coefficienti, che può essere sfruttata per ricavare una strategia drasticamente migliore di quelle che avete proposto.
Suggerimento: domandare P(1) come prima cosa è una buona idea, ma da lì si può procedere meglio...

2 domande vanno bene?

E si dovrebbe fare anche con il Bonus 1, forse.
Ma nel bonus 2 la "realtà" si riferisce ai coefficienti o a quello che posso dire?
Perché se è la seconda ipotesi, allora equivale al problema originale (con una domanda non si riesce!).

@ ghilu: per il bonus 2 le ipotesi su P sono le stesse, ma mi si può chiedere un x anche non intero.
Comunque sarebbe il caso di dimostrare qualcuna delle congetture che enunci.

MIO DIO IN SOLE 2 DOMANDE
Complimenti ghilu xD

beh ad occhio io ti chiederei P(1) e poi P(P(1)), trovando quindi il polinomio vedendolo in base P(1).

In una mossa è impossibile poichè P(x) non è univocamente determinato conoscendo un solo valore.

Mettiamo che $ P(n)=a_k n^k + a_{k-1}+...+a_0 $ per ogni n diverso da zero possiamo trovare un Q(x) tale che $ b_k=a_k, ..., b_1=0, b_0=a_1 n + a_0 $ ad esempio.

Una domanda per il bonus 2:
In teoria se ti chiedessi $ P(\pi) $ sarebbe univocamente determinato, devo anche trovare un modo per determinarlo operativamente?

Jessica92 ha scritto:Una domanda per il bonus 2:
In teoria se ti chiedessi ad esempio$ P(\pi) $ sarebbe univocamente determinato, devo anche trovare un modo per determinarlo operativamente?

Mi accontentavo che fosse unicamente determinato P, perché il "determinarlo operativamente" è un problema più di calcolabilità che puramente algebrico, e lo giudico non elementare (già l'esistenza di numeri trascendenti sarebbe non elementare, ma mi pareva ugualmente carino proporlo come bonus).

In definitiva, bravo!!

scusate per il primo post, a quanto pare ho scazzato tutto usando l'ipotesi solo all'inizio (e tra l'altro nemmeno nel modo ottimale, vedo) e poi abbandonandola completamente
Comunque complimenti per la soluzione, non credo mi sarebbe venuta in mente tanto presto

Io non ho capito l'idea da Jessica, me la potete spiegare? Cioè se io dico 1 tu mi rispondi 5, poi dico 5 e tu mi rispondi 37, come faccio ad arrivare a $ P(x)=x^2+2x+2 $?

Praticamente esprimi 37 in base 5 ;) E miracolosamente fuoriescono i coefficienti:
37 in base 5 è 122 da cui viene $ $1x^2+2x+2 $

Oh cavolo!

Mi spieghi perchè accade questo "miracolo"?

EDIT: no aspetta, forse ho capito... il P(1) serve per trovare un numero sicuramente maggiore di ogni coefficente del polinomio? Così poi funziona il gioco delle basi? Per quello la condizione che siano positivi?

Esattamente ;)