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.

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$

[axpgn]

"axpgn":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|$
0	2
3	3
7	5
6	19
27	8
9	49
62	11
12	94
112	14
15	154
178	17
18	230
259	20

[Mathita]

@axpng, è esattamente il percorso che ho fatto per arrivare a formulare il problema, solo che i miei disegni in geogebra erano più bruttini. Tuttavia, ho una richiesta: come hai fatto a trovare le varie cardinalità? Hai per caso scoperto qualcosa?

Ci ho pensato un po' su e ho scoperto questa cosa.

Considero la successione $\{x_n\}_n$ con $x_n=|S_{n}|$. Per $n\ge 4$, ho notato che $x_{n+1}-x_{n}=2n-\ceil{2\sqrt{n}}$, dove $\ceil{\cdot}$ è la funzione ceiling. È una successione definita ricorsivamente... non bellissima a dire il vero, non tanto perché ricorsiva (alla fine è una sommatoria): ciò che mi turba è la presenza della funzione ceiling. Se qualcuno è esperto in teoria dei numeri, il problema può essere riscritto in questi termini: quanti interi ci sono tra $2\sqrt{n}$ e $n$ (estremi inclusi) al variare di $n\ge 4$? (o se volete, quanti quadrati perfetti ci sono tra $4n$ e $n^2$, al variare di $n\ge 4$?)

[hydro1]

Non capisco esattamente quale risposta tu stia cercando; se vuoi una formula polinomiale non credo proprio che esista. Asintoticamente $S_n$ ha ovviamente $n^2$ elementi. Puoi anche stimare l'errore perchè chiaramente $|S_n|$ la puoi calcolare così: se $x\ge \ceil{\sqrt{2n}}$ vanno bene tutte le scelte di $y$, quindi hai $n(n-(\ceil{\sqrt{2n}}-1))$ elementi. Altrimenti, per ogni scelta di $x$ hai $\floor{\frac{x^2}{4}}$ scelte di $y$. In totale quindi $|S_n|=n(n-(\ceil{\sqrt{2n}}-1))+\sum_{x=1}^{\ceil{\sqrt{2n}}-1}\floor{\frac{x^2}{4}}$. Adesso puoi stimare quella sommatoria da sotto e da sopra levando le parti intere e troverai che l'errore è dell'ordine di $n\sqrt{n}$ (a meno di qualche strana cancellazione, nel qual caso bisogna pensarci meglio).

[axpgn]

"Mathita":... solo che i miei disegni in geogebra erano più bruttini.

Non è che i miei siano granché

"Mathita": Hai per caso scoperto qualcosa?

Figurati!
Ho solo costruito una tabella in Excel

[Mathita]

"hydro":Non capisco esattamente quale risposta tu stia cercando; se vuoi una formula polinomiale non credo proprio che esista.

In realtà non cercavo qualcosa di polinomiale. È più che altro il contesto in cui ho inserito il problema che mi "turba": non so fino a che punto questo possa essere un problema da scuola secondaria. Una volta trovata, la soluzione è piuttosto tranquilla da spiegare a degli studenti; la sua formalizzazione, invece, richiede degli strumenti che uno studente medio non possiede.[nota]Specifico medio, perché quando frequentavo l'Oliforum eoni fa, c'erano studenti davvero in gamba che mangiavano pane e funzioni floor e ceiling a colazione.[/nota] Peccato.

Aggiungiamoci pure che mi piace tanto fare casino con i problemi: mi diverto a passare da un problema facente parte di un ambito matematico a uno equivalente che appartiene a un altro... E i problemi di axpgn si prestano davvero bene a fare casino. Mi diverto con poco. Detto ciò...

Asintoticamente $S_n$ ha ovviamente $n^2$ elementi. Puoi anche stimare l'errore perchè chiaramente $|S_n|$ la puoi calcolare così: se $x\ge \ceil{2\sqrt{n}}$ vanno bene tutte le scelte di $y$, quindi hai $n(n-\ceil{2\sqrt{n}})$ elementi. Altrimenti, per ogni scelta di $x$ hai $\floor{\frac{x^2}{4}}$ scelte di $y$. In totale quindi $|S_n|=n(n-\ceil{2\sqrt{n}})+\sum_{x=1}^{\ceil{2\sqrt{x}}-1}\floor{\frac{x^2}{4}}$. Adesso puoi stimare quella sommatoria da sotto e da sopra levando le parti intere e troverai che l'errore è dell'ordine di $n\sqrt{n}$ (a meno di qualche strana cancellazione, nel qual caso bisogna pensarci meglio).

Mi sono perso! Se ti va, puoi gentilmente essere più esplicito? Non sono sicuro di aver compreso come funziona la somma in $|S_n|=n(n-\ceil{2\sqrt{n}})+\sum_{x=1}^{\ceil{2\sqrt{x}}-1}\floor{\frac{x^2}{4}}$: per come la interpreto io, l'uguaglianza non regge per ogni $n$. Grazie per essere intervenuto in ogni caso.

[hydro1]

Eh hai ragione, avevo sbagliato a scrivere, ho corretto. Comunque è semplice: devi contare le coppie $(x,y)$ che soddisfano quella relazione. Adesso se $x$ è almeno $\ceil{2n}$, allora $y$ può essere qualsiasi cosa. Altrimenti, dovendo essere minore di $x^2/4$, avrai parte intera di $x^2/4$ scelte per $y$. Ovviamente questa formula varrà definitivamente in $n$, non per ogni $n$, ma questo genere di problemi, ovvero contare punti interi in regioni dello spazio, si studia solo in questi termini normalmente, perchè se vuoi sapere la risposta per $n$ piccolo fai una tabella di excel come axpgn…

[Mathita]

@hydro, non ho ancora esaminato le modifiche che hai apportato, ma intanto ti ringrazio!

Nello spoiler riporto il ragionamento che ho seguito per trovare la mia soluzione.

Riprendo un attimo le notazioni. L'obiettivo è determinare la cardinalità dell'insieme

$S_n=\{(x,y)\in N\times N : x^2-4y\ge 0\}$.

Osservo preliminarmente che, per ogni $n\ge 1$, gli insiemi ${1,2,...,n}^2$ e ${1,2,...,n,n+1}^2$ differiscono di $(n+1)^2-n^2=2n+1$ elementi. Dal punto di vista geometrico, partendo dal "quadrato puntato" ${1,2,...,n}^2$, possiamo costruire il "quadrato puntato" ${1,2,...,n,n+1}^2$, aggiungendo i $2n+1$ punti di coordinate intere

$(n+1,k)$ con $k\in {1,2,...,n+1}$

$(k,n+1)$ con $k\in\{1,2,...,n\}$

Inoltre, evidentemente $S_n\subseteq S_{n+1}$, per ogni $n\ge 1$.

Una volta stabilito il set-up, osservo quanto segue.

Per $x\ge 1$, la parabola di equazione $y=\frac{x^2}{4}$ giace al di sopra della bisettrice del 1° e del 3° quadrante se e solo se $x\ge 4$. (Dimostrazione ovvia.). Ciò prova che per ogni $n>4$, $n<\frac{n^2}{4}$ o equivalentemente $2\sqrt{n}< n$. Dal punto di vista geometrico ciò si traduce in: per ogni $n>4$, la parabola fugge dal quadrato $[1,n]^2$ intersecando internamente il segmento che congiunge i punti $(1,n)$ e $(n,n)$ (in pratica il segmento superiore del quadrato).

Questo ci permette di affermare che per ogni $n\ge 4$, l'insieme $S_{n+1}$ si esprime nell'unione di tre insiemi a due a due disgiunti:

$S_{n+1}=S_{n}\cup\{(n+1,k): k\in {1,2,...,n+1}\}\cup\{(j,n+1): 2\sqrt{n+1}\le j\le n\}$

da cui

$|S_{n+1}|=|S_{n}|+|\{(n+1,k): k\in {1,2,...,n+1}\}|+|\{(j,n+1): 2\sqrt{n+1}\le j\le n\}|$

Ora, il secondo addendo è chiaramente $n+1$, un po' meno evidente è il terzo addendo. Sia $\ceil{2\sqrt{n+1}}$ il più piccolo intero più grande o uguale a $2\sqrt{n+1}$, allora

$|\{(j,n+1): 2\sqrt{n+1}\le j\le n\}|=|\{(j,n+1): \ceil{2\sqrt{n+1}}\le j\le n\}|=$

$=n-\ceil{2\sqrt{n+1}}+1$

In definitiva $|S_{n+1}|=|S_{n}|+2n+2-\ceil{2\sqrt{n+1}}$ per ogni $n\ge 4$ da cui:

$|S_{n+1}|=|S_4|+\sum_{k=4}^{n}(2k+2-\ceil{2\sqrt{k+1}})=$

$=7+(n^2+3n-18)-\sum_{k=4}^{n}\ceil{2\sqrt{k+1}}=$

$=n^2+3n-11-\sum_{k=4}^{n}\ceil{2\sqrt{k+1}}$ per ogni $n\ge 4$, salvo errori o omissioni.

Non una bellissima dimostrazione, lo ammetto. Non mi piace nemmeno come l'ho buttata giù... :\

[hydro1]

"Mathita":@hydro, non ho ancora esaminato le modifiche che hai apportato, ma intanto ti ringrazio!

Nello spoiler riporto il ragionamento che ho seguito per trovare la mia soluzione.

Riprendo un attimo le notazioni. L'obiettivo è determinare la cardinalità dell'insieme

$S_n=\{(x,y)\in N\times N : x^2-4y\ge 0\}$.

Osservo preliminarmente che, per ogni $n\ge 1$, gli insiemi ${1,2,...,n}^2$ e ${1,2,...,n,n+1}^2$ differiscono di $(n+1)^2-n^2=2n+1$ elementi. Dal punto di vista geometrico, partendo dal "quadrato puntato" ${1,2,...,n}^2$, possiamo costruire il "quadrato puntato" ${1,2,...,n,n+1}^2$, aggiungendo i $2n+1$ punti di coordinate intere

$(n+1,k)$ con $k\in {1,2,...,n+1}$

$(k,n+1)$ con $k\in\{1,2,...,n\}$

Inoltre, evidentemente $S_n\subseteq S_{n+1}$, per ogni $n\ge 1$.

Una volta stabilito il set-up, osservo quanto segue.

Per $x\ge 1$, la parabola di equazione $y=\frac{x^2}{4}$ giace al di sopra della bisettrice del 1° e del 3° quadrante se e solo se $x\ge 4$. (Dimostrazione ovvia.). Ciò prova che per ogni $n>4$, $n<\frac{n^2}{4}$ o equivalentemente $2\sqrt{n}< n$. Dal punto di vista geometrico ciò si traduce in: per ogni $n>4$, la parabola fugge dal quadrato $[1,n]^2$ intersecando internamente il segmento che congiunge i punti $(1,n)$ e $(n,n)$ (in pratica il segmento superiore del quadrato).

Questo ci permette di affermare che per ogni $n\ge 4$, l'insieme $S_{n+1}$ si esprime nell'unione di tre insiemi a due a due disgiunti:

$S_{n+1}=S_{n}\cup\{(n+1,k): k\in {1,2,...,n+1}\}\cup\{(j,n+1): 2\sqrt{n+1}\le j\le n\}$

da cui

$|S_{n+1}|=|S_{n}|+|\{(n+1,k): k\in {1,2,...,n+1}\}|+|\{(j,n+1): 2\sqrt{n+1}\le j\le n\}|$

Ora, il secondo addendo è chiaramente $n+1$, un po' meno evidente è il terzo addendo. Sia $\ceil{2\sqrt{n+1}}$ il più piccolo intero più grande o uguale a $2\sqrt{n+1}$, allora

$|\{(j,n+1): 2\sqrt{n+1}\le j\le n\}|=|\{(j,n+1): \ceil{2\sqrt{n+1}}\le j\le n\}|=$

$=n-\ceil{2\sqrt{n+1}}+1$

In definitiva $|S_{n+1}|=|S_{n}|+2n+2-\ceil{2\sqrt{n+1}}$ per ogni $n\ge 4$ da cui:

$|S_{n+1}|=|S_4|+\sum_{k=4}^{n}(2k+2-\ceil{2\sqrt{k+1}})=$

$=7+(n^2+3n-18)-\sum_{k=4}^{n}\ceil{2\sqrt{k+1}}=$

$=n^2+3n-11-\sum_{k=4}^{n}\ceil{2\sqrt{k+1}}$ per ogni $n\ge 4$, salvo errori o omissioni.

Non una bellissima dimostrazione, lo ammetto. Non mi piace nemmeno come l'ho buttata giù... :\

Questa formula certamente non può essere giusta perchè l'ordine di grandezza dell'errore è troppo piccolo. Contare i punti interi sotto a $y=x^2/4$ per $x=1,\ldots,\ceil{\sqrt{2n}}$ è asintotico a integrare la funzione $x^2/4$ da $1$ a $\ceil{\sqrt{2n}}$. L'integrale di $x^2$ è $x^3$, e quando lo valuti in $\sqrt{n}$ trovi $n\sqrt{n}$. L'errore della tua formula è $\le n$, troppo piccolo.

[Mathita]

Grazie per lo spunto, hydro. Ho riletto più volte la dimostrazione e purtroppo non riesco a intravedere il bug che la fa saltare: ho bisogno di pensarci meglio a mente fresca.

[Mathita]

Ciao a tutti!

