Indovina il polinomio!
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Indovina il polinomio!
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?
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?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
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
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
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Questo è falso perchè sono a coefficienti interi.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.
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 :)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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...
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...
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
@ 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.
Comunque sarebbe il caso di dimostrare qualcuna delle congetture che enunci.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
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?
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?
Ultima modifica di Jessica92 il 26 mar 2010, 21:59, modificato 1 volta in totale.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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).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?
In definitiva, bravo!!
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
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
Comunque complimenti per la soluzione, non credo mi sarebbe venuta in mente tanto presto
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Praticamente esprimi 37 in base 5 ;) E miracolosamente fuoriescono i coefficienti:
37 in base 5 è 122 da cui viene $ $1x^2+2x+2 $
37 in base 5 è 122 da cui viene $ $1x^2+2x+2 $
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai