Togliere le progressioni geometriche

[080e73990d22b9e30ee6fddddc45a902d78283e6]

Costruire una successione \( \{ a_n\}_{n \ge 1} \) strettamente crescente di numeri interi positivi tale che \[ \lim_{n \to \infty} \frac{\max \{k : a_k \le n \}}{n} = 1 \] e che non contenga alcuna progressione geometrica infinita del tipo \( \{ q^n \}_{n \ge 1}\) con \(q\) intero positivo.

Enjoy.

[hydro1]

Un'idea abbastanza banale. Definisco $a_n$ per ricorsione così: $a_1=1$ e poi $a_{n+1}=a_n+1$ se $a_n+1$ non è un quadrato e $a_{n+1}=a_n+2$ se $a_n+1$ è un quadrato. Questa successione non contiene quadrati perchè non ci sono due quadrati consecutivi negli interi positivi. Siccome non contiene quadrati, non può contenere successioni geometriche. Quant'è grande $a_n$? beh almeno \(n+\lfloor \sqrt{n}\rfloor-1\) e al più \(n+\lfloor \sqrt{n}\rfloor\), perchè ogni volta che incontro un quadrato sposto in là di $1$, e tra $1$ ed $n$ ci sono \(\lfloor \sqrt{n}\rfloor\) quadrati. Chiamiamo $k_n=\max\{k:a_n\le n\}$; da un lato \(a_{n-\lfloor\sqrt{n}\rfloor}\le n\), quindi \(k_n\ge n-\lfloor\sqrt{n}\rfloor\) dall'altro se $a_k\le n$ allora $k+\sqrt{k}-1\le n$ e di conseguenza $k_n\le n+o(n)$. Questo dimostra che $k_n$ è asintotico ad $n$.

[080e73990d22b9e30ee6fddddc45a902d78283e6]

"hydro":

Un'idea abbastanza banale. Definisco $a_n$ per ricorsione così: $a_1=1$ e poi $a_{n+1}=a_n+1$ se $a_n+1$ non è un quadrato e $a_{n+1}=a_n+2$ se $a_n+1$ è un quadrato. Questa successione non contiene quadrati perchè non ci sono due quadrati consecutivi negli interi positivi. Siccome non contiene quadrati, non può contenere successioni geometriche. Quant'è grande $a_n$? beh almeno \(n+\lfloor \sqrt{n}\rfloor-1\) e al più \(n+\lfloor \sqrt{n}\rfloor\), perchè ogni volta che incontro un quadrato sposto in là di $1$, e tra $1$ ed $n$ ci sono \(\lfloor \sqrt{n}\rfloor\) quadrati. Chiamiamo $k_n=\max\{k:a_n\le n\}$; da un lato \(a_{n-\lfloor\sqrt{n}\rfloor}\le n\), quindi \(k_n\ge n-\lfloor\sqrt{n}\rfloor\) dall'altro se $a_k\le n$ allora $k+\sqrt{k}-1\le n$ e di conseguenza $k_n\le n+o(n)$. Questo dimostra che $k_n$ è asintotico ad $n$.

Bello!

Io pensavo di togliere un termine di ogni progressione geometrica "ogni tanto", in maniera "sempre piu' lenta", i.e. definisco per esempio \(n_k = 2^k\) e considero \(C = \mathbb{N} \setminus \{2^{n_k}, 3^{n_k}, \dots \}_{k \ge 1}\), \(C_n = \{ t \in C : t \le n \} \). Se fisso \(n\), prendo il piu' grande \(k\) tale che \(2^{2^k} \le n\), cioe' \( k = \lfloor \log_2(\log_2(n)) \rfloor \). Dovrebbe essere \( \max_{k=1} C_n = \lfloor \sqrt{n} \rfloor \), quindi \(\text{card}(C_n) \ge n - \lfloor \log_2(\log_2(n)) \rfloor \lfloor \sqrt{n} \rfloor \) da cui la tesi.

Dalle olimpiadi di Matematica di qualche anno fa dell'universita' di Kyev, mi pare.