Pagina 28 di 33

Re: Staffetta tdn

Inviato: 26 nov 2010, 00:04
da Federiko
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.

Re: Staffetta tdn

Inviato: 26 nov 2010, 14:54
da minima.distanza
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...

Re: Staffetta tdn

Inviato: 26 nov 2010, 15:47
da <enigma>
Peccato che $ \displaystyle S_n=\sum _{k=0} ^n {\binom n k}^2=\binom {2n} n $ :?

Re: Staffetta tdn

Inviato: 26 nov 2010, 15:49
da dario2994
Per chiarirlo definitivamente, il problema in realtà chiede di mostrare:
$3\nmid \binom{4n}{2n}+1$

Re: Staffetta tdn

Inviato: 26 nov 2010, 21:07
da paga92aren
dario2994 ha scritto:Per chiarirlo definitivamente, il problema in realtà chiede di mostrare:
$3\nmid \binom{4n}{2n}+1$
Mi sembra semplice...
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

Inviato: 26 nov 2010, 22:39
da sasha™
Ehm... $\binom{8}{4} = 70$, che non è esattamente multiplo di 3...

Re: Staffetta tdn

Inviato: 27 nov 2010, 14:16
da Euler
Non hai considerato che anche al denominatore ci sono fattori 3...

Re: Staffetta tdn

Inviato: 27 nov 2010, 17:44
da dario2994
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

Re: Staffetta tdn

Inviato: 28 nov 2010, 10:24
da dario2994
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 :)

Re: Staffetta tdn

Inviato: 05 dic 2010, 11:51
da Nabir Albar
Anche il tuo è interessante :D
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

Inviato: 05 dic 2010, 13:04
da dario2994
Sisi è giusto ma lo devi dimostrare :wink:

Re: Staffetta tdn

Inviato: 05 dic 2010, 22:39
da Nabir Albar
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 :oops:

Re: Staffetta tdn

Inviato: 05 dic 2010, 22:42
da dario2994
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 :oops:
Non ho capito molto... comunque era giusto e non puoi porre n=16 dato che deve essere libero da cubi.

Re: Staffetta tdn

Inviato: 06 dic 2010, 20:22
da Nabir Albar
Mi ero dimenticato di questa ipotesi.. :oops: 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:
  • 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 $.
Con questi polinomi "nulli" particolari, possiamo ridurre un polinomio $ \displaystyle~P(x)=\sum_{i=0}^d c_i x^i $ qualsiasi a uno identico come funzione ma di grado minore di $ \displaystyle~pa $ (togliendo un opportuno multiplo di $ \displaystyle~S_a(x) $) e con i coefficienti che rispettano le condizioni $ \displaystyle~0\le c_i<p^{a-k} $ per ogni $ \displaystyle~kp\le i<(k+1)p $ e per ogni k (aggiustando i coefficienti dal grado più alto fino a $ \displaystyle~c_0 $, togliendo un opportuno multiplo di $ \displaystyle~x^{i-kp}S_k(x) $ per $ \displaystyle~kp\le i<(k+1)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

Inviato: 06 dic 2010, 21:20
da dario2994
Alur... prima di tutto ti odio :twisted: 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 :roll: (tra l'altro in quel punto hai piazzato una delle latexate più complicate che abbia mai visto :shock: )
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 :oops: ).

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