OliForum Matematico

Quello che vi propongo è davvero un superclassico! Ebbene sì, siamo alla frutta. In assenza di Simo, l'unico a tenere vivo il subforum di TdN, postando risposte sensate ai problemi proposti, è il nostro Igor (già, questa aspirerebbe ad essere un'invettiva bella e buona, se soltanto non fosse per il fatto che mi scopro tremendamente stanco! Ditevi fortunati... ). Certo anche HumanTorch merita una menzione d'onore, altro non fosse (e non è poco!!!) per il grande impegno, l'interesse e lo studio con cui si applica! Mi sono perciò detto che, al fine di coinvolgere anche gente al di fuori della cerchia (...), forse è il caso di evitare i self-posed, di abbassare un attimino il livello dei problemi e andare così più sulla letteratura. Spero almeno che il Satanasso apprezzi lo sforzo e la smetta di rimbrottarmi ad ogni rinnovata occasione, grrr...

Problema: sia $ \{p_n: n \in\mathbb{N}_0\} $ la sequenza ordinatamente crescente di tutti e soli i numeri primi di $ \mathbb{N} $ ($ p_1 = 2, p_2 = 3, p_3 = 5, \ldots) $. Senza usare risultati troppo raffinati, dimostrare che, per ogni intero $ n > 0 $: $ p_n \leq 2^{2^{n-1}} + 1 $, e stabilire quando vale l'uguaglianza.

Visto che stanotte non ho proprio sonno ho provato a buttare giù qualcosina..

Step 1: Per un fatto noto (non troppo raffinato spero) tra n e 2n (estremi esclusi) per n>1 c’è un numero primo. Posso dedurne che tra $ 2^n $ e $ 2^{n+1} $ c’è un primo.

Lemma:
So che 2 è primo; tra 2 e $ 2^2 $ c’è almeno un primo oltre a due (due in totale). Dimostro (induttivamente) ora che è sempre così.
Hp: tra 1 e $ 2^{n+1} $ ho almeno n+1 primi. So che tra $ 2^{n+2} $ avrò almeno un altro primo quindi ho minimo n+2 primi e ciò dimostra il lemma.

Step 2: $ p_n \leq 2^n $ perché se $ p_n > 2^n $ ci sarebbe almeno un primo (della successione p_i con $ i \leq n $ ) che non appartiene a nessuno degli n cassetti [1;2][2;4][..] $ [2^{n-1};2^{n}] $ e quindi n-1 camice da mettere in n cassetti e un cassetto vuoto ma ciò è assurdo perché contraddice un risultato precedente.

Step 3: $ 2^n \leq 2^{2^{n-1}}+1 $
Tolgo l’uno che mi sta molto antipatico..e lavoro sugli esponenti:
la th è riscritta come:
$ 2^n \leq 2^{2^{n-1}} $ ovvero per la crescenza della funzione $ 2^n $: $ n \leq 2^{n-1} $
Passo 1) $ 1\leq 1 $
Passo 2) HP: $ n \leq 2^{n-1} $ ; TH: $ n+1 \leq 2^n $ .
Moltiplico per 2 l’ipotesi e (sapendo che $ n \ge 1 $ ) ottengo la catena $ 2^n \ge 2n \ge n+1 $ da cui la tesi induttiva.

Ora so che: $ p_n \leq 2^n \leq 2^{2^{n-1}} < 2^{2^{n-1}}+1 $ ovvero la tesi (si noti che avendo dimostrato la seconda disuguaglianza senza quell'uno antipatico l'uguaglianza non dovrebbe essere verificata).

Sogni d'oro a coloro che riescono a dormire..

enomis_costa88 ha scritto:[...] Per un fatto noto (non troppo raffinato spero) tra n e 2n (estremi esclusi) per n>1 c’è un numero primo.

Ok, la tua dimostrazione è corretta, soltanto che usa un risultato davvero troppo raffinato, o almeno così si è convenuto di ritenere altrove (click). Del resto, ammettendo di poter utilizzare il teorema di Chebyshev (i.e., il risultato di cui si discute), la tesi risulta notevolmente raffinata ($ p_n \leq 2^n $, per ogni $ n\in\mathbb{N}_0 $). Questo per dire che il tuo proof non va bene, viste le precise richieste formulate nella consegna del problema:

HiTLeuLeR ha scritto:[...] Senza usare risultati troppo raffinati, dimostrare che [...]