@hydro, ho provato più e più volte a rileggere la dimostrazione, ma non ho trovato l'inghippo. I casi sono due: ho commesso un errore dovuto a una convinzione matematica errata, così radicata in me, che non potrò mai vedere. Oppure la dimostrazione è corretta. (Conoscendomi, ci sarà un bug grande quanto a una casa).

Inoltre, se devo essere del tutto sincero, non capisco il ragionamento che fai per le stime asintotiche. Ho l'impressione che ragionando con l'integrale $\int_{1}^{\ceil{\sqrt{2n}}}\frac{x^2}{4}dx$ tu stia aggiungendo un pezzo: l'area della parte di grafico di $\frac{x^2}{4}$ compresa tra le rette $y=0$ e $y=1$. Possibile che sia questo il gap che crea discrepanza? Non saprei...

Siccome non ho ancora perso del tutto le speranze, riporto un grafico per chiarire un po' il ragionamento.



$S_6$ è composto dai punti di $S_5$ (in blu), dai punti in rosso che appartengono all'insieme

$\{(6,y): y\in\{1,2,3,4,5,6\}\}$

e dal punto verde che appartiene all'insieme

$\{(x,6): x\mbox{ intero tale che } 2\sqrt{6}\le x\le 5\}$.

Una volta notato questo, ho generalizzato (o meglio, ho tentato di generalizzare), esprimendo la cardinalità dell'insieme $S_{n+1}$ in termini di $S_n$.

In spoiler, una dimostrazione alternativa

Volendo ragionare per segmenti paralleli all'asse x e a ordinate intere, potremmo seguire questo procedimento.

Fisso $k\in\{1,2,...,n\}$, considero l'insieme

$R_{k}=\{(i,k) : i\in\{1,2,...,n}\}$

la cui cardinalità è $n$ per ogni $k$ fissato. Tale insieme può essere espresso nell'unione di due insiemi disgiunti

$M_{k}=\{(j,k): j \mbox{ intero t.c. } 1\le j<2\sqrt{k}\}$ (sono i punti a coordinate intere positive che stanno a sinistra del grafico di $y=x^2/4$ con quota fissata $k$).

$N_{k}=\{(j,k): j\mbox{ intero t.c. } 2\sqrt{k}\le j\le n\}$ (sono i punti a coordinate intere minori o uguali a $n$ che stanno a destra del grafico di $y=x^2/4$ con quota fissata $k$).

Per ogni $k\in\{1,2,...,n\}$, si ha che $R_k=M_k\cup N_{k}$ con $M_{k}\cap N_{k}=\emptyset$, di conseguenza

$|R_{k}|=|M_{k}|+|N_{k}| \implies n=|M_{k}|+|N_{k}|$ (1).

A questo punto osservo che

$|M_k|=|\{(j,k): j \mbox{ intero t.c. } 1\le j\le \ceil{2\sqrt{k}}-1\}|=\ceil{2\sqrt{k}}-1$

e che da (1)

$|N_{k}|=n-|M_{k}|=n-\ceil{2\sqrt{k}}+1$ per ogni $k\in\{1,2,...,n\}$

Infine noto che $S_n=\cup_{k=1}^{n}N_k$ con $N_{i}\cap N_{j}=\emptyset$ per $i\ne j$

$|S_n|=\mbox{card}(\bigcup_{k=1}^{n}N_{k} )=$

$=\sum_{k=1}^{n}(n-\ceil{2\sqrt{k}}+1)=n^2+n-\sum_{k=1}^{n}\ceil{2\sqrt{k}}$ e questa vale per ogni $n\in\mathbb{N}\setminus\{0\}$.

Volendo, avrei potuto calcolare direttamente la cardinalità di $N_{k}$ usando la funzione floor, ma siccome sono uno che si complica la vita, ho preferito infierire su di me... e di riflesso, su di voi, sorry.

Spero che la dimostrazione sia corretta: non vorrei mai che uno studente si presentasse con un dado a 20 facce, di 30 kg, e mi chiedesse di risolvere il problema di axpgn col suddetto dado. Sopproblemi!

[hydro1]

"Mathita":Ciao a tutti!



Inoltre, se devo essere del tutto sincero, non capisco il ragionamento che fai per le stime asintotiche. Ho l'impressione che ragionando con l'integrale $\int_{1}^{\ceil{\sqrt{2n}}}\frac{x^2}{4}dx$ tu stia aggiungendo un pezzo: l'area della parte di grafico di $\frac{x^2}{4}$ compresa tra le rette $y=0$ e $y=1$.

Certo, ma quella parte asintoticamente è irrilevante perchè pesa al più $n$.

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