Indovina il polinomio!

Polinomi, disuguaglianze, numeri complessi, ...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Indovina il polinomio!

Messaggio da Tibor Gallai » 22 mar 2010, 20:24

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?
[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]

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 25 mar 2010, 19:28

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
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 25 mar 2010, 20:07

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 :)
...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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 26 mar 2010, 04:26

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...
[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]

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 26 mar 2010, 18:15

2 domande vanno bene?
Non si smette mai di imparare.

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 26 mar 2010, 18:20

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!).
Non si smette mai di imparare.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 26 mar 2010, 21:40

@ 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.
[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]

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 26 mar 2010, 21:48

MIO DIO IN SOLE 2 DOMANDE :shock:
Complimenti ghilu xD
...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

Jessica92
Messaggi: 34
Iscritto il: 19 mar 2010, 18:08

Messaggio da Jessica92 » 26 mar 2010, 21:55

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?
Ultima modifica di Jessica92 il 26 mar 2010, 21:59, modificato 1 volta in totale.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 26 mar 2010, 21:59

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!! :wink:
[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]

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 26 mar 2010, 23:02

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 :shock:
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Messaggio da Dani92 » 27 mar 2010, 14:06

:oops: 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 $?

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 27 mar 2010, 14:09

Praticamente esprimi 37 in base 5 ;) E miracolosamente fuoriescono i coefficienti:
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

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Messaggio da Dani92 » 27 mar 2010, 14:13

Oh cavolo! :shock:

Mi spieghi perchè accade questo "miracolo"? :lol:

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? :oops:

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 27 mar 2010, 14:43

Esattamente ;)
...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

Rispondi