gismondo ha scritto:Salve, spero che questo problema non sia stato già postato, in tal caso mi scuso...
Si, è stato già postato altre volte, ma don't worry, che io mi ricordi non è stata postata una soluzione al punto 2 (o almeno non sono riuscito a trovarla..
).
gismondo ha scritto:
$ ax + by = e $
$ cx + dy = f $
1.Dimostrare che il sistema ammette una e una sola soluzione qualunque siano $ e , f $ se e solo se $ ad-bc \not= 0 $
E' sufficiente operare per sostituzione e ottenere che la soluzione $ \displaystyle (x,y)=\left( \frac{ed-bf}{ad-bc}, \frac{af-ec}{ad-bc}\right) $ esiste ed è unica se e solo se $ ad-bc \neq 0 $
gismondo ha scritto:
2. Si supponga di scegliere a caso $ (a, b, c, d, e, f) \in \mathbb{Z}^6 $ di modo tale che $ \max\{|a|,|b|,|c|,|d|,|e|,|f|\} \le n $, dove $ n \in \mathbb{N}_0 $ è fissato.
Dimostrare che la probabilità che il sistema abbia esattamente una soluzione (non necessariamente intera) è compresa tra $ 1 - \frac {1} {2n} $ e $ 1 - \frac{1} {3n^2} $
Sia $ \displaystyle p(n) \in \mathbb{Q} $ la probabilità che, fissato $ \displaystyle n \in \mathbb{N}_0 $ e scelto $ \displaystyle (a, b, c, d) \in \mathbb{Z}^4 $ sotto il vincolo $ \displaystyle \max\{|a|,|b|,|c|,|d|\} \le n $, risulti $ \displaystyle ab=cd $.
Allora la tesi del problema è equivalente a mostrare che $ \displaystyle \frac{1}{3n^2} < p(n) < \frac{1}{2n} $, infatti dal punto 1 sappiamo che la scelta di $ \displaystyle (e,f) \in \mathbb{Z}^2 $ è invariante a $ \displaystyle p(n) $ e inoltre che, sotto i vincoli sopra detti, la probabilità che si abbia $ \displaystyle ad-bc=0 $ è la stessa di quella che si abbia $ \displaystyle ab=cd $.
Definiamo $ \displaystyle (q(n),h(n)) \in \mathbb{N}_0^2 $ quegli interi positivi coprimi tra loro tali che $ \displaystyle p(n)h(n)=q(n) $, per ogni $ \displaystyle n \in \mathbb{N}_0 $. Banalmente vale $ \displaystyle h(n)=(2n+1)^4 $.
Il nostro obiettivo è ora stimare bound per $ \displaystyle q(n) $. Le possibilità per cui $ ab=cd=0 $ sono esattamente $ \displaystyle 1+4\cdot(2n)^2+4 \cdot(2n)=(4n+1)^2 $, e d'ora in poi nella stima di q(n) le variabili saranno tutte non nulle.
Utilizzando questa semplice osservazione possiamo notare che $ \displaystyle q(1)=5^2+2^2+2^2 $ e che quindi risulta verificata $ \displaystyle \frac{1}{3} < p(1)=\frac{33}{81} < \frac{1}{2} $. D'ora in poi assumiamo wlog che $ \displaystyle n \in \mathbb{N} \setminus\{0,1\} $.
Le possibilità per cui (è sempre sottointeso il vincolo $ \displaystyle \max\{|a|,|b|,|c|,|d|\} \le n $) risultano $ \displaystyle ab=cd $ e $ \displaystyle a=|c| $ sono esattamente $ \displaystyle 2 \cdot (2n)^2 $ e le possibilità per cui $ \displaystyle ab=cd, a=|d| \text{ e } a \neq |c| $ sono esattamente $ \displaystyle 2 \cdot (2n(2n-2)) $.
D'altro canto se tutte le variabili sono non tutte, se vale $ \displaystyle ab=cd $ allora una variabile sarà certamente dipendente dalle altre per cui si avranno al massimo $ \displaystyle (2n)^3 $ possibilità.
Riassumendo, abbiamo mostrato che $ \displaystyle (4n+1)^2+2(2n)^2+4n(2n-2) \le q(n) \le (4n+1)^2+(2n)^3 $ per ogni $ \displaystyle n $ intero positivo.
Lower bound. Dobbiamo mostrare che $ \displaystyle p_n=\frac{q(n)}{h(n)}>\frac{1}{3n^2} $; ma dato che $ \displaystyle q(n) \ge 32n^2+1 >32n^2 $ allora ci è sufficiente mostrare che $ \displaystyle \frac{32n^2}{(2n+1)^4} \ge \frac{1}{3n^2} $ per ogni $ \displaystyle n \ge 2 $. Ciò è equivalente a mostrare che $ \displaystyle \left(\frac{2n+1}{2n}\right)^4 \le 6 $, che è vera fin tanto che LHS è una funzione strettamente decrescente in $ n $ e $ \displaystyle \left(\frac{5}{4}\right)^4=\left(\frac{25}{16}\right)^2 <2^2<6 $.
Upper bound. Dobbiamo mostrare che $ \displaystyle p(n) < \frac{1}{2n} $, ma è vero che $ \displaystyle p(n) \le \frac{(4n+1)^2+(2n)^3}{(2n+1)^4} < \frac{1}{2n} $, infatti:
$ \displaystyle 2n(4n+1)^2+(2n)^4<(2n+1)^4 $
$ \displaystyle \leftrightarrow 2n(4n+1)^2<((2n+1)^2-(2n)^2)((2n+1)^2+(2n)^2)=(4n+1)(8n^2+4n+1) $
$ \displaystyle \leftrightarrow 2n(4n+1)<8n^2+4n+1 $, che è sempre vera per ogni $ n \ge 0 $.
