Cardinalità di un insieme discreto
Questo quesito nasce dall'esigenza di generalizzare un problema proposto da Axpgn. Non ho ancora trovato una soluzione, e se vogliamo dirla tutta non so nemmeno se esiste una soluzione elementare.
Siano $n\in\mathbb{N}\setminus\{0\}$ ed $N=\{1,2,...,n\}$. Definiamo l'insieme $$S_n=\{(x,y) \in N\times N : x^2-4y\ge 0\} $$ Determinare la cardinalità di $S_n$, al variare di n.
Siano $n\in\mathbb{N}\setminus\{0\}$ ed $N=\{1,2,...,n\}$. Definiamo l'insieme $$S_n=\{(x,y) \in N\times N : x^2-4y\ge 0\} $$ Determinare la cardinalità di $S_n$, al variare di n.
Risposte
"Mathita":
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?
"Mathita":
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)$.
"hydro":
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)!
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...
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...
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$
$|S_4|=|S_3|+\ceil{4-4}+3=6\ne 7$
Ci sono anche altri valori che non vanno bene...
Va corretta
Va corretta
"hydro":
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
"dan95":
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.
Yes, ora correggo. Praticamente i valori n+1 quadrato perfetto erano il problema.
"axpgn":
[quote="hydro"] 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[/quote]
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.
"Mathita":
Va notato che non ho ancora determinato (e non ho tanta voglia di farlo
Sicuramente $\sum_{k=1}^n2\sqrt{k}$ è asintotico a $\frac{4}{3}n\sqrt{n}$, sempre per lo stesso motivo di sopra. Ora quanto metti le parti intere stai sbagliando al più di $1$ per ogni termine della sommatoria, quindi complessivamente al più di $n$.
Sì, mi convince! Quindi, alla fine della fiera, anche $\sum_{k=1}^{n}\ceil{2\sqrt{k}}$ è asintotico a $n\sqrt{n}$, no? Dopotutto mi stai dicendo che
$\sum_{k=1}^{n}\ceil{2\sqrt{k}}=\sum_{k=1}^{n}2\sqrt{k}+r_{n}$
con $r_{n}\le n$. Mi garba!
$\sum_{k=1}^{n}\ceil{2\sqrt{k}}=\sum_{k=1}^{n}2\sqrt{k}+r_{n}$
con $r_{n}\le n$. Mi garba!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo