TST italiano 2007 numero 6

[Pigkappa]

Sia p un primo maggiore di 3. Dimostrare che:

1)$ \displaystyle (p-1)^p +1 $ ha dei fattori primi diversi da p.
2)Sia $ \displaystyle (p-1)^p +1 = q_1 ^{\alpha_1} q_2 ^{\alpha_2} ... q_n ^{\alpha_n} $ la scomposizione di $ \displaystyle (p-1)^p $. Dimostrare che $ \displaystyle q_1 \alpha_1 + q_2 \alpha_2 + ... + q_n \alpha_n > p^2/2 $

[edriv]

Oggi facendo il giro della stazione di Santa Maria Novella ho scoperto che, se non mi fossi tanto complicato la vita, potevo tranquillamente concludere la mia soluzione.

Bando alle ciancie, ecco qua una:
Lemma 0: $ ~ p^2 \mid \mid (p-1)^p + 1 $.
Dimostrazione: riscrivere come $ ~ p^2\left( p^{p-2} - {p \choose p-1}p^{p-3} + ...+ {p \choose 3}p - {p \choose 2} + 1\right) $ e notare che il secondo fattore è una somma di multipli di p + 1, ed è uguale a 1 sse p=3. Questo dimostra il punto a).

Lemma 1: Dati interi a,b > 2 e reali positivi $ ~ \alpha,\beta $ tali che $ ~ a<b $ e $ \alpha a = \beta b $. Allora $ a^{\alpha} > b^{\beta} $.
Dimostrazione: riscrivere come $ ~ a^{\frac{b \beta}a} > b^{\beta} \Leftrightarrow a^{\frac 1a} > b^{\frac 1b} $ che è vero per la decrescenza della funzione $ ~ x^{\frac 1x} $ per x>e.

Lemma 2: I fattori primi diversi da p di $ ~ (p-1)^p+1 $ sono maggiori di 2p.
Dimostrazione: $ ì (p-1)^p \equiv -1 \pmod q $, quindi l'ordine di (p-1) modulo q è pari e divide 2p, ma non piò essere 2 perchè implica $ ~ p-1 \equiv -1 \pmod q $, quindi l'ordine è 2p e divide q-1.

Passo 3: Scriviamo $ ~ (p-1)^p+1 = p^2q_2^{\alpha_2}\cdots q_{n-1}^{\alpha_{n-1}} q_n^{\alpha_n} $.
Usando ripetutamente il lemma 1 e consci per il lemma 2 che p è il minimo dei primi, vediamo che possiamo cancellare il primo più grande ed aumentare l'esponente di p, ottenendo una formula del tipo $ ~ p^{2 + \alpha}q_2^{\alpha_2}\cdots q_{n-1}^{\alpha_{n-1}} $ tale che $ ~ (2+\alpha)p + \alpha_2 q_2 + \ldots + \alpha_{n-1}q_{n-1} = 2p + \alpha_2 q_2 + \ldots + \alpha_{n-1}q_{n-1} + \alpha_nq_n $ e che $ ~ p^{2 + \alpha}q_2^{\alpha_2}\cdots q_{n-1}^{\alpha_{n-1}} > p^2q_2^{\alpha_2}\cdots q_{n-1}^{\alpha_{n-1}} q_n^{\alpha_n} $.
Cioè, possiamo eliminare il primo più grande e aumentare l'esponente di p in modo che la funzione che vogliamo stimare rimanga costante, e il valore complessivo aumenta.

Applicando ripetutamente, avremo $ ~ p^{\alpha} > (p-1)^p+1 $ e $ ~ \alpha p = 2p + \alpha_2 q_2 + \ldots + \alpha_{n-1}q_{n-1} + \alpha_nq_n $.
Siccome $ ~ p^{\alpha} > (p-1)^p+1 $, qui possiamo fare due stime:
- usare che $ ~ \sqrt{p} <p> \frac{p}2 $
- usare ancora la decrescenza di $ ~ x^{\frac 1x} $ e dimostrare che $ ~ \alpha > p-1 $.
Nel primo caso otteniamo $ ~ 2p + \alpha_2 q_2 + \ldots + \alpha_{n-1}q_{n-1} + \alpha_nq_n=\alpha p >\frac{p^2}2 $, che senz'altro ci basta
Nella seconda stima otteniamo $ ~ \alpha p > p(p-1) $ che non è male.

[enomis_costa88]

Sia p un primo maggiore di 3. Dimostrare che:

1)$ \displaystyle (p-1)^p +1 $ ha dei fattori primi diversi da p.

Mihailescu ovviamente

[salva90]

Sia p un primo maggiore di 3. Dimostrare che:

1)$ \displaystyle (p-1)^p +1 $ ha dei fattori primi diversi da p.

Mihailescu ovviamente

Per chi non lo sapesse, costui dice che non esistono due potenze consecutive a parte 8 e 9. Perciò quel numero non può essere una potenza di p e di conseguenza ha fattori primi diversi da p.
Ora, la domanda è una. Se qualcuno avesse scritto 'vero per mihailescu' l'avrebbero accettata o no come soluzione?

[edriv]

Io credo che non l'avrebbero accettata.
A quanto ne so, alle IMO qualunque teorema noto si può usare, e anche questo sarebbe accettato, ma appunto si evita esercizi che si facciano con i cannoni.
Invece prima delle IMO direi che il criterio "se il problema nella tua/sua soluzione è un caso molto particolare di un cannone che non sai/sa dimostrare, lascia perdere/dagli 0" sia ottimo, per "contestants" (perdonate l'inglesismo)/correttori.

[enomis_costa88]

Io credo che non l'avrebbero accettata.

Comunque non sarebbe giusto..se un teorema esiste ed è dimostrato perchè non usarlo?

@Salva: visto che c'è qualcuno che l'ha fatto...basta vedere se quel qualcuno prenderà 0 o 2 punti sul B3.

[salva90]

Io credo che non l'avrebbero accettata.

Comunque non sarebbe giusto..se un teorema esiste ed è dimostrato perchè non usarlo?

@Salva: visto che c'è qualcuno che l'ha fatto...basta vedere se quel qualcuno prenderà 0 o 2 punti sul B3.

quel qualcuno si chiama simone?

[giove]

Io credo che non l'avrebbero accettata.

Comunque non sarebbe giusto..se un teorema esiste ed è dimostrato perchè non usarlo?

@Salva: visto che c'è qualcuno che l'ha fatto...basta vedere se quel qualcuno prenderà 0 o 2 punti sul B3.

quel qualcuno si chiama simone?

Confermo, confermo...

[Simo_the_wolf]

Ok adesso miglioriamo il bound... Provate a dimostrare che:
$ \sum_{i=0}^k \alpha_iq_i > p^2 $

[Jacobi]

Quel k sta a significare qualsiasi intero da 1 a n o e un errore di battitura?

[enomis_costa88]

Confermo che il povero pazzo che ha usato Mihailescu ha preso 2 punti sul B3