OliForum Matematico

Con potenza perfetta intendiamo un numero dello forma $ x^{y+1} $ per qualche $ (x,y) \in \mathbb{N}_0^2 $.
a) (Olimpiadi nazionali brasiliane) Esiste un insieme S di 2009 interi positivi distinti tali che la somma di uno o più elementi distinti di S non sia mai una potenza perfetta?
b) (Own) Esiste un insieme S con infiniti interi positivi distinti tali che la somma di uno o più elementi distinti di S non sia mai una potenza perfetta?

a) Considero i $ \displaystyle~2009 $ interi $ \displaystyle~p_1^{e_{1,1}}\cdots p_{2009}^{e_{2009,1}},\ldots,p_1^{e_{1,2009}}\cdots p_{2009}^{e_{2009,2009}} $ ($ \displaystyle~p_i $ indica l'$ \displaystyle~i- $esimo primo, mentre poniamo $ \displaystyle~e_{i,1}=1,\forall i\in\mathbb{N}_0 $ e $ \displaystyle~e_{i,j+1}=\begin{cases}e_{i,j}+1 & \text{se }p_i\nmid e_{i,j}+1 \\ e_{i,j}+2 & \text{se }p_i\mid e_{i,j}+1\end{cases},\forall i\in\mathbb{N}_0 $).
Se per assurdo una somma fosse una potenza $ \displaystyle~x- $esima, consideriamo un primo $ \displaystyle~q:q\mid x $. Allora se $ \displaystyle~\exists i \le 2009 : q=p_i $ avremmo che la valutazione $ \displaystyle~p_i- $adica della somma eguaglierebbe quella del numero minore nella somma, che per costruzione non è divisibile per $ \displaystyle~p_i $, quindi la somma non è nemmeno una potenza $ \displaystyle~p_i- $esima, assurdo!
Se $ \displaystyle~q>p_{2009} $ allora siamo a posto anche solo guardando la valutazione $ \displaystyle~2- $adica che non supererà $ \displaystyle~e_{1,2009}=2\cdot 2009-1\le p_{2009}<q $ e dunque non sarà divisibile per $ \displaystyle~q $.

Per il punto b) devo pensarci, spero solo che sia fattibile..

E che ne dici se al punto a) definiamo $ a_i:=pi $ per ogni $ 1 \le i \le 2009 $ e $ p \in \mathbb{P} $ sufficientemente grande?

Senonchè anche questo ragionamento non può essere applicato al punto b) (che comunque è fattibile.. )

Il punto b)
Non ho tempo di fare una dimostrazione dettagliata... non sarò molto formale:
Assumo (lo dimostro dopo) che per ogni k esiste una sequenza di naturali consecutivi lunga k priva di potenze: Allora gli elementi li scelgo così:
$ x_1=2 $
L'elemento i-esimo si trova così, sommo tutti i precedenti e chiamo la somma k, prendo la sequenza con k+1 naturali privi di potenze e scelgo il primo numero.
Assumo per assurdo che ci sia un sottoinsieme degli $ x_i $ tale che la somma è una potenza, ma allora scelgo il numero maggiore presente nel sottoinsieme, per definizione ottengo che sommando a questo degli elementi precedenti la somma rimarrà sempre minore della potenza successiva: assurdo.

Ora tocca al lemma che scritto in modo fico è:
$ \forall k\in \mathbb{N}\ \ \exists x\in\mathbb{N}\ t.c. \lfloor\log_i(x)\rfloor=\lfloor\log_i(x+k)\rfloor\ \ \forall i\in \mathbb{N} \wedge 2<i<x $
Che tradotto in italiano sarebbe che esistono 2 potenze consecutive distanti almeno "quanto si vuole".
Per dimostrarlo considero l'intervallo $ 2^{2x-1}\rightarrow 2^{2x} $
Prima di tutto noto che per ogni numero k in quell'intervallo può esserci al massimo una sola potenza di k, se ce ne fossero 2 allora otterrei un bell'assurdo con k<2. Inoltre se una potenza di k è presente nell'intervallo allora:
$ k<\sqrt{2^{2x}}=2^x $.
Per quanto detto in quell'intervallo sono presenti al massimo $ 2^x-1 $ (il 2 non è compreso) potenze perfette... da cui per pidgeon-hole, considerando come piccioni i numeri in quell'intervallo e come cassetti le potenze tra cui un numero e compreso, ottengo che esistono $ 2^{x-1}-1 $ numeri consecutivi privi di potenze dato che:
$ \frac{2^{2x-1}-1-(2^x-1)}{2^x}=2^{x-1}-1 $
Che è la divisione tra il numero dei piccioni e dei buchi xD da cui il lemma.

Spero di non aver scritto immani cazzate... soprattutto dato che questa è la dimostrazione mia che più mi piace :) Perchè è molto utile... soprattutto il lemma, che forse è un fatto noto xD

Si dario, l'hai scritto un po in maniera pedestre, ma funziona, good
Anyway..
-per la dimostrazione del lemma era sufficiente l'utilizzo del teorema cinese del resto;
-per la dimostrazione completa, era sufficiente porre $ a_i:=p_{i+1}\text{@} \cdot p_i\text{@} $ per ogni $ i \in \mathbb{N}_0 $ dove $ p_i\text{@} $ è l'i-esimo primoriale.