Un Bell'Esercizio

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
CoccodrilloGiurys
Messaggi: 1
Iscritto il: 11 ago 2019, 16:41

Un Bell'Esercizio

Messaggio da CoccodrilloGiurys » 11 ago 2019, 16:45

[math]
Ecco un esercizio carino: in quanti modi posso scrivere n come $f(2)$ di una funzione polinomiale con coefficienti che possono essere solo 0,1,2,3?

Avatar utente
Fenu
Messaggi: 67
Iscritto il: 10 set 2017, 16:34

Re: Un Bell'Esercizio

Messaggio da Fenu » 11 ago 2019, 21:35

Mostro una soluzione che permette di capire come si arriva al risultato.
Ragioniamo utilizzando le funzioni generatrici. E' chiaro che il problema ci chiede di trovare il coeff. di $x^n$ nella ogf
$G(x)=(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^{12})..$ dato che gli esponenti che prendiamo sono tutti e soli i termini del tipo $2^ka$ (dove $a$ ha i bound del testo) contati con la giusta molteplicità. Riscrivendo si ha
$G(x)=\frac{x^4-1}{x-1}\frac{x^8-1}{x^2-1}\frac{x^{16}-1}{x^4-1}\frac{x^{32}-1}{x^8-1}..$ ottenuta utilizzando l fatto che tutti i fattori tra parentesi sono della forma $(1+x+x^2+x^3)=\frac{x^4-1}{x-1}$ e sostituendo al posto di $x\rightarrow x^{2^\alpha}$.
Semplificando "a croce" e ricordando che la produttoria va a infinito, ricaviamo una scrittura per $G$ decisamente comoda:
$G(x)=\frac{1}{1-x}(x^2+1)(x^4+1)(x^8+1)(x^{16}+1)...$.
Cosa vogliamo fare qui? Trovare $[x^n]$:i prodotti contribuiscono in un solo modo per ottenere $x^{2k}$ (basta, ad esempio, scrivere 2k in base 2 e prendere i termini in $x$ nei fattori con l'$1$ della rappresentazione binaria), mentre invece il best friend contribuisce in un solo modo per ogni $k$ naturale. Segue che, preso un numero $k$, possiamo prendere un pari $a$ qualsiasi (anche $0$) minore di lui, rappresentarlo con i fattori binari, e prendere ciò che resta (ossia $k-a$) dal $\frac{1}{1-x}$: tutto ciò può essere fatto in un unico modo (e viceversa.. da una scelta degli esponenti passare alla scelta dell' $a$, a ritroso), pertanto $x^k$ avrà come coeff. il numero di pari sotto di lui (eventualmente lui stesso).
Segue che la risposta è $\lfloor{\frac{n}{2}}\rfloor+1$.
Piccola insight: dimostrazioni più elementari, o talvolta veloci, sono facili da ricavare una volta claimato il risultato (ad esempio: se io ho rappresentato n, cosa posso fare per rappresentare n+1?.. ).

TeoricodeiNumeri
Messaggi: 17
Iscritto il: 14 lug 2019, 09:58

Re: Un Bell'Esercizio

Messaggio da TeoricodeiNumeri » 19 ago 2019, 15:24

[math] Vi propongo una soluzione che non fa uso di generatrici: denotata con $\lbrace a_n \rbrace_{n\in \mathbb{N}}$ la successione che conta il numero di modi di scrivere $n$ come combinazione lineare a coefficienti in $\lbrace 0;1;2;3\rbrace$ di potenze di $2$ distinte, risulta che la successione in questione è soluzione della seguente ricorrenza per $n\geq 2$:
\begin{equation}
a_n =a_{\lfloor n/2 \rfloor}+ a_{\lfloor n/2 \rfloor -1}
\end{equation}
Difatti per qualsiasi rappresentazione di $n\geq 2$ come $b_k b_{k-1}\dots b_0$ con tutti i $b_i\in \lbrace 0;1;2;3\rbrace$ abbiamo che $b_0$ può essere scelto in due modi in base alla classe di congruenza di $n$ modulo $2$. Se indichiamo con $c_0$ l'ultima cifra della rappresentazione di $n$ in base $2$, chiaramente le rappresentazioni di $n$ in cui $b_0=c_0$ sono in bigezione con le rappresentazioni di $\lfloor n/2 \rfloor$ e se invece $b_0=c_0 +2$ (il che si può verificare sse $n\geq 2$) allora tali rappresentazioni sono in bigezione con le rappresentazioni di $\lfloor n/2 \rfloor -1$.
Una volta scoperta questa ricorrenza abbastanza semplice diventa facile computare i primi termini della successione :
\begin{equation}
a_0 =1,a_1=1,a_2=1+1=2,a_3=2,a_4=1+2=3,a_5=3,a_6=2+2=4,a_7=4 \dots
\end{equation}
e quindi congetturiamo che $a_n=\lfloor n/2 \rfloor +1$. Per dimostrarla utilizziamo l'induzione forte:
1) caso base: $a_0=1=\lfloor 0/2 \rfloor +1$ e $a_1=1=\lfloor 1/2\rfloor +1$;
2) supponiamo ora che per ogni valore minore di un $n$ qualsiasi (con $n\geq 2$) valga la congettura e dimostriamola per $n$. Per semplificarci la vita (alias: non usare la parte intera), notiamo che sia perché $a_0=a_1$ e sia per la ricorrenza scoperta vale necessariamente che $a_{2n}=a_{2n+1}$ per qualsiasi $n$ naturale, per cui è sufficiente dimostrare la congettura per i termini a indice pari visto che $\lfloor 2n/2 \rfloor +1=n+1=\lfloor (2n+1)/2 \rfloor +1$. Se $n$ è pari allora si possono verificare solo due possibilità: $n=4k$ oppure $n=4k+2$ per qualche $k$ naturale, da cui
a) se $n=4k$ allora $a_n =a_{2k} +a_{2k-1}=k+1+k-1+1=2k+1=\lfloor n/2 \rfloor +1$;
b) se $n=4k+2$ allora $a_n=a_{2k+1}+a_{2k}=2\cdot (k+1)=2k+1+1=\lfloor n/2 \rfloor +1$.
Lo so, è una soluzione molto più barbara ma ci tenevo a mostrare a quelli che di funzioni generatrici non hanno mai sentito parlare e si sono spaventati che è possibile farlo anche con un po' di intuito.

Rispondi