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
181. easy
-
- Messaggi: 59
- Iscritto il: 25 mag 2013, 16:41
- Località: Bregnano (Provincia di Como)
181. easy
Ultima modifica di Mountains Drew il 13 giu 2015, 19:13, modificato 2 volte in totale.
Re: 181. easy
Nel vero problema direi che non è necessario $p$ primo...
E poi il bonus
E poi il bonus
Testo nascosto:
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: 181. easy
Il bonus con un cannone si uccide in fretta...
-
- Messaggi: 59
- Iscritto il: 25 mag 2013, 16:41
- Località: Bregnano (Provincia di Como)
Re: 181. easy
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
Mentre col cannone è tutto più facile
Re: 181. easy
Suvvia, qualcuno risolva il problema facile!
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: 181. easy
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]
Ora, andiamo con quello un po' piu' difficile? [Se non sbaglio, anche quello è già stato sull'oliforum]
The only goal of science is the honor of the human spirit.
Re: 181. easy
Scusate la domanda stupida, ma con $\sum_{i\in I}a_i$ si intende che si possono anche sottrarre due $a_i$?
-
- Messaggi: 79
- Iscritto il: 03 dic 2014, 23:23
Re: 181. easy
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...