OliForum Matematico

Questa mattina, risolvendo un problema, mi sono trovato di fronte alla seguente questione.

Dato un intero n dispari, definiamo $ \gamma(n) $ come la funzione che associa ad n il numero di interi dispari minori di esso e con esso coprimi.
Allora $ \gamma(n)=\frac12\cdot\varphi(n) $, dove $ \varphi(n) $ è la classica funzione di Eulero.

Invito gli utenti poco esperti a trovare una dimostrazione (è facile facile, garantisco).

Chiedo inoltre se in gara potrei dare per scontato tale fatto, o se devo dimostrarlo ogni volta.


Good work

salva90 ha scritto:Questa mattina, risolvendo un problema, mi sono trovato di fronte alla seguente questione.

Dato un intero n dispari, definiamo $ \gamma(n) $ come la funzione che associa ad n il numero di interi dispari minori di esso e con esso coprimi.
Allora $ \gamma(n)=\frac12\cdot\varphi(n) $, dove $ \varphi(n) $ è la classica funzione di Eulero.

Invito gli utenti poco esperti a trovare una dimostrazione (è facile facile, garantisco).

Chiedo inoltre se in gara potrei dare per scontato tale fatto, o se devo dimostrarlo ogni volta.


Good work

provo:
in sostanza bisogna dimostrare che i coprimi minori di n pari sono quanti i dispari.
se n è primo, è banale, perchè i coprimi sono tutti i numeri che lo precedono, quindi i pari sono quanti i disapri.
se n non è primo, ma fattorizzabile in $ \displaystyle n=x_1^{i_1}x_2^{i_2}.....x_m^{i_m} $ (con $ \displaystylex_k $ diverso da 2), i coprimi di n sono tutti i numeri precedenti esclusi i multipli di $ \displaystile x_k $ con k da 1 a m.
ma i multipli di $ x_k $ minori di n sono $ jx_k $ con j da 1 a $ \displaystyle\frac{n}{x_k}-1 $.
sono quindi un numero pari, e i dispari sono quanti i pari.
lo stesso vale per gli altri fattori di n.

Se d è un dispari minore di n e primo con n, p=n-d è un pari minore di n e primo con n; allo stesso modo se p è un pari minore di n e primo con n, d=n-p è un dispari minore di n e primo con n.
Dunque tra l'insieme dei d e dei p c'è una corrispondenza biunivoca, ed essi sono in numero uguale.

nicelbole ha scritto:Se d è un dispari minore di n e primo con n, p=n-d è un pari minore di n e primo con n; allo stesso modo se p è un pari minore di n e primo con n, d=n-p è un dispari minore di n e primo con n.
Dunque tra l'insieme dei d e dei p c'è una corrispondenza biunivoca, ed essi sono in numero uguale.

perfetto, era questa che volevo saltasse fuori

Ma scusate, questo è uno dei primi lemmi che si fa quando si studiano le proprietà di phi odd. Potrete trovare di più su "Zwing Czauklasi", libro di un giovane semisconosciuto ballerino sloveno sul problem solving... Parla di phi odd nel capitolo: "Wedno Doryczy Przediegu" (che vuol dire: "Ah già è vero, anche stavolta ho perso punti sul problema più facile")...

@ salva: credo di avere in mente il problema che stavi risolvendo

piever ha scritto:"Wedno Doryczy Przediegu"

Vergogna, c'è un errore di grammatica!Si scrive "Wyedno"! Eh, è amico mio sto ballerino... anche di Fede90, ma questa è un'altra storia...vero Fede? (sperando che Fede legga)