Staffetta tdn
Re: Staffetta tdn
Mi aggiungo anche io a questa staffetta TDN, aggiungendo anche la mia gioia per la riapertura del forum! Allora,
Partendo dal fatto noto che negli interi di Gauss c'è la fattorizzazione unica, considero un primo p che divide x. Allora $ p|z^2+1 $ quindi $ p|(1+iz)(1-iz) $ . Se p fosse primo ( e cioè irriducibile ) negli interi di Gauss, dovrebbe dividere uno di quei 2 fattori, che è impossibile perché implicherebbe che $ p(a+ib)=(1\pm z) \rightarrow pa=1 $ . Quindi p è riducibile, cioè esistono e,f tali che $ p=(e+if)(e-if)=e^2+f^2 $ (p è somma di quadrati) . L'essere somma di quadrati è moltiplicativo, perché $ (e^2+f^2)(z^2+w^2)=(ez+fw)^2+(ew-fz)^2 $ . Pertanto, x è somma di quadrati, e analogamente anche y. Consideriamo tutte le possibili scritture di x e y come somme di quadrati. Se genericamente scrivo $ x=a^2+b^2 $ e $ y=c^2+d^2 $ , xy si scrive come $ (ac+bd)^2+(ad-bc)^2 $ . Facendo variare a,b,c,d in tutti i modi possibili, $ (ac+bd)^2+(ad-bc)^2 $ descrive tutti e soli i modi di scrivere xy come somma di quadrati. Pertanto, essendo $ xy=z^2+1 $, esiste una scelta di a,b,c,d tale che $ ac+bd=z $ e in più $ ad-bc=1 $
Problema 82: Sia $ n $ un numero naturale positivo (non so mai se i naturali hanno lo zero). Definisco $ S_n $ la somma dei quadrati dei coefficienti di $ (1+x)^n $ . Dimostrare che $ S_{2n}+1 $ non è divisibile per 3.
Partendo dal fatto noto che negli interi di Gauss c'è la fattorizzazione unica, considero un primo p che divide x. Allora $ p|z^2+1 $ quindi $ p|(1+iz)(1-iz) $ . Se p fosse primo ( e cioè irriducibile ) negli interi di Gauss, dovrebbe dividere uno di quei 2 fattori, che è impossibile perché implicherebbe che $ p(a+ib)=(1\pm z) \rightarrow pa=1 $ . Quindi p è riducibile, cioè esistono e,f tali che $ p=(e+if)(e-if)=e^2+f^2 $ (p è somma di quadrati) . L'essere somma di quadrati è moltiplicativo, perché $ (e^2+f^2)(z^2+w^2)=(ez+fw)^2+(ew-fz)^2 $ . Pertanto, x è somma di quadrati, e analogamente anche y. Consideriamo tutte le possibili scritture di x e y come somme di quadrati. Se genericamente scrivo $ x=a^2+b^2 $ e $ y=c^2+d^2 $ , xy si scrive come $ (ac+bd)^2+(ad-bc)^2 $ . Facendo variare a,b,c,d in tutti i modi possibili, $ (ac+bd)^2+(ad-bc)^2 $ descrive tutti e soli i modi di scrivere xy come somma di quadrati. Pertanto, essendo $ xy=z^2+1 $, esiste una scelta di a,b,c,d tale che $ ac+bd=z $ e in più $ ad-bc=1 $
Problema 82: Sia $ n $ un numero naturale positivo (non so mai se i naturali hanno lo zero). Definisco $ S_n $ la somma dei quadrati dei coefficienti di $ (1+x)^n $ . Dimostrare che $ S_{2n}+1 $ non è divisibile per 3.
CUCCIOLO
-
- Messaggi: 131
- Iscritto il: 11 giu 2010, 17:56
- Località: Milano, in provincia...
Re: Staffetta tdn
allora, ci provo io...
$ s_n = \sum_{r=0}^{n}\binom{n}{r}^2= \Bigl( \sum_{r=0}^{n}\binom{n}{r} \Bigr) ^2 -2 \sum_{{\alpha \neq \beta}\atop {0\le \alpha \le n,0 \le \beta \le n}}\binom{n}{\alpha} \binom{n}{\beta} = 2^{2n} -2\sum_{\alpha = 0}^{n}\Bigl( 2^n -\binom{n}{\alpha} \Bigr)\binom{n}{\alpha} $
Da qui si ottiene quindi che $ S_n = 2^{2n}-\sum_{\alpha=0}^{n}2^{n+1}\binom{n}{\alpha} +2S_n $
$ S_n = 2^{2n+1} -2^{2n} = 2^{2n} $
Quindi, essendo $ S_{2n} = 2^{4n} $ si ha che $ 2^{4n}+1 \equiv 16^n+1 \equiv 2 \mod{3} $
Aspetto conferme per postare u altro problema...
$ s_n = \sum_{r=0}^{n}\binom{n}{r}^2= \Bigl( \sum_{r=0}^{n}\binom{n}{r} \Bigr) ^2 -2 \sum_{{\alpha \neq \beta}\atop {0\le \alpha \le n,0 \le \beta \le n}}\binom{n}{\alpha} \binom{n}{\beta} = 2^{2n} -2\sum_{\alpha = 0}^{n}\Bigl( 2^n -\binom{n}{\alpha} \Bigr)\binom{n}{\alpha} $
Da qui si ottiene quindi che $ S_n = 2^{2n}-\sum_{\alpha=0}^{n}2^{n+1}\binom{n}{\alpha} +2S_n $
$ S_n = 2^{2n+1} -2^{2n} = 2^{2n} $
Quindi, essendo $ S_{2n} = 2^{4n} $ si ha che $ 2^{4n}+1 \equiv 16^n+1 \equiv 2 \mod{3} $
Aspetto conferme per postare u altro problema...
Re: Staffetta tdn
Peccato che $ \displaystyle S_n=\sum _{k=0} ^n {\binom n k}^2=\binom {2n} n $
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: Staffetta tdn
Per chiarirlo definitivamente, il problema in realtà chiede di mostrare:
$3\nmid \binom{4n}{2n}+1$
$3\nmid \binom{4n}{2n}+1$
...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: 358
- Iscritto il: 31 lug 2010, 10:35
Re: Staffetta tdn
Mi sembra semplice...dario2994 ha scritto:Per chiarirlo definitivamente, il problema in realtà chiede di mostrare:
$3\nmid \binom{4n}{2n}+1$
Verifico a mano il caso $n=1$ $\binom{4}{2}=6$
Negli altri casi poiché il numeratore si semplifica col denominatore (il binomiale è sempre intero) e ha almeno 3 fattori (consecutivi) in più del denominatore, uno dei tre fattori è divisibile per tre quindi il binomiale è divisibile.
Da qui la tesi.
E' corretto?
Re: Staffetta tdn
Ehm... $\binom{8}{4} = 70$, che non è esattamente multiplo di 3...
Re: Staffetta tdn
Non hai considerato che anche al denominatore ci sono fattori 3...
Re: Staffetta tdn
Lucas' theorem (piazzo come l'ho dimostrato perchè personalmente prima di affrontare questo problema non l'avevo mai usato e non ne conoscevo la dimostrazione):
Dati $a\ge b$ interi positivi che si scrivono in base $p$ primo (accettabili le cifre 0 all'inizio) come $a_ka_{k-1}\dots a_1a_0$ e $b_kb_{k-1}b_{k-2}\dots b_1b_0$ allora
$\displaystyle\binom{a}{b}\equiv\prod_{i=0}^k\binom{a_i}{b_i}\pmod p$
Fatto I: Se $b=1$ è vero
Ovvio
Fatto II: Se $x,y$ sono interi non negativi minori di $p$ allora $\binom{pa+x}{pb+y}\equiv \binom{pa}{pb}\binom{x}{y}\pmod p$
Se $x\ge y$:
$\displaystyle \binom{pa+x}{pb+y}= \binom{pa}{pb}\frac{\prod_{i=1}^x(pa+i)}{\prod_{i=1}^y(pb+i)\prod_{i=1}^{y-x}(p(a-b)+i)}\equiv \binom{pa}{pb}\frac{\prod_{i=1}^xi}{\prod_{i=1}^yi\prod_{i=1}^{x-y}i}=\binom{pa}{pb}\binom{x}{y}\pmod{p}$
Se $x<y$ il fatto equivale a dimostrare che $\displaystyle p|\binom{pa+x}{pa+y}$ (dato che $\binom{x}{y}$ sarebbe nullo):
$\displaystyle \binom{pa+x}{pa+y}=\binom{pa}{pb}\frac{\prod_{i=1}^x(pa+i)\prod_{i=0}^{x-y-1}(p(a-b)-i)}{\prod_{i=1}^y(pb+i)}=p\binom{pa}{pb}\frac{(a-b)\prod_{i=1}^x(pa+i)\prod_{i=1}^{x-y-1}(p(a-b)-i)}{\prod_{i=1}^y(pb+i)}\equiv 0\pmod p$
Fatto III: $\displaystyle\binom{pa}{pb}\equiv \binom{a}{b}\pmod p$
$\displaystyle \binom{pa}{pb}= \frac{\prod_{i=1}^b\left(p(a+1-i)\prod_{j=1}^{p-1}(p(a+1-i)-j)\right)}{\prod_{i=1}^b\left(p(b-i)\prod_{j=1}^{p-1}(p(b-i)-j)\right)}=\frac{\prod_{i=1}^bp(a+1-i)}{\prod_{i=1}^bp(b-i)}\cdot \frac{\prod_{i=1}^b(p-1)!}{\prod_{i=1}^b(p-1)!}\equiv \binom{a}{b}\pmod p$
Usando i vari fatti mostrati il teorema segue per induzione sul numero di cifre di b (senza zeri all'inizio):
Passo base: È il fatto I
Passo induttivo: Usando i fatti II e III vale
$\displaystyle\binom{a_ka_{k-1}\dots a_1a_0}{b_kb_{k-1}\dots b_1b_0}\equiv \binom{a_ka_{k-1}\dots a_10}{b_kb_{k-1}\dots b_10}\binom{a_0}{b_0}\equiv \binom{a_ka_{k-1}\dots a_1}{b_kb_{k-1}\dots b_1}\binom{a_0}{b_0}\pmod p$
Ma dato che $b_kb_{k-1}\dots b_1$ ha meno cifre di $b_kb_{k-1}\dots b_0$ posso usare l'ipotesi induttiva e ottenere quindi la tesi.
Bon ora passo al problema: $3\nmid \binom{4n}{2n}+1$
Caso I: 2n ha almeno una cifra "2" in base 3
Considero la prima cifra 2 presente in 2n... allora la corrispettiva presente in 4n sarà 1 (ovvio) quindi per il teorema di Lucas:
$\displaystyle\binom{4n}{2n}\equiv (QUALCOSA)\cdot \binom{1}{2}=0 \pmod 3\Rightarrow 3\nmid \binom{4n}{2n}+1$
Caso II: 2n ha tutte cifre 0 e 1
Le cifre di 2n in base 3 sono: $x_kx_{k-1}\dots x_1x_0$ e quelle di 4n risultano $(2x_k)(2x_{k-1})\dots (2x_1)(2x_0)$ (dato che non ci sono riporti). Per il teorema di lucas vale:
$\displaystyle\binom{4n}{2n}\equiv \prod_{i=0}^k\binom{2x_i}{a_i}$
Se chiamo z il numero di cifre 1 di 2n ottengo quindi: $\binom{4n}{2n}\equiv 2^z\pmod{3}$ ma z è pari poichè 2n lo è (la somma delle cifre ha la stessa parità del numero in base 3... è ovvio) quindi
$\displaystyle\binom{4n}{2n}\equiv 2^{2k}\equiv 1\pmod{3}\Rightarrow 3\nmid \binom{4n}{2n}+1$
p.s. data l'enorme quantità di latex sono certo di aver fatto un'altrettanto enorme quantità di errorini nelle formule... me ne scuso in anticipo
Dati $a\ge b$ interi positivi che si scrivono in base $p$ primo (accettabili le cifre 0 all'inizio) come $a_ka_{k-1}\dots a_1a_0$ e $b_kb_{k-1}b_{k-2}\dots b_1b_0$ allora
$\displaystyle\binom{a}{b}\equiv\prod_{i=0}^k\binom{a_i}{b_i}\pmod p$
Fatto I: Se $b=1$ è vero
Ovvio
Fatto II: Se $x,y$ sono interi non negativi minori di $p$ allora $\binom{pa+x}{pb+y}\equiv \binom{pa}{pb}\binom{x}{y}\pmod p$
Se $x\ge y$:
$\displaystyle \binom{pa+x}{pb+y}= \binom{pa}{pb}\frac{\prod_{i=1}^x(pa+i)}{\prod_{i=1}^y(pb+i)\prod_{i=1}^{y-x}(p(a-b)+i)}\equiv \binom{pa}{pb}\frac{\prod_{i=1}^xi}{\prod_{i=1}^yi\prod_{i=1}^{x-y}i}=\binom{pa}{pb}\binom{x}{y}\pmod{p}$
Se $x<y$ il fatto equivale a dimostrare che $\displaystyle p|\binom{pa+x}{pa+y}$ (dato che $\binom{x}{y}$ sarebbe nullo):
$\displaystyle \binom{pa+x}{pa+y}=\binom{pa}{pb}\frac{\prod_{i=1}^x(pa+i)\prod_{i=0}^{x-y-1}(p(a-b)-i)}{\prod_{i=1}^y(pb+i)}=p\binom{pa}{pb}\frac{(a-b)\prod_{i=1}^x(pa+i)\prod_{i=1}^{x-y-1}(p(a-b)-i)}{\prod_{i=1}^y(pb+i)}\equiv 0\pmod p$
Fatto III: $\displaystyle\binom{pa}{pb}\equiv \binom{a}{b}\pmod p$
$\displaystyle \binom{pa}{pb}= \frac{\prod_{i=1}^b\left(p(a+1-i)\prod_{j=1}^{p-1}(p(a+1-i)-j)\right)}{\prod_{i=1}^b\left(p(b-i)\prod_{j=1}^{p-1}(p(b-i)-j)\right)}=\frac{\prod_{i=1}^bp(a+1-i)}{\prod_{i=1}^bp(b-i)}\cdot \frac{\prod_{i=1}^b(p-1)!}{\prod_{i=1}^b(p-1)!}\equiv \binom{a}{b}\pmod p$
Usando i vari fatti mostrati il teorema segue per induzione sul numero di cifre di b (senza zeri all'inizio):
Passo base: È il fatto I
Passo induttivo: Usando i fatti II e III vale
$\displaystyle\binom{a_ka_{k-1}\dots a_1a_0}{b_kb_{k-1}\dots b_1b_0}\equiv \binom{a_ka_{k-1}\dots a_10}{b_kb_{k-1}\dots b_10}\binom{a_0}{b_0}\equiv \binom{a_ka_{k-1}\dots a_1}{b_kb_{k-1}\dots b_1}\binom{a_0}{b_0}\pmod p$
Ma dato che $b_kb_{k-1}\dots b_1$ ha meno cifre di $b_kb_{k-1}\dots b_0$ posso usare l'ipotesi induttiva e ottenere quindi la tesi.
Bon ora passo al problema: $3\nmid \binom{4n}{2n}+1$
Caso I: 2n ha almeno una cifra "2" in base 3
Considero la prima cifra 2 presente in 2n... allora la corrispettiva presente in 4n sarà 1 (ovvio) quindi per il teorema di Lucas:
$\displaystyle\binom{4n}{2n}\equiv (QUALCOSA)\cdot \binom{1}{2}=0 \pmod 3\Rightarrow 3\nmid \binom{4n}{2n}+1$
Caso II: 2n ha tutte cifre 0 e 1
Le cifre di 2n in base 3 sono: $x_kx_{k-1}\dots x_1x_0$ e quelle di 4n risultano $(2x_k)(2x_{k-1})\dots (2x_1)(2x_0)$ (dato che non ci sono riporti). Per il teorema di lucas vale:
$\displaystyle\binom{4n}{2n}\equiv \prod_{i=0}^k\binom{2x_i}{a_i}$
Se chiamo z il numero di cifre 1 di 2n ottengo quindi: $\binom{4n}{2n}\equiv 2^z\pmod{3}$ ma z è pari poichè 2n lo è (la somma delle cifre ha la stessa parità del numero in base 3... è ovvio) quindi
$\displaystyle\binom{4n}{2n}\equiv 2^{2k}\equiv 1\pmod{3}\Rightarrow 3\nmid \binom{4n}{2n}+1$
p.s. data l'enorme quantità di latex sono certo di aver fatto un'altrettanto enorme quantità di errorini nelle formule... me ne scuso in anticipo
...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
Re: Staffetta tdn
Problema 83:
Sia $n$ un intero positivo libero da cubi (cioè nella sua fattorizzazione gli esponenti sono solo 1,2). Sia $P(x)$ un polinomio a coefficienti interi, definisco $f(P)$ la $n$-upla $(P(0)\pmod n,P(1)\pmod n,\dots ,P(n-1)\pmod n)$ di interi non negativi minori di $n$.
Quanto vale $|\{f(P):\ P(x)\in \mathbb{Z[x]}\}|$ ?
p.s. volevo fare i complimenti (un poco in ritardo...) a kn per il problema che ha postato qui mesi fa: $\displaystyle p^3\mid \binom{pa}{pb}-\binom{a}{b}$ è bellissimo Ma da dove l'hai preso? edit: trovato da me la fonte: Wolstenholme's theorem
Sia $n$ un intero positivo libero da cubi (cioè nella sua fattorizzazione gli esponenti sono solo 1,2). Sia $P(x)$ un polinomio a coefficienti interi, definisco $f(P)$ la $n$-upla $(P(0)\pmod n,P(1)\pmod n,\dots ,P(n-1)\pmod n)$ di interi non negativi minori di $n$.
Quanto vale $|\{f(P):\ P(x)\in \mathbb{Z[x]}\}|$ ?
p.s. volevo fare i complimenti (un poco in ritardo...) a kn per il problema che ha postato qui mesi fa: $\displaystyle p^3\mid \binom{pa}{pb}-\binom{a}{b}$ è bellissimo Ma da dove l'hai preso? edit: trovato da me la fonte: Wolstenholme's theorem
...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: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: Staffetta tdn
Anche il tuo è interessante
Allora mettiamo che $ \displaystyle~n=\prod_{k=1}^m p_k^{a_k} $ sia la fattorizzazione di n.
Mi viene una cosa come $ \displaystyle~\prod_{k=1}^m p_k^{\displaystyle\frac{p_k a_k(a_k+1)}{2}} $.. è giusto
Allora mettiamo che $ \displaystyle~n=\prod_{k=1}^m p_k^{a_k} $ sia la fattorizzazione di n.
Mi viene una cosa come $ \displaystyle~\prod_{k=1}^m p_k^{\displaystyle\frac{p_k a_k(a_k+1)}{2}} $.. è giusto
Re: Staffetta tdn
Sisi è giusto ma lo devi dimostrare
...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: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: Staffetta tdn
No, temo sia falso chiedo scusa a tutti (per n=16 a occhio $ \displaystyle~|\{f(P)\}|=2^{8+6+2}=2^{16} $)
Domani penso a come si può aggiustare il risultato
Domani penso a come si può aggiustare il risultato
Re: Staffetta tdn
Non ho capito molto... comunque era giusto e non puoi porre n=16 dato che deve essere libero da cubi.Nabir Albar ha scritto:No, temo sia falso chiedo scusa a tutti (per n=16 a occhio $ \displaystyle~|\{f(P)\}|=2^{8+6+2}=2^{16} $)
Domani penso a come si può aggiustare il risultato
...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: 62
- Iscritto il: 22 nov 2010, 19:09
- Località: Sto ca... Stoccarda!
Re: Staffetta tdn
Mi ero dimenticato di questa ipotesi.. Visto che avevo già cominciato a scrivere la soluzione, dimostro che vale quel risultato se $ \displaystyle~a_k\le p_k $ per ogni k (quindi funziona anche con $ \displaystyle~a_k\le 2 $).
Intanto chiamiamo $ \displaystyle~g(P,n) $ la n-upla $ (P(0)\pmod n,\ P(1)\pmod n,\ \dots ,\ P(n-1)\pmod n) $.
Per cominciare riduciamoci al caso in cui n è potenza di primo, cioè dimostriamo che $ \displaystyle~|\{g(P,n)\}|=\prod_{k=1}^m |\{g(P,p_k^{a_k})\}| $.
Questa tesi preliminare equivale a mostrare che c'è un'associazione biunivoca tra gli elementi di $ \displaystyle~\{g(P,n)\} $ e quelli di $ \displaystyle~\{g(P,p_1^{a_1})\}\times\{g(P,p_2^{a_2})\}\times\dots\times\{g(P,p_m^{a_m})\} $. Presa quindi una n-upla $ \displaystyle~(a_1,a_2,\dots,a_n) $ del primo insieme, considero $ (a_1\pmod{p_k^{a_k}},\ a_2\pmod{p_k^{a_k}},\ \dots,\ a_{p_k^{a_k}}\pmod{p_k^{a_k}})\in\{g(P,p_k^{a_k})\} $ per ogni k, ottenendo un elemento del prodotto cartesiano.
Viceversa, a partire da m $ \displaystyle~p_k^{a_k} $-uple appartenenti ognuna al suo $ \displaystyle~\{g(P,p_k^{a_k})\} $, abbiamo per come sono definiti gli insiemi che ognuna è generata da un certo polinomio $ \displaystyle~P_k(x) $. Considero adesso il polinomio $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x) $, essendo $ z_i\equiv\left(\prod_{j\neq i} p_j^{a_j}\right)^{-1}\pmod{p_i^{a_i}} $. Allora $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x)=\sum_{i\neq k} \prod_{j\neq i} p_j^{a_j} z_i P_i(x)+\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv P_k(x)\pmod{p_k^{a_k}} $ per ogni k, essendo divisibili per $ \displaystyle~p_k^{a_k} $ tutti i termini dell'ultima sommatoria. Quindi $ (P(0)\pmod{p_k^{a_k}},\ P(1)\pmod{p_k^{a_k}},\ \dots,\ P(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $ è proprio $ (P_k(0)\pmod{p_k^{a_k}},\ P_k(1)\pmod{p_k^{a_k}},\ \dots,\ P_k(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $, cioè la nostra associazione è sicuramente biunivoca.
Detto questo, passiamo a far vedere che $ \displaystyle~|\{g(P,p^a)\}|=p^\frac{pa(a+1)}{2} $ e avremo finito.
$ \displaystyle~|\{g(P,p^a)\}| $ è il numero di "funzioni polinomiali" $ \displaystyle~\pmod p^a $, quindi occorre capire quando due polinomi $ \displaystyle~P(x),P'(x) $ assumono gli stessi valori, ovvero quando $ \displaystyle~P(x)-P'(x) $ è la funzione che trasforma tutto in 0 $ \displaystyle~\pmod p^a $.
Consideriamo $ \displaystyle~a $ p-uple $ \displaystyle~(a_{k,0},a_{k,1},\dots,a_{k,p-1}) $ in modo che $ \displaystyle~a_{k,j}\equiv j\pmod p $ (per ogni j e k) ma allo stesso tempo anche $ \displaystyle~a_{k,j}\not\equiv a_{k',j}\pmod{p^2} $ (per ogni k, j e $ \displaystyle~j'\neq j $). Esistono: per esempio possiamo prendere $ \displaystyle~a_{k,j}=(k-1)p+j $.
Dato un polinomio $ \displaystyle~Q(x) $ tale che $ \displaystyle~\forall x\quad Q(x)\equiv0\pmod{p^a} $, abbiamo $ \displaystyle~Q(a_{1,0})\equiv0\pmod{p^a} $, quindi per Ruffini $ \displaystyle~Q(x)=(x-a_{1,0})Q'(x)+p^aRoba(x) $. Essendo $ \displaystyle~Q(a_{1,1})\equiv(a_{1,1}-a_{1,0})Q'(x)\equiv0\pmod{p^a} $, possiamo ancora dividere $ \displaystyle~Q(x) $ per $ \displaystyle~(x-a_{1,1}) $. Continuando a dividere (possiamo perché $ \displaystyle~a_{k,j}-a_{k,j'} $ è sempre invertibile), arriviamo a $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})Q_1(x)+p^aR_0(x) $ per certi polinomi $ \displaystyle~Q_1(x) $ e $ \displaystyle~R_0(x) $ ($ \displaystyle~R_0(x) $ ha grado minore di p).
Sostituendo ora a x i vari $ \displaystyle~a_{2,j} $ otteniamo che $ \displaystyle~\prod_{j=0}^{p-1}(x-a_{1,j}) $ ha esattamente un fattore $ \displaystyle~p $, quindi $ \displaystyle~Q_1(a_{2,j})\equiv0\pmod{p^{a-1}} $ per ogni j e di nuovo possiamo dividere ottenendo $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})\prod_{j=0}^{p-1}(x-a_{2,j})Q_2(x)+p^{a-1}\prod_{j=0}^{p-1}(x-a_{1,j})R_1(x)+p^aR_0(x) $.
Ripetendo il ragionamento con tutte le p-uple arriviamo infine al seguente mostro:
$ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $.
Viceversa è facile vedere che ogni $ \displaystyle~Q(x) $ del genere, al variare dei polinomi $ \displaystyle~R_i(x) $, è sempre nullo considerato come funzione:
A questo punto le funzioni polinomiali $ \displaystyle~\pmod{p^a} $ sono al massimo il numero di polinomi di questo tipo, che è proprio $ \displaystyle~(p^a)^p(p^{a-1})^p\cdots p^p=p^{p(1+2+\dots+(a-1)+a)}=p^\frac{pa(a+1)}{2} $.
Ma in effetti se per assurdo due polinomi distinti $ \displaystyle~P(x),P'(x) $ di questo tipo fossero uguali come funzioni avremmo che $ \displaystyle~P(x)-P'(x)=\sum_{i=0}^{pa-1}(c_i-c_i')x^i $ sarebbe della forma $ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $, ma è facile vedere che $ \displaystyle~|c_i-c_i'|<p^k (*) $ (per $ \displaystyle~kp\le i<(k+1)p $ e per ogni k). Dunque, chiamando N il più grande $ \displaystyle~i $ tale che $ \displaystyle~R_i(x)\neq 0 $, notando che i polinomi $ \displaystyle~p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $ hanno grado minore di $ \displaystyle~pi+p<pN $ per $ \displaystyle~i<N $ e che $ \displaystyle~p^{a-N}\prod_{k=1}^N\prod_{j=0}^{p-1}(x-a_{k,j})R_N(x) $ ha grado $ \displaystyle~\ge pN $, il termine di grado massimo di $ \displaystyle~Q(x) $ appartiene a quest'ultimo e ha quindi coefficiente non nullo e multiplo di $ \displaystyle~p^{a-N} $. Ma questo coefficiente è $ \displaystyle~c_i-c_i' $ per qualche $ \displaystyle~i\ge pN $, assurdo per la $ \displaystyle~(*) $.
Chiedo scusa per la dimostrazione prolissa e per la notazione complicata e aspetto conferme..
Intanto chiamiamo $ \displaystyle~g(P,n) $ la n-upla $ (P(0)\pmod n,\ P(1)\pmod n,\ \dots ,\ P(n-1)\pmod n) $.
Per cominciare riduciamoci al caso in cui n è potenza di primo, cioè dimostriamo che $ \displaystyle~|\{g(P,n)\}|=\prod_{k=1}^m |\{g(P,p_k^{a_k})\}| $.
Questa tesi preliminare equivale a mostrare che c'è un'associazione biunivoca tra gli elementi di $ \displaystyle~\{g(P,n)\} $ e quelli di $ \displaystyle~\{g(P,p_1^{a_1})\}\times\{g(P,p_2^{a_2})\}\times\dots\times\{g(P,p_m^{a_m})\} $. Presa quindi una n-upla $ \displaystyle~(a_1,a_2,\dots,a_n) $ del primo insieme, considero $ (a_1\pmod{p_k^{a_k}},\ a_2\pmod{p_k^{a_k}},\ \dots,\ a_{p_k^{a_k}}\pmod{p_k^{a_k}})\in\{g(P,p_k^{a_k})\} $ per ogni k, ottenendo un elemento del prodotto cartesiano.
Viceversa, a partire da m $ \displaystyle~p_k^{a_k} $-uple appartenenti ognuna al suo $ \displaystyle~\{g(P,p_k^{a_k})\} $, abbiamo per come sono definiti gli insiemi che ognuna è generata da un certo polinomio $ \displaystyle~P_k(x) $. Considero adesso il polinomio $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x) $, essendo $ z_i\equiv\left(\prod_{j\neq i} p_j^{a_j}\right)^{-1}\pmod{p_i^{a_i}} $. Allora $ \displaystyle~P(x)=\sum_{i=1}^m \prod_{j\neq i} p_j^{a_j} z_i P_i(x)=\sum_{i\neq k} \prod_{j\neq i} p_j^{a_j} z_i P_i(x)+\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv\prod_{j\neq k} p_j^{a_j} z_k P_k(x)\equiv P_k(x)\pmod{p_k^{a_k}} $ per ogni k, essendo divisibili per $ \displaystyle~p_k^{a_k} $ tutti i termini dell'ultima sommatoria. Quindi $ (P(0)\pmod{p_k^{a_k}},\ P(1)\pmod{p_k^{a_k}},\ \dots,\ P(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $ è proprio $ (P_k(0)\pmod{p_k^{a_k}},\ P_k(1)\pmod{p_k^{a_k}},\ \dots,\ P_k(p_k^{a_k}-1)\pmod{p_k^{a_k}}\}) $, cioè la nostra associazione è sicuramente biunivoca.
Detto questo, passiamo a far vedere che $ \displaystyle~|\{g(P,p^a)\}|=p^\frac{pa(a+1)}{2} $ e avremo finito.
$ \displaystyle~|\{g(P,p^a)\}| $ è il numero di "funzioni polinomiali" $ \displaystyle~\pmod p^a $, quindi occorre capire quando due polinomi $ \displaystyle~P(x),P'(x) $ assumono gli stessi valori, ovvero quando $ \displaystyle~P(x)-P'(x) $ è la funzione che trasforma tutto in 0 $ \displaystyle~\pmod p^a $.
Consideriamo $ \displaystyle~a $ p-uple $ \displaystyle~(a_{k,0},a_{k,1},\dots,a_{k,p-1}) $ in modo che $ \displaystyle~a_{k,j}\equiv j\pmod p $ (per ogni j e k) ma allo stesso tempo anche $ \displaystyle~a_{k,j}\not\equiv a_{k',j}\pmod{p^2} $ (per ogni k, j e $ \displaystyle~j'\neq j $). Esistono: per esempio possiamo prendere $ \displaystyle~a_{k,j}=(k-1)p+j $.
Dato un polinomio $ \displaystyle~Q(x) $ tale che $ \displaystyle~\forall x\quad Q(x)\equiv0\pmod{p^a} $, abbiamo $ \displaystyle~Q(a_{1,0})\equiv0\pmod{p^a} $, quindi per Ruffini $ \displaystyle~Q(x)=(x-a_{1,0})Q'(x)+p^aRoba(x) $. Essendo $ \displaystyle~Q(a_{1,1})\equiv(a_{1,1}-a_{1,0})Q'(x)\equiv0\pmod{p^a} $, possiamo ancora dividere $ \displaystyle~Q(x) $ per $ \displaystyle~(x-a_{1,1}) $. Continuando a dividere (possiamo perché $ \displaystyle~a_{k,j}-a_{k,j'} $ è sempre invertibile), arriviamo a $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})Q_1(x)+p^aR_0(x) $ per certi polinomi $ \displaystyle~Q_1(x) $ e $ \displaystyle~R_0(x) $ ($ \displaystyle~R_0(x) $ ha grado minore di p).
Sostituendo ora a x i vari $ \displaystyle~a_{2,j} $ otteniamo che $ \displaystyle~\prod_{j=0}^{p-1}(x-a_{1,j}) $ ha esattamente un fattore $ \displaystyle~p $, quindi $ \displaystyle~Q_1(a_{2,j})\equiv0\pmod{p^{a-1}} $ per ogni j e di nuovo possiamo dividere ottenendo $ \displaystyle~Q(x)=\prod_{j=0}^{p-1}(x-a_{1,j})\prod_{j=0}^{p-1}(x-a_{2,j})Q_2(x)+p^{a-1}\prod_{j=0}^{p-1}(x-a_{1,j})R_1(x)+p^aR_0(x) $.
Ripetendo il ragionamento con tutte le p-uple arriviamo infine al seguente mostro:
$ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $.
Viceversa è facile vedere che ogni $ \displaystyle~Q(x) $ del genere, al variare dei polinomi $ \displaystyle~R_i(x) $, è sempre nullo considerato come funzione:
- per $ \displaystyle~R_a(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq a $ otteniamo il polinomio $ \displaystyle~S_a(x)=\prod_{k=1}^a\prod_{j=0}^{p-1}(x-a_{k,j}) $, monico e di grado $ \displaystyle~pa $;
- per $ \displaystyle~R_{a-1}(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq a-1 $ otteniamo $ \displaystyle~S_{a-1}(x)=p\prod_{k=1}^{a-1}\prod_{j=0}^{p-1}(x-a_{k,j}) $, con coeff. direttivo $ \displaystyle~p $ e di grado $ \displaystyle~p(a-1) $;
- ...
- per $ \displaystyle~R_1(x)=1 $ e $ \displaystyle~R_i(x)=0 $ per ogni $ \displaystyle~i\neq 1 $ si ha $ \displaystyle~S_1(x)=p^{a-1}\prod_{j=0}^{p-1}(x-a_{1,j}) $, con coeff. direttivo $ \displaystyle~p^{a-1} $ e di grado $ \displaystyle~p $.
A questo punto le funzioni polinomiali $ \displaystyle~\pmod{p^a} $ sono al massimo il numero di polinomi di questo tipo, che è proprio $ \displaystyle~(p^a)^p(p^{a-1})^p\cdots p^p=p^{p(1+2+\dots+(a-1)+a)}=p^\frac{pa(a+1)}{2} $.
Ma in effetti se per assurdo due polinomi distinti $ \displaystyle~P(x),P'(x) $ di questo tipo fossero uguali come funzioni avremmo che $ \displaystyle~P(x)-P'(x)=\sum_{i=0}^{pa-1}(c_i-c_i')x^i $ sarebbe della forma $ \displaystyle~Q(x)=\sum_{i=0}^a p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $, ma è facile vedere che $ \displaystyle~|c_i-c_i'|<p^k (*) $ (per $ \displaystyle~kp\le i<(k+1)p $ e per ogni k). Dunque, chiamando N il più grande $ \displaystyle~i $ tale che $ \displaystyle~R_i(x)\neq 0 $, notando che i polinomi $ \displaystyle~p^{a-i}\prod_{k=1}^i\prod_{j=0}^{p-1}(x-a_{k,j})R_i(x) $ hanno grado minore di $ \displaystyle~pi+p<pN $ per $ \displaystyle~i<N $ e che $ \displaystyle~p^{a-N}\prod_{k=1}^N\prod_{j=0}^{p-1}(x-a_{k,j})R_N(x) $ ha grado $ \displaystyle~\ge pN $, il termine di grado massimo di $ \displaystyle~Q(x) $ appartiene a quest'ultimo e ha quindi coefficiente non nullo e multiplo di $ \displaystyle~p^{a-N} $. Ma questo coefficiente è $ \displaystyle~c_i-c_i' $ per qualche $ \displaystyle~i\ge pN $, assurdo per la $ \displaystyle~(*) $.
Chiedo scusa per la dimostrazione prolissa e per la notazione complicata e aspetto conferme..
Re: Staffetta tdn
Alur... prima di tutto ti odio Non si capisce una mazza
Il modo in cui ti riconduci alle potenze di primo mi pare scontato dire che non l'ho letto (ma penso di capire da quelle somma-produttorie cosa stai facendo ) ... ma ho piena fiducia quindi ok (tra l'altro in quel punto hai piazzato una delle latexate più complicate che abbia mai visto )
Ora torniamo a pensare a quando gli esponenti sono minori o uguali a 2... in particolare quando sono 2 (se è 1 è palese che i polinomi sono $p^p$). (evitami il caso generale che non si capisce una ceppa)
Quanti sono i polinomi $\pmod {p^2}$? Tu parti bene cercando i polinomi nulli, poi non ho ancora letto ma risulta inquietante
Facciamo così... non è che mi riscrivi quali sono per te i polinomi nulli $\pmod {p^2}$?
Una volta che hai trovato i polinomi nulli cerchi quindi di contare i polinomi (sfrutti il fatto che se 2 sono uguali allora la differenza è uno di quei polinomi) e penso che ci riesci alla grande.
Insomma l'unica cosa che vorrei vedere meglio (perchè sono un rompipalle) sono i polinomi nulli $\pmod{ p^2}$ poi per me va bene, se qualcuno becca errori lo dicesse.
Direi che come ragionamento fila, peccato che dato che hai risolto un caso più generale (e mi complimento) non si capisce (o perlomeno io non ho voglia di leggermi tutte quelle somma-produttorie ).
p.s. rileggendo con più calma la tua soluzione mi sembra tutto giusto, ma per chiarezza scrivi comunque i polinomi nulli in p^2... poi posta il nuovo problema
Il modo in cui ti riconduci alle potenze di primo mi pare scontato dire che non l'ho letto (ma penso di capire da quelle somma-produttorie cosa stai facendo ) ... ma ho piena fiducia quindi ok (tra l'altro in quel punto hai piazzato una delle latexate più complicate che abbia mai visto )
Ora torniamo a pensare a quando gli esponenti sono minori o uguali a 2... in particolare quando sono 2 (se è 1 è palese che i polinomi sono $p^p$). (evitami il caso generale che non si capisce una ceppa)
Quanti sono i polinomi $\pmod {p^2}$? Tu parti bene cercando i polinomi nulli, poi non ho ancora letto ma risulta inquietante
Facciamo così... non è che mi riscrivi quali sono per te i polinomi nulli $\pmod {p^2}$?
Una volta che hai trovato i polinomi nulli cerchi quindi di contare i polinomi (sfrutti il fatto che se 2 sono uguali allora la differenza è uno di quei polinomi) e penso che ci riesci alla grande.
Insomma l'unica cosa che vorrei vedere meglio (perchè sono un rompipalle) sono i polinomi nulli $\pmod{ p^2}$ poi per me va bene, se qualcuno becca errori lo dicesse.
Direi che come ragionamento fila, peccato che dato che hai risolto un caso più generale (e mi complimento) non si capisce (o perlomeno io non ho voglia di leggermi tutte quelle somma-produttorie ).
p.s. rileggendo con più calma la tua soluzione mi sembra tutto giusto, ma per chiarezza scrivi comunque i polinomi nulli in p^2... poi posta il nuovo problema
...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