Prueba de (1)
Dejemos que $S = \left\{ \dfrac{p}{q} \,|\; 1 \le p \le q \le n \right\}$ . Entonces todos los elementos de $S$ se situaría entre $0$ y $1$ . Ordena los elementos en orden creciente y que sea $a_1 < a_2 < \cdots < a_N$ = 1. Además, dejemos que $a_0=0$ .
En primer lugar, hay que tener en cuenta que $$N = \sum_{d=1}^{n} \phi(d)$$ ya que hay exactamente $\phi(d)$ número de fracción cuyo denominador es $d$ en su forma reducida.
Si algunos $a_i = \frac{p}{q}$ se encuentra entre $x$ y $y$ , entonces uno de $\lfloor qx \rfloor$ y $\lfloor qy \rfloor$ debe ser menor que $p$ y uno mayor o igual a $p$ . Así, para $(x,y)$ para ser un elemento de $S_n$ deben estar ambos en algún intervalo $[a_i, a_{i+1})$ .
Por otro lado, si $x, y \in [a_i, a_{i+1})$ no puede haber ningún $q \le n$ tal que existe un número entero $p$ entre $qx$ y $qy$ . Por lo tanto, no hay $q$ que $\lfloor qx \rfloor \neq \lfloor qy \rfloor$ y $(x,y) \in S_n$ .
Ahora sabemos que $S_n$ sólo se compone de cuadrados $[a_i,a_{i+1}) \times [a_i,a_{i+1})$ para $i = 0, 1, \cdots, N-1$ y $(1,1)$ . Por lo tanto, el número de cuadrados es $R_n = N$ .
