OliForum Matematico

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

Jordan, potresti postare una soluzione o inviarmela per messaggio privato? Tra l'altro, mi pare che la cosa funzioni anche se "al minimo 2k residui diversi" diventa "al minimo k+1 residui diversi", confermi?

Grazie,
Pietro

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.

edriv ha scritto:{...} Assurdo.

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.

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

piever 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.

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 risposte