Quante domande?

[Giovanni98]

Leo e Cristiano fanno il seguente gioco : Cristiano scrive un polinomio a coefficienti interi non negativi alla lavagna e non lo mostra a Leo, che lo deve indovinare. Leo però può chiedere a Cristiano il valore di $P(x)$ con $x$ intero. Quante domande al minimo deve fare Leo a Cristiano per essere certo di poter dedurre il polinomio scritto da Cristiano?

[CosecantofPi]

Non so come prendere questo problema.. La risposta piu' ovvia e' $n+1$ dove $n$ e' il grado del polinomio.. Ce' probabilmente un inganno, ma sono sicuro che nel problema manca un dato, ovvero il grado di $P(x)$, senno' esso potrebbe essere indefinitamente grande.
PS: La mia risposta utilizza il principio di identita' dei polinomi, che asserisce che se due polinomi di $n-esimo$ grado coincidono in $n+1$ punti, sono identici.
Facendo esattamente $n$ domande, invece si potrebbe provare un interpolazione, ma i possibili polinomi non sono identici.

[Veritasium]

Non mancano dati.

Risultato

Testo nascosto:

$2$

Hintone

Testo nascosto:

Siano $k, C$ interi positivi. Sia $W$ l'insieme di tutti i polinomi di grado al più $k$ a coefficienti interi non negativi e minori uguali di $C.$ Allora esiste una costante $S(k,C)$ tale che, per ogni intero positivo $a > S,$ vale $p(a) \neq q(a)$ per ogni $p \neq q$ polinomi in $W.$

Prima o poi posterò la soluzione completa.

[mr96]

Non mancano dati.

Risultato

Testo nascosto:

$2$

Hintone

Testo nascosto:

Siano $k, C$ interi positivi. Sia $W$ l'insieme di tutti i polinomi di grado al più $k$ a coefficienti interi non negativi e minori uguali di $C.$ Allora esiste una costante $S(k,C)$ tale che, per ogni intero positivo $a > S,$ vale $p(a) \neq q(a)$ per ogni $p \neq q$ polinomi in $W.$

Prima o poi posterò la soluzione completa.

Anche

Testo nascosto:

Cosa succede se scrivo [tex]p(p(1))[/tex] in base [tex]p(1)[/tex]?

[Lasker]

I vostri hint sono troppo violenti secondo me bastava segnalare

coefficienti interi non negativi

che è il dato che CosecantofPi non sta usando

[Veritasium]

I vostri hint sono troppo violenti

Effettivamente è vero, ma il fatto in sé è figo ed è comunque ciò a cui sono arrivato per dimostrare il risultato. Poi è divertente fare effettivamente il gioco con amici usando

Testo nascosto:

$2$ e poi $p(2) + 1$.
Per grado $≤ 6$ è effettivamente fattibile con una calcolatrice e stupisce in quanto chiunque con un minimo di esperienza è portato a claimare [tex]n+1[/tex] domande con $n$ il grado.

[CosecantofPi]

Effettivamente ci ho messo un po a comprendere gli hint. Tuttavia, mi piacerebbe vedere con che passaggi siete arrivati al 2. Io ho fatto un po di tentativi per arrivare alla risposta, vorrei vedere i vostri procedimenti
Scusate il fallimento

[mr96]

Effettivamente ci ho messo un po a comprendere gli hint. Tuttavia, mi piacerebbe vedere con che passaggi siete arrivati al 2. Io ho fatto un po di tentativi per arrivare alla risposta, vorrei vedere i vostri procedimenti
Scusate il fallimento

Testo nascosto:

Se scrivo $p(p(1))$ in base $p(1)$ ho i coefficienti del polinomio, quindi la prima domanda sarà $p(1)$ e la seconda $p(p(1))$. Perché questo funziona?

[Gerald Lambeau]

Non funziona. Cioè, funziona, ma devi prestare attenzione a troppe cose. Se il polinomio è della forma $cx^n$ allora $p(1)=c$ e $p(p(1))=c^{n+1}$, che in base $p(1)=c$ ti fa credere che il polinomio sia $x^{n+1}$. Ovvio, sai che ciò è impossibile perché altrimenti $p(1)=1$, ma se $c=1$? Sì, ok, in quel caso invece di $p(1)=1$ proveresti un altro numero come secondo tentativo, ma diventa poco pratica come soluzione. Non sarebbe più pulito guardare $p(p(1)+1)$ in base $p(1)+1$? L'unico caso dove questa cosa non può essere fatta, dato che $p(1) \ge 0$, è quando $p(1)+1=1 \Rightarrow p(1)=0$, ma questo caso non credo sia un problema.