161. $1,\ldots,100$ coperta da progr geom

[jordan]

161. E' possibile che $12$ progressioni geometriche coprono i numeri $1,2,\ldots,100$?

(Olimpiadi russe, 95', Grade 11)

[Troleito br00tal]

In che senso coprono? Lunghe quanto?

[jordan]

Lunghe quanto vuoi; coprono nel senso che ognuno di quegli interi appartiene ad (almeno) una delle sequenze

[Troleito br00tal]

Aaaaaah grazie:)

[karlosson_sul_tetto]

Devono essere per forza intere o non è necessario?

[jordan]

No, una di queste sequenze potrebbe anche essere, per esempio, $a_n=(\pi-\sqrt{2})(-\cos 5)^n$, con $n\ge 0$

[Troleito br00tal]

Proviamo.

Allora: una progressione geometrica può passare per al più $2$ primi $p;q$. Supponiamo esista una progressione del tipo $kx^n$ tale che $kx^a=p;kx^b=q;kx^c=r$ con $a<b<c$ naturali e $p<q<r$ primi. Valgono allora $x^{b-a}=\frac{q}{p};x^{c-b}=\frac{r}{q}$. Sia $M=(a-b;c-b)$. Per il teorema di Bézout, esistono $h;k$ interi positivi tali che $h(b-a)-k(c-b)=M$. Ma allora $(\frac{q}{p})^h/(\frac{r}{q})^k=x^{k(b-a)}/x^{k(c-b)}=x^M$, da cui $x^M$ è razionale. Sia $x^M=\frac{m}{n}$ con $(m;n)=1$. Ma allora $\frac{q}{p}=x^{b-a}=(\frac{n}{m})^{\frac{b-a}{M}}$ e $\frac{r}{q}=x^{c-b}=(\frac{n}{m})^{\frac{c-b}{M}}$. In particolare, gli interi positivi $\frac{a-b}{M}$ e $\frac{c-b}{M}$ devono essere uguali a $1$, poiché, se così non fosse, non varrebbe la primalità di $p;q;r$. Ma allora $c-b=M=b-a$, da cui $b=\frac{a+c}{2}$. Ma allora $q=\sqrt{pr}$: assurdo.

[Troleito br00tal]

Ok, credo che manchi la conclusione: poiché esistono $25$ numeri primi tra $1$ e $100$ le progressioni geometriche che coprono l'insieme cercato sono almeno $13$.

[jordan]

Bene, vai col prossimo!