Pagina 1 di 1

181. easy

Inviato: 10 giu 2015, 15:06
da 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

Re: 181. easy

Inviato: 10 giu 2015, 15:49
da 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?

Re: 181. easy

Inviato: 10 giu 2015, 15:53
da cip999
Il bonus con un cannone si uccide in fretta... :D

Re: 181. easy

Inviato: 13 giu 2015, 19:12
da 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 :D

Re: 181. easy

Inviato: 17 lug 2015, 14:53
da Drago96
Suvvia, qualcuno risolva il problema facile!

Re: 181. easy

Inviato: 19 lug 2015, 21:57
da 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]

Re: 181. easy

Inviato: 24 lug 2015, 12:11
da rizzo-5
Scusate la domanda stupida, ma con $\sum_{i\in I}a_i$ si intende che si possono anche sottrarre due $a_i$?

Re: 181. easy

Inviato: 28 lug 2015, 01:10
da 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...