OliForum Matematico

Teorema di Erdos-Ginzburg-Ziv (che, santoddio, ho scritto giusto alla prima botta )
Sia $n$ un intero positivo. Dati $2n-1$ numeri interi dimostrare che ne esistono $n$ distinti tra questi con somma divisibile per $n$.

Bonus del piffero:
Mostrare che sarebbe falso se al posto di $2n-1$ ci fosse $2n-2$

p.s. questo mi fatto proprio rosicare ... ci pensavo da mesi (non in modo costante... a sprazzi) perchè mi piaceva proprio come problema... pensavo di non averne cavato nulla così ieri non ho resistito e ho "spizzato" (che vuol dire scorrere rapidissimamente da cima a fondo leggendo solo quanto riesco di sfuggita... è una lettura che dura 4-5 secondi che dovrebbe fare tipo da hint) una soluzione... che ricalcava tutte idee che avevo avuto... allora oggi mi ci sono messo e a scuola l'ho dimostrato... ma la soddisfazione non è piena
Comunque il problema resta fighissimo e la soluzione ancora di più Provateci perchè se lo risolvete è una gran soddisfazione (la soluzione che ho trovato (diciamo su cui sono stato indirizzato) se non si fosse capito usa solo metodi olimpici )

Ma tutti i $2n-1$ numeri sono diversi?

Una volta avevo dimostrato che in un insieme di $n+1$ numeri, ce ne sono almeno 2 la cui differenza è divisibile per $n$...
Potrebbe essere simile la cosa? (a me pare di no...)

Drago96 ha scritto:Ma tutti i $2n-1$ numeri sono diversi?

Non per forza. Il "distinti" del testo è da intendere come: ho i numeri scritti alla lavagna e ne devo cerchiare $n$ ma non posso cerchiare 2 volte lo stesso MA se uno è scritto più volte lo posso prendere più volte.

Drago96 ha scritto: Una volta avevo dimostrato che in un insieme di $n+1$ numeri, ce ne sono almeno 2 la cui differenza è divisibile per $n$...
Potrebbe essere simile la cosa? (a me pare di no...)

Potrebbe essere un po' più difficile

dario2994 ha scritto:

Drago96 ha scritto:Ma tutti i $2n-1$ numeri sono diversi?

Non per forza. Il "distinti" del testo è da intendere come: ho i numeri scritti alla lavagna e ne devo cerchiare $n$ ma non posso cerchiare 2 volte lo stesso MA se uno è scritto più volte lo posso prendere più volte.

Drago96 ha scritto: Una volta avevo dimostrato che in un insieme di $n+1$ numeri, ce ne sono almeno 2 la cui differenza è divisibile per $n$...
Potrebbe essere simile la cosa? (a me pare di no...)

Potrebbe essere un po' più difficile

Chiaro...
direi proprio che è complicatuccio...

Se sono tutti uguali è facile:
La somma è $n_1+...+n_n = n\cdot n_1$ che diventa $n\cdot n_1\equiv 0\cdot n_1\equiv 0 \ (mod \ n)$
Stessa cosa quando sono diversi, ma tutti divisibili per $n$ .

Dato che possono essere uguali, non penso che centri molto il pigeonhole, o sbaglio?

Senti, non so se lo conosci, ma dato l'autore del post direi che questo problema è abbastanza al di sopra delle tue possibilità... Se vuoi continuare a provare fai pure, io però te lo dico prima.

sasha™ ha scritto:Senti, non so se lo conosci, ma dato l'autore del post direi che questo problema è abbastanza al di sopra delle tue possibilità...

Me ne sto accorgendo...
Mi sa che lo lascio a qualcuno più esperto...

Ma va là... cheppalle... il problema è difficile, senza dubbio, anche molto. Ma non lo è perchè lo ho piazzato io. Tra l'altro, così da sfatare questa millantata bravura, come ho scritto sopra: in mesi non sono riuscito a risolverlo... questo non vuol dire che è impossibile, ma che sono io scarso!!!
Detto ciò... questo non deve scoraggiare nessuno dal provarlo, tantopiù che è oggettivamente figo.

E ora... beh, dato che ho paura che questo robo vada a seppellirsi nell'oblio piazzo un hintone nascosto :

Mica ho detto che posti solo problemi difficili... Però, se un IMOista qualsiasi resta un bel po' di tempo su un problema, senza neanche riuscirci (ok, può capitare, come Julian a Cese...), mediamente vuol dire che quel problema è troppo per un ragazzo di prima (o al massimo di seconda, dal nick, giusto?) con poca esperienza alle spalle.

