S insieme di n numeri interi positivi
Salve a tutti ragazzi,
ieri svolgendo il quesito che vi proporrò (che dovrei aver risolto bene) mi è sorto un dubbio, o meglio, diciamo che mi pare di aver colto una particolarità.
Il quesito chiedeva:
Sia $S$ un insieme di $9$ numeri interi positivi.
1) Esiste un sottoinsieme non vuoto $A sube S$ tale che la somma dei suoi elementi sia divisibile per 9?
2) Ne esiste uno tale che la somma sia divisibile per 10?
Alla prima domanda io ho risposto si, alla seconda no.
Ho ragionato in questo modo:
Un numero intero positivo diviso per 9 può dare come resti: $1,2,3,4,5,6,7,8$ (tralascio lo 0 altrimenti il quesito avrebbe ovviamente soluzione).
Noi abbiamo 9 numeri quindi 9 resti. Nel caso si cui tutti i numeri diano lo stesso resto il quesito ha soluzione perché si avrebbe $r*9$, dove $r$ indica uno dei resti.
Nel caso in cui invece i resti non siano uguali bisogna considerare il fatto che:
$1$ e $8$ se compaiono insieme danno un multiplo di nove
$2$ e $7$ " " "
$3$ e $6$ " " "
$4$ e $5$ " " "
Ho fatto molte prove combinando queste cose e ho visto che ci sono sempre sottoinsiemi che danno un multiplo di nove in un insieme di 9 elementi. (Non le metto tutte perché il post diventerebbe molto caotico, se però sto sbagliando correggetemi)
Ovviamente la 2) è falsa perché i resti possono essere $1,2,3,4,5,6,7,8,9$; ponendo il caso in cui tutti i resti siano $9$ in un insieme di nove elementi la somma non sarebbe mai un multiplo di dieci. (Ancora correggetemi se sto dicendo cose non vere)
Ora alla domanda invertita e generalizzata:
Quanti elementi deve avere un insieme affinché sia sempre possibile trovare un suo sottoinsieme proprio la cui somma degli elementi sia divisibile per un numero $n$ dato?
Io risponderei: deve avere $n$ elementi. E' giusto? (Sarebbe questa la particolarità di cui parlavo all'inizio)
Se lo è qualcuno riesce a dare una dimostrazione?
Io ci ho provato, ma non ci sono riuscito (forse perché non è la risposta giusta, ma anche questo me lo confermerete o smentirete voi
).
Grazie a tutti, spero di essere riuscito a spiegarmi!
ieri svolgendo il quesito che vi proporrò (che dovrei aver risolto bene) mi è sorto un dubbio, o meglio, diciamo che mi pare di aver colto una particolarità.
Il quesito chiedeva:
Sia $S$ un insieme di $9$ numeri interi positivi.
1) Esiste un sottoinsieme non vuoto $A sube S$ tale che la somma dei suoi elementi sia divisibile per 9?
2) Ne esiste uno tale che la somma sia divisibile per 10?
Alla prima domanda io ho risposto si, alla seconda no.
Ho ragionato in questo modo:
Un numero intero positivo diviso per 9 può dare come resti: $1,2,3,4,5,6,7,8$ (tralascio lo 0 altrimenti il quesito avrebbe ovviamente soluzione).
Noi abbiamo 9 numeri quindi 9 resti. Nel caso si cui tutti i numeri diano lo stesso resto il quesito ha soluzione perché si avrebbe $r*9$, dove $r$ indica uno dei resti.
Nel caso in cui invece i resti non siano uguali bisogna considerare il fatto che:
$1$ e $8$ se compaiono insieme danno un multiplo di nove
$2$ e $7$ " " "
$3$ e $6$ " " "
$4$ e $5$ " " "
Ho fatto molte prove combinando queste cose e ho visto che ci sono sempre sottoinsiemi che danno un multiplo di nove in un insieme di 9 elementi. (Non le metto tutte perché il post diventerebbe molto caotico, se però sto sbagliando correggetemi)
Ovviamente la 2) è falsa perché i resti possono essere $1,2,3,4,5,6,7,8,9$; ponendo il caso in cui tutti i resti siano $9$ in un insieme di nove elementi la somma non sarebbe mai un multiplo di dieci. (Ancora correggetemi se sto dicendo cose non vere)
Ora alla domanda invertita e generalizzata:
Quanti elementi deve avere un insieme affinché sia sempre possibile trovare un suo sottoinsieme proprio la cui somma degli elementi sia divisibile per un numero $n$ dato?
Io risponderei: deve avere $n$ elementi. E' giusto? (Sarebbe questa la particolarità di cui parlavo all'inizio)
Se lo è qualcuno riesce a dare una dimostrazione?
Io ci ho provato, ma non ci sono riuscito (forse perché non è la risposta giusta, ma anche questo me lo confermerete o smentirete voi
).Grazie a tutti, spero di essere riuscito a spiegarmi!
Risposte
A naso direi che la proprietà che hai detto sembra corretta, però per dimostrarla ci devo pensare un po' su.
Intanto ti dico un modo alternativo di risolvere il quesito originale (il numero 1) che ha il vantaggio di esaminare pochi casi.
Prima dimostro che, se un insieme ha $3$ elementi, allora esiste un suo sottoinsieme non vuoto tale che la somma dei suoi elementi sia divisibile per $3$.
I resti nella divisione per $3$ possono essere $0$,$1$,$2$. D'ora in poi assumo che tutti gli elementi siano $0$,$1$ o $2$ (come hai fatto tu) senza perdere di generalità.
I casi possibili sono:
- l'insieme contiene $0$: allora basta prendere $0$.
- l'insieme contiene solo $1$ o solo $2$: allora posso prendere tutti gli elementi, la cui somma sarà $3$ o $6$.
- l'insieme contiene $1$ e $2$ (non $0$): basta prendere un $1$ e un $2$.
Dimostrazione con $n=3$ finita.
Ora passo a $n=9$, quindi considero un insieme di $9$ elementi. Partiziono questi $9$ elementi in $3$ sottoinsiemi ognuno di $3$ elementi. Per quello che ho dimostrato prima, per ognuno dei $3$ sottoinsiemi posso scegliere qualche elemento in modo che la somma sia multipla di $3$. Quindi posso ottenere somme $3a, 3b, 3c$ rispettivamente dai tre sottoinsiemi.
Considero l'insieme $\{a,b,c\}$. Come dimostrato, posso scegliere alcuni dei suoi elementi in modo che la somma sia multipla di $3$. Di conseguenza posso scegliere qualcuno tra $3a, 3b, 3c$ in modo che la somma sia multipla di $9$. Se avete capito il mio ragionamento, allora sarete d'accordo che la dimostrazione è finita.
A dire il vero con questo ragionamento si dimostra questo fatto più generale:
se la proprietà vale per $n=a$ e per $n=b$, allora vale anche per $n=ab$
(nel mio caso avevo $a=b=3$)
Intanto ti dico un modo alternativo di risolvere il quesito originale (il numero 1) che ha il vantaggio di esaminare pochi casi.
Prima dimostro che, se un insieme ha $3$ elementi, allora esiste un suo sottoinsieme non vuoto tale che la somma dei suoi elementi sia divisibile per $3$.
I resti nella divisione per $3$ possono essere $0$,$1$,$2$. D'ora in poi assumo che tutti gli elementi siano $0$,$1$ o $2$ (come hai fatto tu) senza perdere di generalità.
I casi possibili sono:
- l'insieme contiene $0$: allora basta prendere $0$.
- l'insieme contiene solo $1$ o solo $2$: allora posso prendere tutti gli elementi, la cui somma sarà $3$ o $6$.
- l'insieme contiene $1$ e $2$ (non $0$): basta prendere un $1$ e un $2$.
Dimostrazione con $n=3$ finita.
Ora passo a $n=9$, quindi considero un insieme di $9$ elementi. Partiziono questi $9$ elementi in $3$ sottoinsiemi ognuno di $3$ elementi. Per quello che ho dimostrato prima, per ognuno dei $3$ sottoinsiemi posso scegliere qualche elemento in modo che la somma sia multipla di $3$. Quindi posso ottenere somme $3a, 3b, 3c$ rispettivamente dai tre sottoinsiemi.
Considero l'insieme $\{a,b,c\}$. Come dimostrato, posso scegliere alcuni dei suoi elementi in modo che la somma sia multipla di $3$. Di conseguenza posso scegliere qualcuno tra $3a, 3b, 3c$ in modo che la somma sia multipla di $9$. Se avete capito il mio ragionamento, allora sarete d'accordo che la dimostrazione è finita.
A dire il vero con questo ragionamento si dimostra questo fatto più generale:
se la proprietà vale per $n=a$ e per $n=b$, allora vale anche per $n=ab$
(nel mio caso avevo $a=b=3$)
Ecco, ci sono. E la dimostrazione generale è anche più facile di quella che ho fatto per il $9$.
Allora, abbiamo un insieme di $n$ elementi.
Si scrivano questi elementi in fila, in un ordine a piacere.
Ora sia $A_i$, per $i$ che va da $1$ a $n$, l'insieme dei primi $i$ numeri nella fila.
E sia $s_i$ la somma degli elementi di $A_i$
Se uno di questi $s_i$ è divisibile per $n$, abbiamo finito.
Altrimenti i resti che gli $s_i$ possono dare quando divisi per $n$ possono essere $1,2,3..., n-1$ (cioè $n-1$ possibilità).
Per il principio del pigeonhole esistono $s_i$ e $s_j$ (con $i>j$) che danno lo stesso resto se divisi per $n$.
Quindi considero gli elementi che appartengono ad $A_i$ ma non ad $A_j$ (tenere presente che $A_j$ è contenuto in $A_i$ per come li ho definiti).
La loro somma è multipla di $n$.
Allora, abbiamo un insieme di $n$ elementi.
Si scrivano questi elementi in fila, in un ordine a piacere.
Ora sia $A_i$, per $i$ che va da $1$ a $n$, l'insieme dei primi $i$ numeri nella fila.
E sia $s_i$ la somma degli elementi di $A_i$
Se uno di questi $s_i$ è divisibile per $n$, abbiamo finito.
Altrimenti i resti che gli $s_i$ possono dare quando divisi per $n$ possono essere $1,2,3..., n-1$ (cioè $n-1$ possibilità).
Per il principio del pigeonhole esistono $s_i$ e $s_j$ (con $i>j$) che danno lo stesso resto se divisi per $n$.
Quindi considero gli elementi che appartengono ad $A_i$ ma non ad $A_j$ (tenere presente che $A_j$ è contenuto in $A_i$ per come li ho definiti).
La loro somma è multipla di $n$.
Quindi considero gli elementi che appartengono ad Ai ma non ad Aj (tenere presente che Aj è contenuto in Ai per come li ho definiti)
mi potresti spiegare questa frase dato che non l'ho ben capita?
cioè Ai=Aj+kn, ma cosa significa quella storia sugli elementi contenuti in Ai? fattorizzazione?
Scusa, ero stato un po' impreciso in effetti, facendo confusione tra "insieme" e "somma degli elementi di un insieme".
Ma ho modificato il mio messaggio che adesso dovrebbe essere più chiaro.
Ma ho modificato il mio messaggio che adesso dovrebbe essere più chiaro.
Per la soluzione della prima domanda dell'esercizio in effetti hai ragione, se il numero n di elementi è un composto conviene scomporlo in insiemi secondo la sua fattorizzazione, almeno si lavora su un numero ristretto di elementi.
Per la dimostrazione complimenti, concisa ed elegante!
Per di più mi hai fatto scoprire il principio di pigeonhole che non conoscevo
Per la dimostrazione complimenti, concisa ed elegante!
Per di più mi hai fatto scoprire il principio di pigeonhole che non conoscevo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo