k è un intero non negativo.
sono dati gli interi a(1), a(2), a(3)...a(n) tali modulo (n+k) danno al minimo 2k residui diversi.
provare che esiste almeno un sottoinsieme non vuoto di a(1), a(2)...a(n) tale che la somma è divisibile per (n+k).
è una generalizzazione di un esercizio che avevo gia postato...
good work
residui (from kurschak2000)
La mia soluzione... però con il bound di piever, chiaramente!
Con il bound di jordan proprio non saprei come farla.
Prendiamo dalla nostra sacca di numeri il più grande sottoinsieme possibile di residui distinti (mod n+k):
$ ~ a_1,a_2,a_3,\ldots,a_i $ (dove $ ~ i \ge k+1 $).
Quindi ogni altro residuo sarà uguale ad uno di questi.
Ora consideriamo questi sottoinsiemi di A (sì, chiamiamo A l'insieme degli interi dati inizialmente, assumendoli a due a due distinti [insomma, è un insieme di residui etichettati]).
$ ~ \{a_1\},\{a_2\},\ldots,\{a_i\} $ (prima serie)
Ponendo $ ~ X = \{a_1,\ldots,a_i\} $,
$ ~ X \setminus \{a_1\},\ldots,X \setminus \{a_i\} $ (seconda serie)
La terza serie si costruisce partendo da X e aggiungendo ogni volta un elemento che è ancora rimasto fuori, a conclusione della catena c'è A.
Supponiamo che la somma degli elementi di ciascun sottoinsieme non sia 0 modulo n+k. Supponiamo ora che due insiemi elencati abbiano la stessa somma (mod n+k):
- se tra questi due ce n'è uno della terza serie, allora o è contenuto nell'altro oppure contiene l'altro; in ogni caso facendo la loro differenza troviamo un sottoinsieme con somma 0.
- se sono entrambi della prima serie o della seconda serie... andiamo contro l'assunzione che gli $ ~ a_i $ erano distinti.
- quindi gli insiemi sono $ ~ \{a_j\}, X \setminus \{a_u\} $. Se j e u fossero distinti, allora il primo sarebbe contenuto nel secondo e fine. Quindi j = u, in particolare $ ~ a_j = a_1 + \ldots + a_{j-1} + a_{j+1} + \ldots + a_i $, ponendo s = somma degli a_i, abbiamo $ ~ 2a_j = s $. Questo può accadere per solo due j distinti (in particolare se n+k è dispari, solo uno!).
Concludiamo che, di tutti gli insiemi sopra elencati, esistono al più due coppie disgiunte con la stessa somma. Nella prima serie ci sono i insiemi, nella seconda altri i, nella terza (si va da i elementi ad n) ce ne sono n-i+1; in totale n+i+1. Calcolando anche il caso in cui due coppie avessero somma uguale (sempre mod n+k), abbiamo almeno n+i-1 somme distinte e diverse da 0. Inoltre $ ~ i \ge k+1 $, quindi abbiamo almeno n+k somme distinte e diverse da 0 modulo n+k. Assurdo.
Con il bound di jordan proprio non saprei come farla.
Prendiamo dalla nostra sacca di numeri il più grande sottoinsieme possibile di residui distinti (mod n+k):
$ ~ a_1,a_2,a_3,\ldots,a_i $ (dove $ ~ i \ge k+1 $).
Quindi ogni altro residuo sarà uguale ad uno di questi.
Ora consideriamo questi sottoinsiemi di A (sì, chiamiamo A l'insieme degli interi dati inizialmente, assumendoli a due a due distinti [insomma, è un insieme di residui etichettati]).
$ ~ \{a_1\},\{a_2\},\ldots,\{a_i\} $ (prima serie)
Ponendo $ ~ X = \{a_1,\ldots,a_i\} $,
$ ~ X \setminus \{a_1\},\ldots,X \setminus \{a_i\} $ (seconda serie)
La terza serie si costruisce partendo da X e aggiungendo ogni volta un elemento che è ancora rimasto fuori, a conclusione della catena c'è A.
Supponiamo che la somma degli elementi di ciascun sottoinsieme non sia 0 modulo n+k. Supponiamo ora che due insiemi elencati abbiano la stessa somma (mod n+k):
- se tra questi due ce n'è uno della terza serie, allora o è contenuto nell'altro oppure contiene l'altro; in ogni caso facendo la loro differenza troviamo un sottoinsieme con somma 0.
- se sono entrambi della prima serie o della seconda serie... andiamo contro l'assunzione che gli $ ~ a_i $ erano distinti.
- quindi gli insiemi sono $ ~ \{a_j\}, X \setminus \{a_u\} $. Se j e u fossero distinti, allora il primo sarebbe contenuto nel secondo e fine. Quindi j = u, in particolare $ ~ a_j = a_1 + \ldots + a_{j-1} + a_{j+1} + \ldots + a_i $, ponendo s = somma degli a_i, abbiamo $ ~ 2a_j = s $. Questo può accadere per solo due j distinti (in particolare se n+k è dispari, solo uno!).
Concludiamo che, di tutti gli insiemi sopra elencati, esistono al più due coppie disgiunte con la stessa somma. Nella prima serie ci sono i insiemi, nella seconda altri i, nella terza (si va da i elementi ad n) ce ne sono n-i+1; in totale n+i+1. Calcolando anche il caso in cui due coppie avessero somma uguale (sempre mod n+k), abbiamo almeno n+i-1 somme distinte e diverse da 0. Inoltre $ ~ i \ge k+1 $, quindi abbiamo almeno n+k somme distinte e diverse da 0 modulo n+k. Assurdo.
mm, ho postato qst problema sl xke era una generalizzazione carina di "presi 17 numeri allora se faccio qlk somma ce ne sarà una multipla di17"e ammetto che è uno dei poki che posto senza sapere la soluzione, cmq il testo è giusto,controllato, quindi dovrò pensare a una soluzione piu facile (visto che il buond è molto piu grande)..appena miviene in mente la posto
The only goal of science is the honor of the human spirit.
E' solo una questione di convinzione che una soluzione semplice deve esserci... metodo che, applicato ad un altro topic di TdN su questo forum, per quanto mi riguarda ha poco successo... visto che quel topic ha 0 rispostepiever ha scritto: CLAP CLAP CLAP
Su MathLinks avevo visto una simpatica emoticon con un pupazzetto che si prostrava al suolo, e' un peccato che qui non ci sia.
