L[04/05] Spero di fare bella figura

[Gerald Lambeau]

Siccome è il mio ottocentesimo post volevo fare qualcosa di bello (voglio rifarmi dopo aver buttato il cinquecentesimo per fisica...), ho deciso di postare un problema carino e che utilizza un fatto molto utile e facile da dimostrare (se si hanno le giuste conoscenze).
Determinare il più grande intero positivo $n$ tale che per ogni intero $k$ con $1<k<n, (n, k)=1$, $k$ è primo.

[Veritasium]

È considerato omicidio?

Testo nascosto:

Siano [tex]2 = p_1, p_2, ...[/tex] i primi. Sia [tex]p_j[/tex] il più piccolo primo che non divide [tex]n.[/tex] Allora essendo [tex](n, p_j^2) = 1[/tex] sì ha [tex]p_j^2 > n \ge \prod_{i = 1}^{j - 1} p_i.[/tex] Notiamo che per [tex]p_j = 7[/tex] ciò è vero in quanto [tex]49 > 30[/tex] ma per [tex]p_j = 11[/tex] è falso in quanto [tex]121 < 210. \ 30[/tex] quindi ovviamente soddisfa ed è il massimo [tex]n[/tex] a soddisfare se poniamo [tex]p_j = 7,[/tex] in quanto se moltiplichiamo [tex]30[/tex] per un qualsiasi primo [tex]\le 7[/tex] superiamo [tex]49.[/tex] Mostriamo ora che per [tex]p_j > 7[/tex] non ci sono soluzioni.
È sufficiente mostrare che se [tex]p_j > 7, \prod_{i = 1}^{j-1} p_i > p_j^2.[/tex] Facciamolo per induzione: per $11$ si è già visto che è vero. Ora, diamo per buono $p_m^2 < 2 \cdot 3 \cdot ... \cdot p_{m-1}$ e dimostriamo per $p_{m+1}:$ sarà sufficiente $p_{m+1}^2 < p_m^3$ essendo che per il passo induttivo $p_m^2 < 2 \cdot ... p_{m-1}$. Tuttavia, per il ben noto Postulato di Bertrand, per ogni intero positivo [tex]g[/tex] esiste un primo [tex]q: g \le q \le 2g,[/tex] dunque scegliendo [tex]g = p_{m} + 1[/tex] otteniamo [tex]p_{m+1} ≤ 2(p_m + 1)[/tex] dunque è sufficiente che per [tex]x \ge 11[/tex] valga [tex][2(x+1)]^2 < x^3 \iff f(x) = x^3 - 4x^2 - 8x - 4 > 0.[/tex] Sostituendo $x = 11$ notiamo che è verificata essendo $1331 > 576$. Ci manca da mostrare che $f$ è crescente per $x \ge 11$. Derivando otteniamo che $f'(x) > 0$ vale per ogni $x > \frac{4+2\sqrt10}{3} < 4$ e dunque anche per $x \ge 11$.
Concludiamo quindi che $p_j = 7$ e quindi $n$ è un utente di questo forum (chiaramente scegliendo $p_j < 7$ otteniamo valori di $n$ più bassi).

[Gerald Lambeau]

È considerata la soluzione più ovvia.
Una cosa, il postulato di Bertrand ha delle disuguaglianze strette, quindi potevi scegliere $g=p_m$ e ottenere $p_{m+1}<2p_m$, portando a disuguaglianze più semplici di tutta l'algebra che hai fatto.

Ed è bene ricordarsi che la disuguaglianze che dice, chiamando $p_i$ l'$i$-esimo numero primo, che per $n>3$ si ha $\displaystyle \prod_{i=1}^n p_i>p_{n+1}^2$ si chiama disuguaglianza di Bonse, e adesso vado a scrivere un bel post sull'OliForum per sapere se si può dare per buona in gara.

[Veritasium]

Oh figo non sapevo avesse un nome

Boh speravo ed ero convinto che ci fosse una soluzione che usasse qualcosa di meno potente di Bertrand

[Gerald Lambeau]

Ah non lo so se esiste una soluzione con mezzi meno potenti, anche nel pdf del WC 2015 da cui ho preso il problema lo risolvono così.

[cip999]

Esiste esiste, è completamente calata dal cielo e sta in quello stesso PDF subito dopo la soluzione con Bertrand.