OliForum Matematico

"Esistono 2007 numeri interi distinti tali che la media aritmetica di ogni sottoinsieme sia un intero?" Questo è un esercizio preso da un video di Gobbino, che aggiunge alla traccia il fatto che i numeri presi non debbano avere fattori primi in comune. Potreste spiegarmi come si svolge, nel dettaglio e con le motivazioni? E soprattutto, cosa che mi sfugge, perché se non ci fosse quell'aggiunta andrebbero bene tutti i multipli di $ 2007! $?

Io non ho la soluzione..ci sto pensando, comunque devi agire sul fatto che:
$ \sum_{i=1}^n n = n(n+1) $ perciò se divi per 2 hai la media aritmetica... $ \frac {n^2+n}{2} $ ora devi solo dimostrare che $ 2|n^2+n $
devi trovare però una sommatoria che non parta da 1 ma che parta da un numero $ n_0 $ ora cerco...

Dunque... per ogni p primo (vale anche per i non primi, ma dovrebbero bastare quelli) ho che, presi due numeri qualsiasi dell'insieme (prendo $a_1$ e $a_2$ per comodità) ho che sono congrui a modulo p.
Infatti presi p elementi, la loro somma deve essere multipla di p.
Quindi
$a_1+a_3+\dots a_{p+1}$ \equiv $a_2+a_3+\dots a_{p+1} \equiv 0 \pmod p$ cioè $a_1\equiv a_2 \pmod p$.

Quindi se tutti gli elementi sono congrui a modulo $2\cdot 3 \cdot 5 \cdot \dots \cdot 2003$ (il prodotto dei primi < 2007) allora la media aritmetica di qualsiasi sottoinsieme è intera.

Era questa la soluzione? Oppure mi sono dimenticato qualcosa per la strada?

auron95 ha scritto:Era questa la soluzione? Oppure mi sono dimenticato qualcosa per la strada?

L'inizio e' giusto, la conclusione no.

Possiamo fare di meglio
Problema.Trovare tutte le $n$-uple di interi distinti $a_1,a_2,\ldots,a_n$ a due a due coprimi e con $n\ge 2$ tali che la media aritmetica di ogni sottoinsieme sia un intero.

Fissiamo un intero $2\le m\le n-2$ allora $a_i \equiv a_j \pmod m$ per ogni $1\le i<j\le n$: difatti, una volta definito $S_{m,(i,j)}$ un qualunque sottoinsieme di $\{a_1,a_2,\ldots,a_n\}\setminus\{a_i,a_j\}$ tale che $|S_{m,(i,j)}|=m-1$, e' sufficiente scegliere i due insiemi $S_{m,(i,j)}\cup\{a_i\}$ e $S_{m,(i,j)}\cup\{a_j\}$, entrambi a somma nulla in $\mathbb{Z}/m\mathbb{Z}$. In particolare $a_1\equiv a_2 \equiv \ldots \equiv a_n \pmod m$, e definiamo $\alpha_m$ tale classe di resto.

Lo stesso vale per $m=n-1$, infatti detta $S:=\sum_{1\le i\le n}{a_i}$ allora $S-a_1 \equiv S-a_2 \equiv \ldots \equiv S-a_n \pmod {m}$.

Per $m=n$ e' sufficiente che $n \mid S$.

Avremo quindi un sistema di congruenze del tipo

• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_2 \pmod 2$
• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_3 \pmod 3$
• $\ldots$
• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_{n-1} \pmod {n-1}$

