Un limite "diofantino"

[Ido Bovski]

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

[frod93]

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)

[ant.py]

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

[frod93]

ps e poi se $ S(n) \to 0 $il limite era indeterminato

$ \frac{0}{\infty} $ non è inderetminata D:

[ant.py]

ps e poi se $ S(n) \to 0 $il limite era indeterminato

$ \frac{0}{\infty} $ non è inderetminata D:

Ahah hai ragione scusami

Ora aspettiamo qualcuno che risolva il problema.. O magari un hint

[EvaristeG]

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!

[ant.py]

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

[Leonida]

@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

[EvaristeG]

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?

[Ido Bovski]

Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?

Par brutto lasciare il thread in sospeso, rispondo io.
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.

[Robertopphneimer]

Evariste g che eleganza!! mi hai dato molte idee per molti problemi grazie

[dario2994]

Evariste g che eleganza!!

[<enigma>]

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

[Robertopphneimer]

direi verrebbe una forma indeterminata...$ \frac{\infty}{\infty} $

[ma_go]

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

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.