Cardinalità di un insieme discreto

[Mathita]

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.

Testo nascosto, fai click qui per vederlo

Una mezza idea buttata un po' a caso: avevo iniziato a ragionare in termini continui, avevo cioè considerato l'insieme $S=\{(x, y)\in [1,n]^2: x^2-4y\ge 0\}$ e ho tentato di contare i punti a coordinate intere di S, al variare di n. Chiaramente non ci sono riuscito.

[otta96]

Ma è sempre infinito.

[Mathita]

In che senso è infinito? $S_n\subseteq N\times N$, dunque $|S_n|\leq n^2$

[Mathita]

Ah, forse ho usato una combinazione infelice di lettere. Quella N può essere confusa con $\mathbb{N\}$.

[megas_archon]

Ma la regione di piano in cui la disuguaglianza vale è illimitata... perciò conterrà un numero infinito di punti a coordinate intere.

[Mathita]

$S$ è contenuto nel quadrato $[1,n]^2=[1, n]\times [1, n]$. Chiedo scusa per tutte le incomprensioni: avrei dovuto scrivere meglio il quesito.

[otta96]

Si avevo confuso $N$ con $NN$.
Dopo ci ripenso un po'.

[axpgn]

@Mathita
Beh, sai già che per $n=6$ la cardinalità è $19$

Potresti partire da qui




Cordialmente, Alex

[axpgn]

La mia impressione è che la cardinalità aumenti di $n$ più una quantità che aumenta sempre più ma più lentamente di $n$

Testo nascosto, fai click qui per vederlo

[axpgn]

Testo nascosto, fai click qui per vederlo

La mia impressione è che la cardinalità aumenti di $n$ più una quantità che aumenta sempre più ma più lentamente di $n$

però questa quota ulteriore si avvicina sempre più a $n$, quindi mi verrebbe da concludere che tenderebbe ad aumentare di $2n$.
Forse ...

$n$	$|S|$
1	0
2	1
3	3
4	7
5	12
6	19
7	27
8	37
9	49
10	62
11	77
12	94
13	112
14	132
15	154
16	178
17	203
18	230
19	259
20	290