HiTLeuLeR ha scritto:Questo per dire che il tuo proof non va bene, viste le precise richieste formulate nella consegna del problema:

HiTLeuLeR ha scritto:[...] Senza usare risultati troppo raffinati, dimostrare che [...]

ehm.. volendo fare i pignoli, queste non mi sembrano "precise richieste"...
direi che la prossima volta potresti pure dire "senza fare ricorso al teorema di chebycheff (o chebyshev, come preferisci).

Inserisco il problema nel subforum di TdN, che fa capo alla sezione del problem solving olimpico. Altrove, un mod (fph) dichiara che il teorema di Chebychev non è Matematica olimpica, indi è risultato raffinato. Ne deduco che nel risolvere il problema proposto non posso ricorrere al teorema di Chebychev. Punto! Deh, che vuoi farci, ma_go? Abbiamo appena dimostrato che non è da tutti essere pignoli...

Lemma #1.

$ (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1)=(2^{2^n}+1)+2 $

Si verifica per induzione.

Lemma #2

$ p_{n+1}\leq p_1p_2\ldots p_n+1 $

Consideriamo infatti il termine $ p_1p_2\ldots p_n+1 $.Esso non è divisibile per nessuno dei $ p_i $, quindi o è primo, o esiste almeno un altro primo maggiore di $ p_n $.In ogni caso il lemma resta verificato.

Torniamo ora al problema di partenza e lavoriamo per induzione.

Per $ n=1 $ la tesi è verificata, in quanto si ha $ 2\leq 3 $.

Supponiamola ora vera per i primi $ n $ interi positivi.Dimostriamo allora che essa è valida anche per $ n+1 $.Abbiamo infatti

$ p_{n+1}\leq p_1p_2\ldots p_n+1 $ $ \leq (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1) $ $ =2^{2^n}+2 $

Dato che $ 2^{2^n}+2 $ non è mai un numero primo, ne ricaviamo la tesi.

Riguardo l'uguaglianza, poichè non è verificata nè per $ n=1 $ nè per $ n=2 $, non sarà verificata per nessun $ n\in\mathmm{N} $.

Igor ha scritto:Lemma #1: $ (2^{2^{1-1}}+1)(2^{2^{2-1}}+1)\ldots (2^{2^{n-1}}+1)=(2^{2^n}+1)+2 $

Si verifica per induzione.

...ma tu, evidentemente, non l'hai verificato! Avresti scoperto infatti che il claim qui sopra è *falso*. Casomai è vero che, per ogni $ n\in\mathbb{N} $: $ \displaystyle 2 + \prod_{i=0}^n (2^{2^i} + 1) = 2^{2^{n+1}} + 1 $.

Igor ha scritto:Lemma #2: $ p_{n+1}\leq p_1p_2\ldots p_n+1 $ [...]

Sì, l'idea centrale è proprio questa! Adesso però devi rivedere gli argomenti conclusivi, se vuoi che la tua dimostrazione sia giudicata corretta. Mettiti al lavoro appena puoi, io aspetterò...

Ok, me ne occupo io, perché inizio a pensare che Igor non abbia più alcun interesse a rimettersi su un problema che, sostanzialmente, ha già risolto, seppure con qualche sbavatura di troppo.

Claim: per ogni intero $ n > 0 $: $ p_n \leq 2^{2^{n-1}} $.

Dim.: la tesi è banale per $ n = 1 $, ché $ p_1 = 2 \leq 2^{2^0} $. Fissato $ n\in\mathbb{N}_0 $, ammettiamone quindi la consistenza per ogni $ k = 1, 2, \ldots, n $. E allora $ \displaystyle p_{n+1} \leq 1 + \prod_{k=1}^n p_k $, poiché $ \displaystyle 1 + \prod_{k=1}^n p_k $ è un intero $ > 1 $ e non è divisibile per alcun primo dell'insieme $ \{p_k\}_{k=1}^n $. Ergo, dalle ipotesi assunte: $ \displaystyle p_{n+1} \leq 1 + \prod_{k=1}^n 2^{2^{k-1}} = 1 + 2^{1 + 2 + \ldots + 2^{n-1}} = $ $ 1 + 2^{2^n - 1} < 2^{2^n - 1} + 2^{2^n - 1} = 2^{2^n} $. Di qui - per induzione estesa - la tesi, q.e.d.

Il claim implica la tesi asserita nella consegna del problema, e dimostra nondimeno che l'uguaglianza colà suggerita, in effetti, non è mai soddisfatta. E adesso me ne sto zitto...