Ammesso che tale sistema sia coerente (i.e. $\alpha_i$ determina univocamente $\alpha_j$ per ogni $i$ multiplo di $j$, e tale che $\alpha_{ij}$ e' univocamente determinato da $\alpha_i$ e $\alpha_j$ ogni volta che $\text{gcd}(i,j)=1$), la soluzione $\alpha$ esiste ed e' unica modulo $\text{lcm}(2,3,4,\ldots,n-1):=\ell$ grazie al teorema cinese del resto (qui possiamo imporre wlog $0\le \alpha \le \ell-1$).

Esisteranno quindi degli interi $k_1,k_2,\ldots,k_n$ tali che $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$. (*)

Deve essere solo rispettata l'ultima condizione, and we're done: $m \mid \sum_{1\le i\le n}{a_i}$ che e' verificata se e solo se $m \mid \ell \sum_{1\le i\le n}{k_i}$. (**)

Notiamo che (**) e' una conseguenza diretta di (*) se e solo se $n$ non è una potenza di un primo (correzione di ma_go, vedi sotto).

Riassumendo:

• se $n$ non è una potenza di un primo, allora tutte e sole le soluzioni sono date da $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$ per qualche intero $k_1,k_2,\ldots,k_n$
• se $n$ è una potenza di un primo, allora tutte e sole le soluzioni sono date da $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$ per qualche intero $k_1,k_2,\ldots,k_n$ tali che $n \mid \sum_{1\le i\le n}{k_i}$

[]

Uhm... mi ero dimenticato il fatto che se un numero è congruo a un altro modulo ciascuno dei fattori primi di m, non è detto che siano congrui a modulo m (se m contiene un primo elevato almeno al quadrato......)

auron95 ha scritto:Uhm... mi ero dimenticato il fatto che se un numero è congruo a un altro modulo ciascuno dei fattori primi di m, non è detto che siano congrui a modulo m (se m contiene un primo elevato almeno al quadrato......)

esatto, quindi ti bastava prendere, anziché tutti i primi minori di 2007, tutte le potenze di primi minori di 2007.

visto che son qua: diciamo che -a occhio- la soluzione di jordan (del problema più generale) si può pulire un pochino, e si possono evitare i problemi con i moduli non coprimi nel teorema cinese... ah, a proposito:

jordan ha scritto:Notiamo che (**) e' una conseguenza diretta di (*) se e solo se $n$ non è primo.

non è vero se e solo se $n$ non è una potenza un primo?

ma_go ha scritto:esatto, quindi ti bastava prendere, anziché tutti i primi minori di 2007, tutte le potenze di primi minori di 2007.

Si, che è equivalente alla definizione di $\ell=\text{lcm}(2,3,4,\ldots,n-1\}$..

ma_go ha scritto:visto che son qua: diciamo che -a occhio- la soluzione di jordan (del problema più generale) si può pulire un pochino, e si possono evitare i problemi con i moduli non coprimi nel teorema cinese...

Intendi che non servono, tanto alla fine si possono prendere tutte le classi in $(\mathbb{Z}/\ell\mathbb{Z})^*$, giusto?

ma_go ha scritto:ah, a proposito:

jordan ha scritto:Notiamo che (**) e' una conseguenza diretta di (*) se e solo se $n$ non è primo.

non è vero se e solo se $n$ non è una potenza un primo?

Sì, questo succede quando uno scrive direttamente la soluzione senza carta e penna, infatti pensavo a definire $\ell$ come $(n-1)!$ invece che $\text{lcm}(2,3,4,\ldots,n-1)$..
Pardon, edito subito

jordan ha scritto:

auron95 ha scritto:Era questa la soluzione? Oppure mi sono dimenticato qualcosa per la strada?

L'inizio e' giusto, la conclusione no.

Possiamo fare di meglio
Problema.Trovare tutte le $n$-uple di interi distinti $a_1,a_2,\ldots,a_n$ a due a due coprimi e con $n\ge 2$ tali che la media aritmetica di ogni sottoinsieme sia un intero.

Fissiamo un intero $2\le m\le n-2$ allora $a_i \equiv a_j \pmod m$ per ogni $1\le i<j\le n$: difatti, una volta definito $S_{m,(i,j)}$ un qualunque sottoinsieme di $\{a_1,a_2,\ldots,a_n\}\setminus\{a_i,a_j\}$ tale che $|S_{m,(i,j)}|=m-1$, e' sufficiente scegliere i due insiemi $S_{m,(i,j)}\cup\{a_i\}$ e $S_{m,(i,j)}\cup\{a_j\}$, entrambi a somma nulla in $\mathbb{Z}/m\mathbb{Z}$. In particolare $a_1\equiv a_2 \equiv \ldots \equiv a_n \pmod m$, e definiamo $\alpha_m$ tale classe di resto.

Lo stesso vale per $m=n-1$, infatti detta $S:=\sum_{1\le i\le n}{a_i}$ allora $S-a_1 \equiv S-a_2 \equiv \ldots \equiv S-a_n \pmod {m}$.

Per $m=n$ e' sufficiente che $n \mid S$.

Avremo quindi un sistema di congruenze del tipo

• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_2 \pmod 2$
• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_3 \pmod 3$
• $\ldots$
• $a_1\equiv a_2 \equiv \ldots \equiv a_n \equiv \alpha_{n-1} \pmod {n-1}$

Ammesso che tale sistema sia coerente (i.e. $\alpha_i$ determina univocamente $\alpha_j$ per ogni $i$ multiplo di $j$, e tale che $\alpha_{ij}$ e' univocamente determinato da $\alpha_i$ e $\alpha_j$ ogni volta che $\text{gcd}(i,j)=1$), la soluzione $\alpha$ esiste ed e' unica modulo $\text{lcm}(2,3,4,\ldots,n-1):=\ell$ grazie al teorema cinese del resto (qui possiamo imporre wlog $0\le \alpha \le \ell-1$).

Esisteranno quindi degli interi $k_1,k_2,\ldots,k_n$ tali che $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$. (*)

Deve essere solo rispettata l'ultima condizione, and we're done: $m \mid \sum_{1\le i\le n}{a_i}$ che e' verificata se e solo se $m \mid \ell \sum_{1\le i\le n}{k_i}$. (**)

Notiamo che (**) e' una conseguenza diretta di (*) se e solo se $n$ non è una potenza di un primo (correzione di ma_go, vedi sotto).

Riassumendo:

• se $n$ non è una potenza di un primo, allora tutte e sole le soluzioni sono date da $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$ per qualche intero $k_1,k_2,\ldots,k_n$
• se $n$ è una potenza di un primo, allora tutte e sole le soluzioni sono date da $a_i= k_i\ell+\alpha$ per ogni $i=1,2,\ldots,n$ per qualche intero $k_1,k_2,\ldots,k_n$ tali che $n \mid \sum_{1\le i\le n}{k_i}$

[]

Jordan se non ho capito male hai posto una condizione quella iniziale ed hai agito in dei sottoinsiemi che erano la somma di tutti gli elementi da $ a_1 $ a $ a_n $...non capisco un paio dicose..perché $ a_i \equiv a_j (mod m) $??? e Z/mZ(????????) ,per il resto..penso ce la posso fare anche da solo

jordan ha scritto:

ma_go ha scritto:esatto, quindi ti bastava prendere, anziché tutti i primi minori di 2007, tutte le potenze di primi minori di 2007.

Si, che è equivalente alla definizione di $\ell=\text{lcm}(2,3,4,\ldots,n-1\}$..

infatti parlavo con auron95, non con te lo so che le due cose sono equivalenti (e lo so che lo sai anche tu, e spero che l'abbiano capito un po' tutti qui dentro )

jordan ha scritto:

ma_go ha scritto:visto che son qua: diciamo che -a occhio- la soluzione di jordan (del problema più generale) si può pulire un pochino, e si possono evitare i problemi con i moduli non coprimi nel teorema cinese...

Intendi che non servono, tanto alla fine si possono prendere tutte le classi in $(\mathbb{Z}/\ell\mathbb{Z})^*$, giusto?

sì, dico che, a occhio, puoi evitare di considerare gli $\alpha_i$, e semplicemente risolvere tutto in termini di $a_1$ (che è un onesto numero intero, quindi non dà problemi con le congruenze). se poni $\alpha_i := a_1$ per ogni $i$, risolvi tutti i problemi di consistenza, e poi puoi usare il teorema cinese -nella direzione facile- per smontare le congruenze, per togliere tutte quelle inutili (che tanto sono consistenti tra loro), e poi di nuovo il teorema cinese -nella direzione difficile- per rimontare tutto, modulo $\ell$.
semplicemente per evitare di introdurre nuove variabili inutili: non è che sia sbagliato, per carità, ma se si può evitare è meglio

Robertopphneimer ha scritto:Jordan se non ho capito male (...)

$\mathbb{Z}/m\mathbb{Z}$ è il nome "da grandi" per indicare le classi di resto modulo $m$, con le operazioni (somma, differenza, prodotto). rileggiti le prime righe della dimostrazione per capire da dove viene la condizione $a_i \equiv a_j \pmod m$.

auron95 ha scritto: Infatti presi p elementi, la loro somma deve essere multipla di p.

questo intendi??
Non capisco la somma i p elementi è multipla di p. Vuol dire che se ho 2 elementi (facciamo $ a_1=2 $,$ a_2 =3 $ allora 2|5??Non capisco..

Robertopphneimer ha scritto:

auron95 ha scritto: Infatti presi p elementi, la loro somma deve essere multipla di p.

questo intendi??
Non capisco la somma i p elementi è multipla di p. Vuol dire che se ho 2 elementi (facciamo $ a_1=2 $,$ a_2 =3 $ allora 2|5??Non capisco..

Sì infatti se la media aritmetica è $\displaystyle \frac{a_1+a_2}{2} $ ed è intera allora il denominatore divide il numeratore, quindi $2\mid a_1+a_2$.

Ah!! così escludi tutti quelli che non danno una media aritmetica intera......ma guardate che roba.