Non voleva essere un disincentivo a risolverlo, però è più utile per ognuno confrontarsi con problemi del proprio livello, o comunque non troppo più difficili. Io non mi reputo certo un campione (anche perché non lo sono), però se resto mesi su un problema e non lo risolvo, o mi sono perso una soluzione stra-facile (il che è possibilissimo ), o non lo vado a proporre a ragazzi del biennio, a meno che non abbiano già qualche esperienza e/o le conoscenze adatte...

Detto questo, io non l'ho provato seriamente a risolvere (mi sono limitato a pensarci un po' su con scarso successo), quindi potrebbe essere tranquillamente alla portata di chiunque, per quanto ne so. Ho solo espresso alcune considerazioni, sei libero di insultarmi, se vuoi, non mi offendo.

sasha™ ha scritto: un ragazzo di prima con poca esperienza alle spalle

Esattamente quello che sono!

P.S: Nell'hint, cosa vuol dire "facile"?

Risolvo il bonus del piffero:
Prendo $n-1$ zeri e $n-1$ uguali a $1$.
Quindi devo sommare almeno un uno (non ho abbastanza zeri) e la somma è sempre minore o uguale alla somma di tutti gli $2n-2$ numeri che è $n-1$. Quindi $n\not | S$ per ogni S.

paga92aren ha scritto:Risolvo il bonus del piffero:
Prendo $n-1$ zeri e $n-1$ uguali a $1$.
Quindi devo sommare almeno un uno (non ho abbastanza zeri) e la somma è sempre minore o uguale alla somma di tutti gli $2n-2$ numeri che è $n-1$. Quindi $n\not | S$ per ogni S.

Yeppa (per il simbolo di non divide usa "\nmid" che dà $\nmid$ )

Drago96 ha scritto:Nell'hint, cosa vuol dire "facile"?

Uhm... te lo stimo come un cese 1-2-3

Più che l'autore del post, direi che l'autore del teorema basta a certificare che non è poi così facile --- se c'è voluto Erdos per risolverlo, non è come fare 2+2...

Dimostro l'hint
Suppongo che, dato un insieme di 2a-1 (o 2b-1) elementi, si possono sempre scegliere a (o b) elementi con somma divisibile per a (o b).
Considero $ 2ab-1 $ numeri. Ne prendo $ 2a-1 $, di questi ne metto da parte gli a che per ipotesi sono divisibili per a. Dei rimanenti ne prendo di nuovo $ 2a-1 $ e ne metto da parte di nuovo gli a divisibili. Alla fine del procedimento mi ritrovo con $ 2b-1 $ insiemi di a elementi ciascuno (la cui somma è sempre divisibile per a) e $ a-1 $ elementi da soli.
Definisco ora i $ c_i $ come la somma degli elementi dell'i-esimo insieme di cardinalità a che ho formato: tra i $ 2b-1 $ $ c_i $ ne esistono quindi b con somma multipla di b. Risostituendo ogni $ c_i $ con gli elementi di cui è somma abbiamo un insieme di ab elementi divisibile per ab.
Da notare che la divisibilità per b è indipendente per quella di a: ad esempio potrei dividere ogni $ c_i $ per a e applicare l'ipotesi su b.

Quindi d'ora in poi posso supporre n primo

fph ha scritto:Più che l'autore del post, direi che l'autore del teorema basta a certificare che non è poi così facile --- se c'è voluto Erdos per risolverlo, non è come fare 2+2...

Lo volevo scrivere pur io, poi mi son ricordato che da qualche parte ho letto che ha il nome di erdos anche il fatto $n+1\mid \binom{2n}{n}$... che in effetti non è difficile, quindi mi sono trattenuto, ma in effetti anche solo il fatto che il teorema porta il nome di 3 matematici di cui uno è erdos può dare l'idea che non è una boiata

Sonner ha scritto:Dimostro l'hint
Suppongo che, dato un insieme di 2a-1 (o 2b-1) elementi, si possono sempre scegliere a (o b) elementi con somma divisibile per a (o b).
Considero 2ab−1 numeri. Ne prendo 2a−1, di questi ne metto da parte gli a che per ipotesi sono divisibili per a. Dei rimanenti ne prendo di nuovo 2a−1 e ne metto da parte di nuovo gli a divisibili. Alla fine del procedimento mi ritrovo con 2b−1 insiemi di a elementi ciascuno (la cui somma è sempre divisibile per a) e a−1 elementi da soli.
Definisco ora i ci come la somma degli elementi dell'i-esimo insieme di cardinalità a che ho formato: tra i 2b−1 ci ne esistono quindi b con somma multipla di b. Risostituendo ogni ci con gli elementi di cui è somma abbiamo un insieme di ab elementi divisibile per ab.
Da notare che la divisibilità per b è indipendente per quella di a: ad esempio potrei dividere ogni ci per a e applicare l'ipotesi su b.

Quindi d'ora in poi posso supporre n primo

Scritto contorto ma giusto Visto che non era tosto... a breve un altro hint per il caso $n$ primo.