Cardinalità di un insieme discreto

[Mathita]

Continuo ad avere molte perplessità. La prima è: perché ti fermi a $\ceil{\sqrt{2n}}$? Da dove viene fuori questo valore?

Inoltre posso dire che il numero di punti a coordinate intere positive del trapezoide di $y=\mbox{min}(x^2/4, n)$ con $x\in [1,n]$ è asintoticamente equivalente alla successione $f(n)=\int_{1}^{n}\mbox{min}(x^2/4,n)\mbox{d}x$?

In ogni caso grazie per avermi risposto finora.

[Edit] Per inciso, $f(n)=n^2-\frac{4n \sqrt{n}}{3}-\frac{1}{12}$ per $n\ge 4$. Ed entrambe le formule che ho trovato per $|S_n|$, vale

$\lim_{n\to+\infty}\frac{f(n)}{|S_n|}=1$

[hydro]

Continuo ad avere molte perplessità. La prima è: perché ti fermi a $\ceil{\sqrt{2n}}$? Da dove viene fuori questo valore?

Perchè continuo a confondermi, è $2\ceil{\sqrt{n}}$ e non $\ceil{\sqrt{2n}}$. Se $x\ge 2\ceil{\sqrt{n}}$ allora $x^2/4\ge n$ e quindi ogni $y\in \{1,\ldots,n\}$ soddisfa $4y\le x^2$, non sei d'accordo?

Inoltre posso dire che il numero di punti a coordinate intere positive del trapezoide di $y=\mbox{min}(x^2/4, n)$ con $x\in [1,n]$ è asintoticamente equivalente alla successione $f(n)=\int_{1}^{n}\mbox{min}(x^2/4,n)\mbox{d}x$?

Direi proprio di sì. Tutto quello che volevo dire è che questo problema è asintoticamente banale, nel senso che ovviamente $S_n$ ha asintoticamente $n^2$ elementi. Poi uno si può chiedere quanto sia l'errore, cioè quanto valga $|S_n-n^2|$, che certamente è $o(n^2)$. Il conto ovvio che ti ho scritto mostra che quel valore è in modulo al più dell'ordine di $n\sqrt{n}$. Poi in effetti ho detto una cosa sbagliata; ci sta che la tua formula sia giusta perchè può darsi che quel modo di contare sia più preciso e mostri che l'errore è $O(n)$.

[Mathita]

Se $x\ge 2\ceil{\sqrt{n}}$ allora $x^2/4\ge n$ e quindi ogni $y\in \{1,\ldots,n\}$ soddisfa $4y\le x^2$, non sei d'accordo?

Sì, sono d'accordo.

Tutto quello che volevo dire è che questo problema è asintoticamente banale, nel senso che ovviamente $S_n$ ha asintoticamente $n^2$ elementi. Poi uno si può chiedere quanto sia l'errore, cioè quanto valga $|S_n-n^2|$, che certamente è $o(n^2)$. Il conto ovvio che ti ho scritto mostra che quel valore è in modulo al più dell'ordine di $n\sqrt{n}$. Poi in effetti ho detto una cosa sbagliata; ci sta che la tua formula sia giusta perchè può darsi che quel modo di contare sia più preciso e mostri che l'errore è $O(n)$.

[Editato]Avevo fatto una battuta fuori luogo. Ho preferito cancellarla[/Editato] Ora mi è tutto chiaro! Sì, in effetti, se i miei calcoli sono corretti, dimostro $|n^2-S_n|=\theta(n)$ (questa stima non è affidabile, l'ho fatta a mente), mentre dalla stima integrale si ottiene che $|n^2-S_n|=O(n\sqrt{n})$, tuttavia la prima non viola la seconda.

Grazie ancora per essere intervenuto (e per avermi sopportato)!

[dan95]

Partendo da $S_n$ estendiamo $N$ a $N uu {n+1}$.

quindi avremo aggiunto:

1) I punti $(x_k, n+1)$ con $x_k$ tali che

$x_k \geq 2\sqrt{n+1}$

che sono $\floor{n+1-2\sqrt{n+1}}+1$.

2) I punti $(n+1,y_k)$ che sono $n+1$ infatti

$(n+1)^2-4y_k \geq (n+1)^2-4(n+1) \ geq 0$

per $n\geq 3$.


Notiamo che il punto $(n+1,n+1)$ viene aggiunto sia in 1) che in 2) quindi

$|S_{n+1}|=|S_n|+\floor{n+1-2\sqrt{n+1}}+n+1$

per $n \geq 3$.

Spero di aver contato bene...

[Mathita]

Ciao dan, possibile che tu abbia commesso un errore nel conteggio degli interi $x_k$? Te lo dico perché la tua formula non funziona per $n=3$. Nota infatti che:

$|S_4|=|S_3|+\ceil{4-4}+3=6\ne 7$

[dan95]

Ci sono anche altri valori che non vanno bene...

Va corretta

[axpgn]

Tutto quello che volevo dire è che questo problema è asintoticamente banale, nel senso che ovviamente $S_n$ ha asintoticamente $n^2$ elementi.

Cosa intendi per "asintoticamente"? Cosa si intende per "asintoticamente"? Perché mentre con un limite posso avvicinarmi al valore limite quanto voglio, qui no, nel senso che percentualmente è vero ma in valore assoluto certamente no.

Cordialmente, Alex

[Mathita]

Ci sono anche altri valori che non vanno bene...

Va corretta

Secondo me non sei molto lontano dalla soluzione, anche perché l'idea di fondo è corretta. Considera che il numero di interi $x_k$ compresi tra $2\sqrt{n+1}$ e $n+1$ coincide con il numero di interi compresi tra $\ceil{2\sqrt{n+1}}$ e $n+1$, e vale $n-\ceil{2\sqrt{n+1}}+2$. Effettuando questa modifica, la tua soluzione mi torna.

[dan95]

Yes, ora correggo. Praticamente i valori n+1 quadrato perfetto erano il problema.

[Mathita]

Tutto quello che volevo dire è che questo problema è asintoticamente banale, nel senso che ovviamente $S_n$ ha asintoticamente $n^2$ elementi.

Cosa intendi per "asintoticamente"? Cosa si intende per "asintoticamente"? Perché mentre con un limite posso avvicinarmi al valore limite quanto voglio, qui no, nel senso che percentualmente è vero ma in valore assoluto certamente no.

Cordialmente, Alex

Provo a risponderti io: se hydro avrà qualcosa da ridire, può tranquillamente intervenire e mandarmi a quel paese.

Quello che hydro si è chiesto è qual è l'ordine di infinito della differenza $n^2-|S_n|$? In base al calcolo effettuato con gli integrali, $n^2-f(n)$ ha un ordine di infinito pari a quello di $n\sqrt{n}$. Se invece consideriamo $n^2-|S_n|$ usando le mie formule risulta che esso ha lo stesso ordine di $n$ (a occhio).

Va notato che non ho ancora determinato (e non ho tanta voglia di farlo ) il comportamento asintotico di $\sum_{k=1}^{n}\ceil{2\sqrt{k}}$, per cui la stima $n^2-|S_n|\tilde{=} n$ per $n\to +\infty$ è probabilmente errata.