181. easy

[Mountains Drew]

Problema staffetta (facile)
Dati $p$ interi $a_1, ... , a_p$ con $p$ intero (non per forza primo), dimostrare che esiste un insieme $I \subseteq \{ 1,2, ..., p\}$ non vuoto tale che $ \sum\limits_{i\in I}a_i $ è multiplo di $p$

Bonus (per non lasciarlo troppo semplice)
Dati $n(p-1)+1$ vettori $a_1, ... , a_{n(p-1)+1}$ appartenenti a $\left(\mathbb{Z}/p\mathbb{Z}\right)^n$ con $p$ primo, dimostrare che esiste un insieme $I \subseteq \{1,2, ..., n(p-1)+1\}$ non vuoto tale che $ \sum\limits_{i\in I}a_i $ sia il vettore nullo

[Drago96]

Nel vero problema direi che non è necessario $p$ primo...
E poi il bonus

Testo nascosto:

si fa anche con pigeonhole o serve un po' di artiglieria?

[cip999]

Il bonus con un cannone si uccide in fretta...

[Mountains Drew]

Avevo provato anche il punto b con pigeonhole e non ero riuscito... poi magari si fa, ma non così agilmente come il punto a.

Mentre col cannone è tutto più facile

[Drago96]

Suvvia, qualcuno risolva il problema facile!

[jordan]

O uno è multiplo di $p$, o altrimenti abbiamo $p-1$ possibilità: consideriamo le $p$ somme $x_1+...+x_n$. O una è zero o due di essi sono uguali modulo $p$. Nell'ultimo caso, prendiamo la differenza tra queste due.

Ora, andiamo con quello un po' piu' difficile? [Se non sbaglio, anche quello è già stato sull'oliforum]

[rizzo-5]

Scusate la domanda stupida, ma con $\sum_{i\in I}a_i$ si intende che si possono anche sottrarre due $a_i$?

[Enigmatico]

In questo caso no, perché gli $a_{i}$ sono tutti interi positivi... Diciamo che il procedimenti di jordan è un modo per trovare gli $a_{i}$ utili, senza, però sottrarl. Ad un orario più decente se vuoi ti posto la soluzione estesa che mi ha mandato per pm dopo che ho avuto lo stesso tuo dubbio...