Un limite "diofantino"
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Un limite "diofantino"
EDIT: spostato in MNE, visto che c'è un limite. ma_go
Dati $a, b\in\mathbb{N}: (a, b)=1$, indichiamo con $S(n)$ il numero delle soluzioni non-negative dell'equazione
$$ax+by=n.$$
Calcolare
$$\lim_{n\to\infty} \frac{S(n)}{n}.$$
Dati $a, b\in\mathbb{N}: (a, b)=1$, indichiamo con $S(n)$ il numero delle soluzioni non-negative dell'equazione
$$ax+by=n.$$
Calcolare
$$\lim_{n\to\infty} \frac{S(n)}{n}.$$
Re: Un limite "diofantino"
In teoria (credo) l'equazione diofantea ha soluzioni solo se $ n = (a,b) $, quindi se $ n \to +\infty $ abbiamo $ S(n)=0 $ e l'intero limite va a $ 0 $. Erro? (probabile)
$Q.E.D.$
Re: Un limite "diofantino"
frod93 ha scritto:In teoria (credo) l'equazione diofantea ha soluzioni solo se $ n = (a,b) $, quindi se $ n \to +\infty $ abbiamo $ S(n)=0 $ e l'intero limite va a $ 0 $. Erro? (probabile)
Beh si.. In realtà basta che $ gcd(a, b) | n $ affinché la diofaentea abbia infinite soluzioni; ora non so cosa cambia se consideriamo solo quelle non negative; è ovvio che bisogna prendere n più grande di una certa soglia (alcuni dicono ab - a - b ma non ne sono sicuro) ma non ho idee per il momento..
ps e poi se $ S(n) \to 0 $il limite era indeterminato
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "
Re: Un limite "diofantino"
$ \frac{0}{\infty} $ non è inderetminata D:ant.py ha scritto:ps e poi se $ S(n) \to 0 $il limite era indeterminato
$Q.E.D.$
Re: Un limite "diofantino"
frod93 ha scritto:$ \frac{0}{\infty} $ non è inderetminata D:ant.py ha scritto:ps e poi se $ S(n) \to 0 $il limite era indeterminato
Ahah hai ragione scusami
Ora aspettiamo qualcuno che risolva il problema.. O magari un hint
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "
Re: Un limite "diofantino"
signori, ma proprio non sapete come addestrar codeste bestie?
Prima se ne conquista la fiducia con piccoli pezzetti del loro cibo preferito, ovvero i casi particolari:
a=b=1
si cercano le soluzioni di x+y=n NON NEGATIVE, quindi $ x,y\geq 0 $, che non è mica difficile calcolare, no?
(0,n), (1,n-1), (2,n-2), .... , (n,0)
che sono n+1, quindi S(n)=n+1 e dunque il limite in questo caso è 1.
a=1, b generico
volete x+by=n e diciamo che $ n\geq b $ altrimenti col fischio che sono non negative... bene, quindi x=n-by, ma $ x\geq 0 $ per cui $ n\geq by $ e quindi y andrà da 0 a $ [n/b] $ (dove con [d] indico la parte intera). Per ogni tale y c'è una x non negativa, e solo per quelle, quindi S(n)=[n/b] e dunque
$ \displaystyle\lim_{n\to\infty} \frac{S(n)}{n}=\lim_{n\to\infty}\frac{[n/b]}{n} $
ma
$ \displaystyle\frac{n-1}{b}\leq [n/b]\leq\frac{n}{b} $
epperò
$ \displaystyle\lim_{n\to\infty}\frac{(n-1)/b}{n}=\frac{1}{b}=\lim_{n\to\infty}\frac{n/b}{n} $
da cui, per il teorema dei carabinieri (è una vita che sogno di usarlo!)
$ \displaystyle\lim_{n\to\infty}\frac{S(n)}{n}=\frac{1}{b} $.
Il caso a generico, b=1 è identico, mutatis mutandis.
Tutto ciò, vergogna e vituperio, potevate farlo anche voi! da qui, orsù, che vi viene in mente per fare il caso generale? Che cambia da quello a questi? Spremetevi le meningi!
Prima se ne conquista la fiducia con piccoli pezzetti del loro cibo preferito, ovvero i casi particolari:
a=b=1
si cercano le soluzioni di x+y=n NON NEGATIVE, quindi $ x,y\geq 0 $, che non è mica difficile calcolare, no?
(0,n), (1,n-1), (2,n-2), .... , (n,0)
che sono n+1, quindi S(n)=n+1 e dunque il limite in questo caso è 1.
a=1, b generico
volete x+by=n e diciamo che $ n\geq b $ altrimenti col fischio che sono non negative... bene, quindi x=n-by, ma $ x\geq 0 $ per cui $ n\geq by $ e quindi y andrà da 0 a $ [n/b] $ (dove con [d] indico la parte intera). Per ogni tale y c'è una x non negativa, e solo per quelle, quindi S(n)=[n/b] e dunque
$ \displaystyle\lim_{n\to\infty} \frac{S(n)}{n}=\lim_{n\to\infty}\frac{[n/b]}{n} $
ma
$ \displaystyle\frac{n-1}{b}\leq [n/b]\leq\frac{n}{b} $
epperò
$ \displaystyle\lim_{n\to\infty}\frac{(n-1)/b}{n}=\frac{1}{b}=\lim_{n\to\infty}\frac{n/b}{n} $
da cui, per il teorema dei carabinieri (è una vita che sogno di usarlo!)
$ \displaystyle\lim_{n\to\infty}\frac{S(n)}{n}=\frac{1}{b} $.
Il caso a generico, b=1 è identico, mutatis mutandis.
Tutto ciò, vergogna e vituperio, potevate farlo anche voi! da qui, orsù, che vi viene in mente per fare il caso generale? Che cambia da quello a questi? Spremetevi le meningi!
Re: Un limite "diofantino"
Orsù , cavalier assai Valente, voglia accettare la mia più profonda stima, e voglia altresì ascoltare la castroneria che sto probabilmente per sparare riguardo il caso generale;
Siamo a $ \displaystyle x = \frac{n-by}{a} $.. Come lei ha già osservato, messere, si ha $ y \le [n/b] $
Qui abbiamo una condizione in più : ovvero é necessario che sia $ n - by \equiv 0 \pmod a $ , ovvero $ n \equiv by \pmod a $
Essendo $ \gcd(a,b) = 1 $, esiste l'inverso di b modulo a (giusto? Mi pare di si) .. Moltiplicando per $ b^{-1} $ si ha dunque
$ y \equiv nb^{-1} \pmod a $ Quindi di y adeguati ce ne sono uno ogni a (partendo da $ nb^{-1} $ fino a $ [n/b] $) di conseguenza ce ne sono $ \displaystyle [\frac{n}{ab}] $
e il limite vale $ \displaystyle \frac{1}{ab} $
Siamo a $ \displaystyle x = \frac{n-by}{a} $.. Come lei ha già osservato, messere, si ha $ y \le [n/b] $
Qui abbiamo una condizione in più : ovvero é necessario che sia $ n - by \equiv 0 \pmod a $ , ovvero $ n \equiv by \pmod a $
Essendo $ \gcd(a,b) = 1 $, esiste l'inverso di b modulo a (giusto? Mi pare di si) .. Moltiplicando per $ b^{-1} $ si ha dunque
$ y \equiv nb^{-1} \pmod a $ Quindi di y adeguati ce ne sono uno ogni a (partendo da $ nb^{-1} $ fino a $ [n/b] $) di conseguenza ce ne sono $ \displaystyle [\frac{n}{ab}] $
e il limite vale $ \displaystyle \frac{1}{ab} $
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "
Re: Un limite "diofantino"
@ant.py: occhio, gli $y$ adeguati possono essere $ \displaystyle \left\lfloor \frac{n}{ab}\right\rfloor $ oppure $ \displaystyle\left\lfloor \frac{n}{ab}\right\rfloor +1 $. Ad esempio $ 2x +3y = 11 $ ha come soluzioni non negative $ (4,1) $ e $ (1,3) $ nonostante $ \left\lfloor \frac{11}{6}\right\rfloor = 1 $. Comunque il limite dovrebbe essere giusto
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"
Re: Un limite "diofantino"
un po' di decenza, suvvia...le cose si fan per bene.
Se di x come si deve ve n'è uno ogni a a partire da un dato c, fino a [n/b], allora ve ne saranno di sicuro
j=[[n/b]/a] più eventualmente un altro se $ c\leq [n/b]-ja $.
Ne convenite?
Comunque il limite sarà poi sempre lui.
Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?
Se di x come si deve ve n'è uno ogni a a partire da un dato c, fino a [n/b], allora ve ne saranno di sicuro
j=[[n/b]/a] più eventualmente un altro se $ c\leq [n/b]-ja $.
Ne convenite?
Comunque il limite sarà poi sempre lui.
Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?
-
- Messaggi: 232
- Iscritto il: 07 mag 2012, 11:51
Re: Un limite "diofantino"
Par brutto lasciare il thread in sospeso, rispondo io.EvaristeG ha scritto:Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?
E' vero: in generale, dati $\alpha\in\mathbb{R}$ e $k\in\mathbb{N}$, vale che $\left\lfloor \frac{\lfloor \alpha \rfloor}{k} \right\rfloor = \left\lfloor \frac{\alpha}{k} \right\rfloor$. Lo dimostro.
Abbiamo che $\frac{\alpha}{k}=\left\lfloor \frac{\alpha}{k} \right\rfloor+\lambda$, dove $\lambda\in\mathbb{R}\cap[0, 1)$, pertanto $\lfloor \alpha \rfloor=\left\lfloor k\left\lfloor \frac{\alpha}{k} \right\rfloor + k\lambda \right\rfloor=k\left\lfloor \frac{\alpha}{k} \right\rfloor+\lfloor k\lambda \rfloor$. Considerando ora che $0\le \frac{\lfloor k\lambda \rfloor}{k}<\lambda<1$, ne segue facilmente la tesi.
-
- Messaggi: 426
- Iscritto il: 14 lug 2012, 15:43
Re: Un limite "diofantino"
Evariste g che eleganza!! mi hai dato molte idee per molti problemi grazie
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"
"Blaise Pascal"
Re: Un limite "diofantino"
Robertopphneimer ha scritto:Evariste g che eleganza!!
...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
Ancora meglio
E se invece l'equazione fosse $\displaystyle \sum_{i=1} ^k a_i x_i=n$ con $\gcd (a_1, \dots, a_k)=1$, quanto varrebbe $\displaystyle \lim _{n \rightarrow \infty} \frac {S(n)}{n^{k-1}}$?
"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.)
-
- Messaggi: 426
- Iscritto il: 14 lug 2012, 15:43
Re: Un limite "diofantino"
direi verrebbe una forma indeterminata...$ \frac{\infty}{\infty} $
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"
"Blaise Pascal"
Re: Ancora meglio
c'è una generalizzazione più debole, e teoricamente più maneggevole, che dovrebbe essere con $\gcd(a_i, a_j) = 1$ per ogni coppia di indici $1\le i,j \le n$. euristicamente mi verrebbe da dire che le due risposte non dovrebbero essere molto diverse, ma ci devo pensare un po' meglio.<enigma> ha scritto:E se invece l'equazione fosse $\displaystyle \sum_{i=1} ^k a_i x_i=n$ con $\gcd (a_1, \dots, a_k)=1$, quanto varrebbe $\displaystyle \lim _{n \rightarrow \infty} \frac {S(n)}{n^{k-1}}$?