Dimostrazione su un insieme di numeri interi.

[UmbertoM1]

Sia $A$ un insieme di $k$ numeri interi strettamente positivi e distinti.
Dimostrare che esiste sempre un sottoinsieme non vuoto di $A$ (che può anche coincidere con $A$), tale che $k$ divide la somma dei numeri che compongono tale sottoinsieme.
Ecco un tentativo di soluzione.

Ciascuno dei $k$ elementi dell'insieme $A$ si può scrivere nella forma $ak+b$, ove $a,binNN$ con l'ulteriore condizione che $0

Cita

Segnala

---

Risposte

xXStephXx

1 ago 2012, 08:10

Se l'ho già visto vale lo stesso? (Intendo proprio che ho già visto la dimostrazione fatta da qualcun altro)
Che poi la dimostrazione è carina però non è tanto facile avere l'idea giusta.

Cita

Segnala

---

FreddyKruger

2 ago 2012, 06:45

Vale vale

Cita

Segnala

---

xXStephXx

2 ago 2012, 08:47

Ok xD Questo dovrebbe essere abbastanza famoso dato che l'avevo trovato in diverse fonti.

Anzitutto il tentativo di soluzione ci sta, cioè si considerano sempre i resti nei problemi di questo tipo.

Poi, ordinando gli elementi di $A$ come: $a_1,a_2,a_3,...,a_k$ consideri queste somme:
$a_1$
$a_1+a_2$
$a_1+a_2+a_3$
$a_1+a_2+a_3+a_4$
....
$a_1+a_2+a_3+a_4+...+a_k$
Praticamente l'idea era questa
Ora se una delle somme scritte sopra è multipla di $k$ il problema è risolto. Altrimenti,
se nessuna di quelle somme è multipla di $k$ vuol dire che dividendo per $k$ i resti possibili sono $k-1$.
Cioè tutti tranne lo $0$. Ma le somme scritte sopra sono $k$. Quindi per il principio dei cassetti esistono almeno due somme di quelle scritte sopra aventi lo stesso resto. Ora sicuramente una delle due ha più elementi dell'altra. Quindi si fa la sottrazione tra quella con più elementi e quella con meno elementi, ottenendo come risultato un numero divisibile per $k$. Ma siccome la somma con più elementi contiene anche tutti gli elementi della somma con meno elementi, fare la differenza tra le due somme equivale a togliere dalla somma con più elementi tutti gli elementi contenuti nella somma con meno elementi. Quindi come risultato rimane una somma tra elementi di $A$ divisibile per $k$.

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[xXStephXx]

Se l'ho già visto vale lo stesso? (Intendo proprio che ho già visto la dimostrazione fatta da qualcun altro)
Che poi la dimostrazione è carina però non è tanto facile avere l'idea giusta.

[FreddyKruger]

Vale vale

[xXStephXx]

Ok xD Questo dovrebbe essere abbastanza famoso dato che l'avevo trovato in diverse fonti.

Anzitutto il tentativo di soluzione ci sta, cioè si considerano sempre i resti nei problemi di questo tipo.

Poi, ordinando gli elementi di $A$ come: $a_1,a_2,a_3,...,a_k$ consideri queste somme:
$a_1$
$a_1+a_2$
$a_1+a_2+a_3$
$a_1+a_2+a_3+a_4$
....
$a_1+a_2+a_3+a_4+...+a_k$
Praticamente l'idea era questa
Ora se una delle somme scritte sopra è multipla di $k$ il problema è risolto. Altrimenti,
se nessuna di quelle somme è multipla di $k$ vuol dire che dividendo per $k$ i resti possibili sono $k-1$.
Cioè tutti tranne lo $0$. Ma le somme scritte sopra sono $k$. Quindi per il principio dei cassetti esistono almeno due somme di quelle scritte sopra aventi lo stesso resto. Ora sicuramente una delle due ha più elementi dell'altra. Quindi si fa la sottrazione tra quella con più elementi e quella con meno elementi, ottenendo come risultato un numero divisibile per $k$. Ma siccome la somma con più elementi contiene anche tutti gli elementi della somma con meno elementi, fare la differenza tra le due somme equivale a togliere dalla somma con più elementi tutti gli elementi contenuti nella somma con meno elementi. Quindi come risultato rimane una somma tra elementi di $A$ divisibile per $k$.