Numero di sottoinsiemi mai quadrato

[jordan]

Per ogni intero positivo $n$, definiamo $f(n)$ il numero di sottoinsiemi non vuoti $\mathcal{N} \subseteq \{1,\ldots,n\}$ tali che $\text{gcd}(n \in \mathcal{N})=1$. Mostrare che $f(n)$ è un quadrato se e solo se $n=1$.

[Drago96]

Vabbè, dato che a nessuno importa ma è piuttosto carino, lo risolvo...

Lemma figo:$$\sum\limits_{i=1}^{n}f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)=2^n-1$$
Dim. Conto tutti i possibili sottoinsiemi non vuoti di $N=\{1,2,\dots,n\}$ in due modi diversi: come $2^n-1$ (cardinalità dell'insieme delle parti meno l'insieme vuoto), oppure sommando su tutti i possibili $\gcd$ degli elementi.
Se $S$ è un sottoinsieme di $N$, sia $d_S=\gcd(x\in S)$. Allora $1\le d_S\le n$; quindi posso suddividere i sottoinsiemi di $N$ in $n$ classi: quelli con $d_S=1$, quelli con $d_S=2$, ..., quelli con $d_S=n$. In particolare se fisso $d_S=k$, allora ho esattamente $f\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$ sottoinsiemi $S$ che soddisfano; infatti in $S$ gli elementi sono del tipo $kh$, e tutti minori o uguali di $n$; ciò significa che $h$ può variare da $1$ a $\left\lfloor\frac{n}{k}\right\rfloor$. Inoltre affinchè $d_S$ sia esattamente $k$, occorre che tutti gli $h$ siano tra loro coprimi: ma i possibili sottoinsiemi di $h$ sono contati dalla $f$, e poiché $1\le h\le\left\lfloor\frac{n}{k}\right\rfloor$, allora tutti i sottoinsiemi $S$ tali che $d_S=k$ fissato sono $f\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$. Siccome i possibili valori del massimo comun divisore sono tutti e soli quelli da $1$ a $n$, allora si ha la tesi (ricordando che in $f$ non è compreso l'insieme vuoto).$\;\;\square$

Dividiamo ora il problema in due parti, a seconda della parità di $n$, ma cercando di dimostrare il seguente
CLAIM: $f(n)\equiv2\pmod3$ per tutti gli $n\neq1$
Per induzione estesa su $n$; il passo base è ok, a mano si vede che $f(2)=2$.
- Caso $n=2m$
Il passo induttivo si basa sul lemma figo (perché sarebbe figo, se no?) e su un fatto piuttosto stupido, ovvero che per $k>m$ si ha che $f\left(\left\lfloor\frac{n}{k}\right\rfloor\right)=1$. Infatti applicando il lemma figo abbiamo che $\displaystyle f\left(2m\right)+f\left(\left\lfloor\frac{2m}{2}\right\rfloor\right)+\dots+f\left(\left\lfloor\frac{2m}{m}\right\rfloor\right)+\dots+f(1)=2^{2m}-1$; per il fatto stupido, gli ultimi $m$ addendi sono uguali a $f(1)=1$; per ipotesi induttiva i precendenti $m-1$ sono $\equiv2\pmod3$. Allora guardando la relazione modulo $3$ otteniamo che
$$f(2m)+(m-1)\cdot2+m\cdot1\equiv2^{2m}-1\pmod3$$
ovvero $$f(2m)\equiv(-1)^{2m}-1+2\equiv2\pmod3$$
- Caso $n=2m-1$
Simile a sopra, bisogna però stare un po' più attenti a contare le cose: ce ne sono $m$ uguali a $f(1)=1$ e $m-2$ congrui a $2\mod3$ per ipotesi induttiva. Quindi
$$f(2m-1)+(m-2)\cdot2+m\cdot1\equiv2^{2m-1}-1\pmod3$$
che diventa $$f(2m-1)\equiv4+(-1)^{2m-1}-1\equiv2\pmod3$$

E quindi abbiamo finito, perché $f(n)\equiv2\pmod3$ per tutti gli $n$, ma $\displaystyle\left(\frac2 3\right)=-1$

[jordan]

Si, quadra Qualche altra soluzione la trovate qui