[SNS 05-06, es.1] Soluzioni di un sistema

[gismondo]

Salve, spero che questo problema non sia stato già postato, in tal caso mi scuso...

$ 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 $
2. Si supponga di scegliere a caso $ a, b, c, d, e, f $ tra gli interi relativi con valore assoluto minore o uguale a un intero positivo $ n $ prefissato.
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} $

Grazie

[pak-man]

Punto 1.
Possiamo riscrivere il sistema in forma matriciale come

$ \left[\begin{array}{ll}a&b\\c&d\end{array}\right]\left[\begin{array}{c}x\\y\end{array}\right]=\left[\begin{array}{c}e\\f\end{array}\right] $

Chiamando $ C $ la matrice dei coefficienti, $ X $ la matrice delle incognite e $ T $ la matrice dei termini noti, possiamo scrivere $ C\cdot X=T $. Dunque se $ |C|\ne0 $, ovvero se $ ad\ne bc $, esiste un'unica soluzione $ X=C^{-1}T $, altrimenti ne esistono $ \infty^1 $ (quando $ (a,b,e)=k(c,d,f) $) o nessuna (quando $ (a,b)=k(c,d) $ e $ e\ne kf $)

Per il punto 2 ci devo pensare...

[gismondo]

Qualcuno per il punto due?

[jordan]

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

$ 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 $

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 $.

[Tibor Gallai]

viewtopic.php?t=4825

[jordan]

Anche se l'avessi trovata non l'avrei di certo letta scritta cosi..

[gismondo]

Complimenti per la soluzione, chiara e precisa.

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.

Potresti spiegare come fai ad esser certo che il lower bound per q(n) sia quello?
(ho corretto l'errore di segno)

[jordan]

Potresti spiegare come fai ad esser certo che il lower bound per q(n) sia quello?

Quando calcoli q(n) dovrai mettere per forza il caso in cui ab=cd=0, che ne sono $ (4n+1)^2 $. Assumendo adesso che tutte le variabili siano non nulle e in modulo non maggiori di n, abbiamo che nel calcolo di q(n) ci sarà sicuramente anche il caso in cui ab=cd con a=c oppure a=-c (in questo modo le variabili libere tra le (2n) possibilità sono a e b per cui $ 2 \cdot(2n)^2 $ possibilità); c'è anche il caso in cui a=d oppure a=-d (imponendo che a e |c| siano diversi possiamo stare sicuri di non averle già contate). In questo modo a può essere scelto tra (2n) valori e c può essere scelto tra (2n-2) valori..di conseguenza $ \displaystyle (4n+1)^2+2(2n)^2+4n(2n-2) \le q(n) $,spero sia più chiaro

[Davide90]

Complimenti a Jordan per la soluzione!
Per il lower bound poteva in teoria già bastare il conto dei casi in cui ab=cd=0, infatti
$ \dfrac{(4n+1)^2}{82n+1)^4}\geq\dfrac{1}{3n^2} $
porta a $ 32n^4\geq 8n^3+21n^2+8n+1 $ che per $ n>2 $ è sempre vera (si vede che per n=1 è falsa, per n=2 è vera, poi si dovrebbe mostrare bene che il LHS cresce molto più in fretta del RHS). Il caso n=1 era già fatto a mano prima, quindi siamo a posto.

Però il conto che hai fatto tu con tutti e tre i casi semplifica molto i calcoli, e senza dubbio è la strada più conveniente...