N elementi. Sottoinsieme con somma multipla di n

[antosecret]

Dimostrare che, comunque siano presi n numeri interi, è sempre possibile sceglierne un sottoinsieme non vuoto in modo che la somma degli elementi sia multipla di n.

Questo problema era stato già proposto qui:
viewtopic.php?t=7244

Con questa soluzione:

se divido a_1 , a_1 + a_2,...., a_1+....+a_n per n e trovo un resto zero il problema è risolto, sennò per il cassetto ce ne sono due con lo stesso resto e facendo la differenza risolvo il problema.

E' possibile dimostrare il problema anche senza intendere la somma come somma algebrica e cioè considerando gli n interi positivi e facendo solo addizioni tra essi???????

Grazie in anticipo dell'aiuto.

[jordan]

bo, sarò tonto io..
cioe, vuoi risolvere lo stesso problema considerando al posto di $ (a_1, a_2, ...a_n) \in Z^n $ la n-upla $ (|a_1|, |a_2|,..|a_n|) \in N^n $?

se è cosi mi sembra un tantino scontata la domanda..

[antosecret]

No. Forse mi sono espresso male.

Nella sua dimostrazione uchiak, dopo aver dimostrato che c'è una classe di congruenza con almeno 2 elementi, li sottrae x ottenere un multiplo di n.

Lui in pratica considera la sottrazione come una somma (che in un certo senso è vero). Ciò che chiedo è se è la tesi è verificata anche se consideriamo solo le addizioni (e quindi non le sottrazioni) tra i membri dell'insieme....

Spero che adesso sia più chiaro

[EvaristeG]

No .. i suoi elementi sono cose del tipo
$ a_1+a_2+\ldots+a_k $
se fai la differenza di due di questi viene fuori un'espressione del tipo
$ a_k+a_{k+1}+\ldots+a_{k+m} $
che è sempre una somma di elementi dell'insieme di partenza.

[jordan]

edit:ci ha gia pensato evariste

[antosecret]

Mi dispiace ma nn capisco......

Facciamo qualche prova, ad esempio per n = 3.
Gli insiemi possibili (modulo 3) privi di multipli di 3 sono
(1,1,1)(1,1,2)(1,2,2)(2,2,2).

In effetti, per ognuno di essi esiste un sottoinsieme la cui somma (senza considerare la differenza) è multipla di 3....

La cosa dovrebbe (a occhio) funzionare anche per numeri più grandi....
Come mai questa tesi non vale???

[edriv]

Il problema è "omunque siano presi n numeri interi, è sempre possibile sceglierne un sottoinsieme non vuoto in modo che la somma degli elementi sia multipla di n".

Questo problema è giusto, ha una soluzione, che è quella che hai scritto, ed è giusta anche quella.

Cosa vuoi tu?
Dimostrare un problema leggermente diverso?
Trovare un'altra dimostrazione?

[antosecret]

Il problema è "Comunque siano presi n numeri interi, è sempre possibile sceglierne un sottoinsieme non vuoto in modo che la somma degli elementi sia multipla di n".

E su questo ci siamo....

La soluzione di uchiak secondo me risolve invece quest'altro problema:
Comunque siano presi n numeri interi, è sempre possibile sceglierne un sottoinsieme non vuoto in modo che la somma o la differenza degli elementi sia multipla di n.

La mia domanda è:
I 2 problemi sono equivalenti??????
La soluzione di uchiak vale anche per il primo problema????
Il primo problema è vero????????

Spero (stavolta) di essermi spiegato bene.........
E scusate per la cocciutaggine...

[giove]

Sia $ a_1,a_2,\dots,a_n $ l'n-upla del testo, e siano $ b_1,b_2,\dots,b_n $ i numeri definiti così:
$ b_k=\sum_1^k a_i $

Allora o c'è un $ b_k\equiv 0 \mod n $ oppure ne esistono due con differenza $ \equiv 0 \mod n $; in entrambi i casi è multipla di $ n $ la somma di un po' di numeri della n-upla di partenza.

(E' quello che ha detto EvaristeG)

[edriv]

La soluzione di uchiak secondo me risolve invece quest'altro problema:
Comunque siano presi n numeri interi, è sempre possibile sceglierne un sottoinsieme non vuoto in modo che la somma o la differenza degli elementi sia multipla di n.

Ah ora è chiaro... è che non hai capito la dimostrazione!
A te dà fastidio che nella sua dimostrazione dice la parola "differenza".
Però attento, non sta facendo una differenza tra elementi della n-upla di partenza . Sta facendo una differenza tra "altre cose" che ha definito lui, in modo che il risultato della differenza sia anche esprimibile come somma di alcuni elementi della n-upla iniziale, e che questa somma sia multipla di n. E questo gli risolve il problema.

[antosecret]

Capito... Grazie a tutti dei chiarimenti

[Lupacante]

non sta facendo una differenza tra elementi della n-upla di partenza . Sta facendo una differenza tra "altre cose" che ha definito lui

scusa...questa volta sono io a non capire...cosa sono le 'altre cose' di cui sta facendo la differenza?

grazie