Matematici in locanda(problema Olimpiadi)

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Mick1719
Messaggi: 8
Iscritto il: 28 lug 2019, 04:06

Matematici in locanda(problema Olimpiadi)

Messaggio da Mick1719 » 20 ago 2019, 15:24

Nel Maggio di moltissimi anni fa, diversi matematici si ritrovarono in una locanda; si accorsero subito di essere esattamente tanti quanti gli interi n, compresi tra 100 e 10000, tali che il loro fattoriale n! è un multiplo di 2^(n-1).Dopo essersi contati, decisero che erano nel giusto numero per intraprendere il pellegrinaggio alla tomba di Archimede. Quanti erano?

mat2772
Messaggi: 17
Iscritto il: 06 dic 2018, 19:49

Re: Matematici in locanda(problema Olimpiadi)

Messaggio da mat2772 » 20 ago 2019, 23:57

Do un abbozzo di soluzione.
Testo nascosto:
Ogni numero naturale può essere espresso in modo univoco come somma di potenze di 2 distinte, in base binaria la quantità di 1 indica il numero di potenze utilizzate. Notiamo (avvalendoci del teorema di Legendre de Polignac) che la v_2(n!)=n-{la quantità di 1}, poiché v_2(n!)>=n-1 deduciamo che n in base 2 è scritto con un solo 1, ovvero che è una potenza di 2. Le potenze di 2 tra 100 e 10000 sono 7 (da 128 a 8192), quindi i matematici erano 7.

TeoricodeiNumeri
Messaggi: 17
Iscritto il: 14 lug 2019, 09:58

Re: Matematici in locanda(problema Olimpiadi)

Messaggio da TeoricodeiNumeri » 21 ago 2019, 12:18

Innanzitutto ringrazio mat2772 per la sua soluzione in quanto sono venuto a conoscenza della stretta relazione fra identità di Legendre e somma delle cifre della rappresentazione di $n$ in base $p$ con $p$ primo. Detto ciò, vi propongo un'altra soluzione: [math]
Testo nascosto:
Innanzitutto scriviamo l'identità di Legendre per $p=2$:
\begin{equation}
\nu_2 (n!)=\sum_{i=1}^{+\infty}\lfloor n/2^i \rfloor
\end{equation}
Dalla disuguaglianza banale $\lfloor n/2^i \rfloor \leq n/2^i$ e dalla considerazione che i termini della serie precedentemente scritta sono definitivamente $0$ si ottiene che $\nu_2 (n!)<n$ e quindi $\nu_2 (n!)\leq n-1$. Di conseguenza una formulazione equivalente della traccia è la seguente:
Quanti sono i numeri $n$ compresi fra $100$ e $10000$ tali per cui $\nu_2 (n!)=n-1$?
Consideriamo innanzitutto il caso più semplice, ovvero $n=2^a$ per qualche $a$ intero positivo. Allora, da $\nu_2 ((2^a)!)=\sum_{i=1}^{+\infty}\lfloor 2^a/2^i \rfloor=\sum_{i=0}^{a-1} 2^i=2^a -1$ si ottiene che tutte le potenze di $2$ vanno bene.
Invece supponiamo ora che $2^a<n<2^{a+1}$ per qualche $a$ intero positivo. Sfruttando il fatto che la valutazione $p$-adica è una funzione logaritmica si ottiene che $\nu_2 (n!)=\nu_2 ((2^a)!)+\nu_2 (\prod_{k=2^a +1}^n k)$, da cui $\nu_2 (n!)=n-1$ sse $\nu_2 (\prod_{k=2^a +1}^n k)=n-2^a$. Dalla considerazione che $gcd (2^a,k)=gcd(2^a,k-2^a)$ e se $\vert k\vert <2^a$ allora $\nu_2 (k)=\nu_2 (gcd(k,2^a))$ allora $\nu_2 (\prod_{k=2^a +1}^n k)=\nu_2 ((n-2^a)!)<n-2^a$ e quindi tutti e i soli numeri che soddisfano la condizione richiesta sono le potenze di $2$, cioè $128,256,512,1024,2048,4096,8192$ e quindi la soluzione è $7$.

Mick1719
Messaggi: 8
Iscritto il: 28 lug 2019, 04:06

Re: Matematici in locanda(problema Olimpiadi)

Messaggio da Mick1719 » 21 ago 2019, 17:33

Grazie mille!!

Rispondi